Gathering by oblivious robots on graphs
Oblivious Look–Compute–Move robots must all reach one node of a graph and stay there; which starts can be gathered depends on the symmetries of the graph, on multiplicity detection and on the scheduler.
Problem statement and measuresexpand
\(k \ge 2\) anonymous, oblivious robots stand on the nodes of a connected anonymous graph \(G\) with \(n\) nodes, which every robot sees whole. A robot runs Look–Compute–Move cycles: in a Look it takes a snapshot of the graph with its occupied nodes, it computes from that snapshot only, and it stays or moves to a neighbour; moves are instantaneous, so robots are always seen on nodes. A node with two or more robots is a tower. With multiplicity detection a snapshot shows which nodes are towers (weak) or how many robots each node holds (strong); without it a tower looks like one robot. The robots must reach a configuration in which all of them are on one node and none moves again. A setting fixes the scheduler, the multiplicity detection, whether towers may exist at the start, and the graph class; an algorithm must gather from every start of the setting except the starts listed as unsolvable. Under round robin the scheduler activates one robot at a time in a fixed cyclic order. Time is counted in epochs: an epoch is an interval in which every robot completes at least one cycle (under round robin, \(k\) consecutive activations).
Measures: Time, epochs until all robots are on one node and no robot moves again.
Rings, ASYNC, weak multiplicity detection
draftWith weak multiplicity detection, an odd number of asynchronous robots gathers on a ring exactly from the starts that are not periodic; two robots never gather.
Assumed (added on the last edge are outlined)
Not assumed
Formal definitions of this setting
- Graph dynamics: static graph
- \(G_t=G\) for all \(t\): the edge set never changes.
- Edge direction: undirected
- \(G=(V,E)\) with \(E\subseteq\binom V2\); every edge can be traversed in both directions.
- Faults: no faults
- All agents follow the algorithm forever.
- Network: ring
- An anonymous, unoriented ring of \(n\) nodes.
- Multiplicity detection: weak detection
- A snapshot marks every occupied node as holding one robot or more than one.
- Initial configuration: dispersed start
- Every initially occupied node holds exactly one agent (\(\ell=k\)). Also called a scattered start, notably in black hole search.
- Scheduler: ASYNC
- ASYNC: each robot's Look, Compute and Move phases take finite but unbounded, adversarially chosen time; a robot may Look while others are between phases, so it may move on an outdated snapshot. A robot is always seen on a node (moves are instantaneous). The scheduler is fair: every robot is activated infinitely often.
- Activation order: any order
- The adversary chooses which robots to activate, subject only to the scheduler's fairness.
Statement for this variant
Starts have one robot per node. A start is periodic if a rotation of the ring other than the identity maps the occupied nodes onto themselves.
What is known
- periodic starts (Theorem 3.1)
- starts of an even number of robots on a ring of even size that are symmetric about an axis through the middles of two edges (Theorem 3.2)
- the adversary activates all robots together, so the symmetry persists; holds even under FSYNC
- \(k = 2\), from a start at odd distance (Proposition 2.1)
- \(k = 4\) robots on a ring of 7 nodes, from a symmetric start whose axis passes through a node (start (i) of their Fig. 3; Theorem 3.5)
- computer-assisted: Lemmas 3.2–3.4 restrict the moves any algorithm may make, and all 57 600 remaining strategies were explored and fail
- the same robots gather in SSYNC (Theorem 4.2), so asynchrony is the obstacle
Results, in order of publication
Theorem 6.1; with Theorem 3.1 this settles odd \(k\). Time is not analysed. For even \(k\) the paper leaves open the symmetric starts whose axis passes through a node (Section 7).
Open questions
Even \(k\): which symmetric starts whose axis passes through a node can be gathered? Left open by Klasing et al. 2008; four robots on rings of seven and nine nodes cannot gather from some of them D'Emidio et al. 2018, and the proofs do not extend to other ring sizes. Later ring papers listed in Cicerone et al. 2025d were not read here.
Notes
Read: the model section, Proposition 2.1, Theorems 3.1, 3.2 and 6.1 and the conclusion of Klasing et al. 2008; the algorithms were not checked in detail. D'Emidio, Di Stefano, Frigioni and Navarra show, with a computer-assisted search, that four robots on a ring of seven nodes cannot gather in ASYNC from a symmetric start whose axis passes through a node (Theorem 3.5), which disproves conjectures of Klasing et al. 2008 and of Koren about which starts can be gathered; four robots on nine nodes are ungatherable too (the IWOCA 2015 version, as reported), and the unified ring algorithm of D'Angelo, Di Stefano and Navarra, which delegates four robots to Koren's algorithm, does not cover these starts D'Emidio et al. 2018. On rings, FSYNC robots are strictly stronger than SSYNC ones, which are strictly stronger than ASYNC ones: four robots on a ring of five nodes gather in FSYNC but not in SSYNC (Theorem 4.1, Corollary 4.3). Model checking found deadlocks in the ring-gathering algorithm of D'Angelo, Di Stefano and Navarra (Distributed Computing 2014) for symmetric configurations with two multiplicities Doan et al. 2017.
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.