CS Paper Radar

Byzantine Resilience of Robot Gathering under Round-Robin Scheduling

Fabian Frei, Yuichi Sudo, Koichi Wada

cs.DC ·submitted 2026-11-17 11:48 UTC · v1
theory

Abstract

We study deterministic gathering of $n$ anonymous, oblivious mobile robots in the plane under round-robin scheduling with rigid movement, in the presence of $f$ Byzantine robots. Robots observe all robot positions with their multiplicities, while their local coordinate systems may change adversarially between activations. The goal is for all correct robots to gather at a single point in finite time and remain there forever. We analyze ToMax, a simple algorithm that moves to a point of maximum multiplicity and stays still if and only if its current position is the unique maximum. We prove that ToMax achieves gathering whenever $f\le\lfloor\sqrt{n}/2\rfloor$, establishing an $Ω(\sqrt{n})$ lower bound on the achievable Byzantine resilience.

Closest papers

Nearest neighbours by meaning across the whole index.

When Robots Crash: Optimal Asynchronous Gathering at Weber Meeting Nodes

cs.DC cs.CGcs.MA ·2026-10-03 ·Animesh Maiti, Prakhar Shukla, Abhinav Chakraborty, Subhash Bhagat
theory similarity 0.72
Abstract

We study the \textit{optimal gathering} problem over a finite set of designated \textit{meeting nodes} for \textit{asynchronous, anonymous,} and \textit{oblivious} mobile robots on an infinite grid under crash faults. The robots have global visibility and strong multiplicity detection, but share neither a coordinate system nor chirality. The objective is to gather all non-faulty robots at a \textsc{Weber Meeting Node}, minimizing the total Manhattan distance from their initial positions. Up to $n-2$ robots may crash permanently, and such crashes are indistinguishable from arbitrary delays. Existing approaches often rely on a designated robot to break symmetry, whose crash may block the remaining robots indefinitely. Instead, our approach enables every robot to independently select the same target from its snapshot, while target-dependent restricted shortest paths preserve the target as a \textsc{Weber Meeting Node}. We prove that, under strong multiplicity detection, optimal gathering is impossible from certain fully symmetric configurations. For all remaining configurations, our algorithm \textsc{CrashTolerantWeberGathering()} selects a unique common target, preserves its optimality throughout the execution, and allows non-faulty robots to progress without waiting for crashed robots, thereby guaranteeing gathering in finite time.

0.14

Budget-Constrained Fault-Tolerant Mutual Visibility for Autonomous Robots under the Mobility Fault Model

cs.DC cs.CGcs.MAcs.RO ·2026-10-03 ·Prakhar Shukla, Animesh Maiti, Shivam Kumar, Subhash Bhagat
similarity 0.62
Abstract

We investigate the mutual visibility problem for a swarm of $n\ge3$ autonomous mobile robots under the budget-constrained mobility fault model. The robots are opaque, so if three robots are collinear, the middle robot obstructs the visibility between the other two. Each robot is assigned a finite movement budget, reflecting its limited energy, that bounds the total distance it may traverse during the execution. Moreover, an arbitrary number of robots may become permanently immobile due to mobility faults. The objective is to design a distributed algorithm that enables the non-faulty robots to coordinate their movements so that, within a finite time, every non-faulty robot attains unobstructed visibility of all robots in the system, including the faulty ones, while respecting the prescribed movement budget. We consider luminous robots operating under the $\mathsf{SSYNC}$ model with non-rigid movements, without any agreement on their local coordinate systems, and equipped only with a {\it common fixed reference point}. We present a deterministic distributed algorithm that solves the problem despite an arbitrary number of mobility faults. The algorithm guarantees mutual visibility for the non-faulty robots, respects the movement budget of every robot, provides collision-free movements for the robots, and uses only 12 light colors.

0.26

Min-Max Uniform Circle Formation by Asynchronous Mobile Robots

cs.DC cs.CGcs.MA ·2026-10-04 ·Animesh Maiti, Prakhar Shukla, Subhash Bhagat
similarity 0.61
Abstract

