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, round robin, no multiplicity detection
standard settingverifiedUnder round robin, robots that cannot see towers gather on a ring from every start except a few listed ones, in at most \(n-3\) epochs, which is optimal up to a constant factor.
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: no multiplicity detection
- A snapshot shows which nodes are occupied, not how many robots each holds.
- Initial configuration: any start
- Agents start at arbitrary nodes; \(\ell\le k\) nodes are initially occupied, possibly with several agents each.
- Scheduler: sequential
- Sequential: an SSYNC scheduler that activates exactly one robot per round, fairly; which robot is the adversary's choice unless the activation order is fixed (see the order axis).
- Activation order: round robin
- With the sequential scheduler: the robots are activated one per round in a cyclic order that the adversary fixes at the start, that the robots do not know, and that repeats forever; an epoch is \(k\) consecutive rounds, one activation per robot.
Statement for this variant
Towers may exist at the start and are invisible. The unsolvable starts are those whose occupied nodes are exactly two adjacent nodes or three consecutive nodes, those with every node occupied, and on the 5-node ring some starts with three or four occupied nodes Navarra & Piselli 2025.
What is known
- \(k \ge 3\) robots whose occupied nodes are exactly two adjacent nodes, three consecutive nodes, or all \(n\) nodes (Theorem III.2)
- on the 5-node ring with \(k \ge 5\) robots: three occupied nodes with a tower next to another occupied node (Theorem III.3), or four occupied nodes (Corollary III.1)
- the adversary chooses where the hidden towers are and the cyclic order; on two adjacent occupied nodes every robot must move to the other node (Lemma III.1), and an order that alternates between the two nodes never empties either
- a solvable start with \(n-1\) occupied nodes, \(n \ge 6\): every node is at distance at least \(\lfloor n/2 \rfloor - 1\) from some robot
- under round robin a robot moves at most one edge per epoch
- the paper argues with the fully occupied ring (Section V), which can be gathered only when it starts with one robot per node
Results, in order of publication
Introductory and current best: at most \(n-3\) epochs (Theorem V.1); no earlier round-robin result on rings was found. Read in the arXiv version (v2).
Open questions
Which sequential schedulers between round robin and an arbitrary sequential scheduler still allow gathering on rings without multiplicity detection? Navarra & Piselli 2025 ask about other sequential schedulers; on graphs that are not vertex-transitive, a new order in every epoch suffices Cicerone et al. 2025d.
Notes
Navarra and Piselli build the algorithm from tasks that a robot recognises in its snapshot: first form two groups of consecutive occupied nodes separated by one empty node on one side and by at least two on the other; that empty node becomes the gathering node; then shrink the two groups onto its two neighbours and move the robots onto it. Round robin makes the last step safe: once the gathering node is fixed, every robot is activated once before any robot is activated again Navarra & Piselli 2025. The same algorithm solves the setting with one robot per node at the start. Checked against the full text of Navarra & Piselli 2025 (arXiv v2).
What carries over from neighbouring settings
Read off the order of assumptions, not checked case by case: results may carry extra assumptions (shown on their pages), and asynchronous time is measured in epochs.
Algorithms from weaker settings work here
Lower bounds from stronger settings hold here
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.