Given a set of point robots $\mathcal{R}$ in the Euclidean plane and a target circle $\mathbf C$ enclosing all robot positions, the \textsc{Min-Max Uniform Circle Formation (MMUCF)} problem requires the robots to move to distinct positions on $\mathbf C$ such that the final configuration forms a regular $n$-gon while minimizing the maximum distance traveled by any robot. Uniform circle formation is a fundamental coordination task in swarm robotics with applications in perimeter monitoring, surveillance, boundary coverage, and pattern formation. The literature does not address the optimization of the maximum individual displacement during the formation process. In this work, we study the min--max versions of the circle formation and uniform circle formation problems, where the goal is to minimize the maximum distance traveled by any robot. We consider these problems under the $\mathcal{ASYNC}$ model, where robots are autonomous, anonymous, identical, homogeneous, oblivious, and silent, and operate under the \textit{Look--Compute--Move} model with non-rigid motion. We first give necessary conditions for a deterministic solution and then present deterministic, distributed, and collision-free algorithms that form a circle and a uniform circle in finite time while minimizing the maximum movement. The algorithms ensure that robots reach distinct positions on the circle and, in the uniform case, equally spaced positions on $\mathbf C$ under the considered model.

0.17

Universal Rendezvous of Anonymous Agents with Footprints

cs.DC ·2026-08-10 ·Bibhuti Das
similarity 0.61
Abstract

Deterministic rendezvous for two anonymous mobile agents starting simultaneously from two distinct nodes of an anonymous connected graph and navigating synchronously in the graph requires that they meet at some node. An instance of the rendezvous problem is the underlying graph, together with two distinct nodes that are the initial positions of the agents. Such an instance is said to be feasible if there is a deterministic algorithm guaranteeing rendezvous, possibly valid only for this instance. A rendezvous algorithm is said to be universal for a class of instances if it guarantees rendezvous for all feasible instances from this class. We consider the model with footprints: whenever an agent visits an unmarked node, it leaves a permanent footprint on it, and all footprints are identical. This paper aims at answering the open problem from the paper by Das and Pelc (SPAA 2026), asking whether there exists a universal rendezvous algorithm for the class of all instances in the model with footprints. We propose a universal rendezvous algorithm for the class of all instances where the underlying graph is connected (finite or countably infinite) in the model with footprints. This shows the existence of a universal algorithm for the class of all instances in the model with footprints, which is an affirmative answer to the open problem.

0.04

Oblivious Self-Distance Symmetric Rendezvous on the Integer Line

cs.DM ·2026-09-12 ·Konstantinos Georgiou, Claude Gravel, Joey Kapusin, Lazar Mandic
similarity 0.60
Abstract

Symmetric rendezvous on the line is a search problem in which two agents, initially placed at distance $2d$, must follow the same randomized strategy to meet as quickly as possible. In the standard model, agents may condition their actions on the entire execution history, and both the known- and unknown-distance variants admit expected rendezvous time $Θ(d)$. We study the role of memory by introducing oblivious self-distance strategies, in which an agent's decision depends only on her position relative to her own starting location. For an initial separation of $2d$, let $R_d$ denote the optimal oblivious expected rendezvous time in the known-distance setting. We develop two finite-state frameworks based on absorbing Markov chains. Truncated chains give computable upper bounds through finite-support strategies, while weak-peek chains give lower bounds through a revealed-information relaxation. Together, they provide a mechanism for certifying optimality. Using that mechanism, we determine $R_1$ exactly and prove that it is attained by a finite-support strategy. For $d=2,\ldots,6$, numerical optimization gives the same truncation structure and objective values, yielding rigorous upper bounds below $7.83d^2$. We do not prove that the computed weak-peek minimizers are global, but the stability of the computations leads us to conjecture that they are, in which case the corresponding truncated strategies are optimal. We also prove that $R_d=Θ(d^2)$. In the unknown-distance setting, we construct a universal strategy, independent of $d$, with expected rendezvous time $O(d^{2+η})$ for every fixed $η>0$. Thus, under the memory restriction, the known-distance rendezvous time becomes quadratic, while near-quadratic performance remains possible even without knowing $d$. The asymptotic analysis uses birth-death Markov chains and their electrical-network interpretation.

0.29

Mechanism Design for Facility Location Games Under a Prelocated Facility

cs.GT ·2026-08-31 ·Genjie Qin, Qizhi Fang, Wenjing Liu
publishedtheory similarity 0.59
Abstract

We study the problem of locating a new homogeneous facility under a prelocated facility. Here, a set of $n$ agents is located on a real line or a circle, each of whom has her location as private information, and her cost is the (expected) distance from her location to the nearest facility. Our goal is to design mechanisms which can approximately minimize the maximum cost or the social cost while eliciting agents' private information truthfully (i.e., strategy-proof). Based on real-life scenarios, we consider the problem in two settings: the general setting where each agent can be located at both sides of the prelocated facility, and the special setting where all the agents are located at the same side of the prelocated facility. For agents on a line, in the general setting, we design the best possible deterministic strategy-proof mechanism with $2$-approximation and provide a lower bound of $1.5-ε\textbf{ }(ε>0)$ for any randomized strategy-proof mechanism under the maximum cost objective. For the social cost, we obtain an upper bound of $n$ for deterministic strategy-proof mechanisms and lower bounds of $1.5$ and $1.0425$ for any deterministic strategy-proof mechanism and any randomized strategy-proof mechanism, respectively. In the special setting, we further provide a randomized strategy-proof $5/3$-approximation mechanism for the maximum cost and a deterministic strategy-proof $(n-1)$-approximation mechanism for the social cost. For agents on a circle, we provide a deterministic strategy-proof 2-approximation mechanism under the maximum cost objective.

0.39

DeFSM: Robust and Efficient Decentralization of Federated Submodular Maximization

cs.DC cs.LG ·2026-11-09 ·Duc A. Tran, Dung Truong, Duy Le
theory similarity 0.58
Abstract

Submodular maximization seeks a small subset best representing a large dataset. In its federated setting, the server is a single point of failure and some clients may be Byzantine. Removing the server raises a trilemma of decentraliza- tion, efficiency, and security. We propose DeFSM, a Byzantine-robust and communication-efficient architecture that replaces the server with a lightweight smart contract and a pool of independent, consensus-free agents. Its aggregation rule, SafeGM, builds on two notions from combinatorial geometry: Tukey depth and safe points (the points lying in the convex hull of the good points wherever the bad points are). SafeGM makes the robust decision on 2D Gaussian random projections, which the contract can compute efficiently, and lifts it back as a convex combination of actual updates. Since lifting loses information, it uses the projected geometric median only when its depth certifies it, and otherwise a Tukey median. The share of bad updates is then bounded only by a count: how many there are, not what they contain. We prove, and confirm empirically, that this bound controls the solution quality. On CIFAR10 and PathMNIST, with up to 30% Byzantine clients and agents, DeFSM never collapses and retains on average about 91% of the quality of the ideal reference, the geometric median at a trusted central server. The geometric median decentralized in its best setting would retain about 96%, but the contract cannot compute it, and so each agent would have to download six times more data, or each client twice as much.

0.15

Conflicting Pattern Formation by Teams of Anonymous, Fully Disoriented Robots

cs.DC cs.CGcs.MAcs.RO ·2026-09-20 ·Animesh Maiti, Prakhar Shukla, Subhash Bhagat
similarity 0.58
Abstract

Two groups of autonomous, anonymous, and oblivious mobile robots are deployed in the two-dimensional Euclidean plane, each assigned a distinct task. We study a setting where the two groups must simultaneously solve two conflicting pattern formation problems: the \textit{gathering problem}, where robots gather at a point not known to them a priori, and the \textit{circle formation problem}, where robots occupy distinct positions on the boundary of a circle. Although each robot knows its own task, it cannot identify other members of its group. A prior solution~\cite{Conflict-1} addressed this problem for asynchronous robots having {\it direction-only axis agreement} and {\it global weak multiplicity detection} capability available to all robots in both groups. In contrast, in this work, we consider fully {\it disoriented robots} without any axis agreement or common \textit{chirality}. We study the feasibility of a solution to this problem for {\it disoriented robots}. We propose a distributed algorithm that solves the problem for semi-synchronous disoriented robots with non-rigid movements. Our proposed algorithm assumes global weak multiplicity detection only for the gathering group, while for the circle formation group, it requires local weak multiplicity detection.

0.22