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, SSYNC, no multiplicity detection
verifiedWithout multiplicity detection, \(k \ge 2\) robots cannot gather on any ring when the scheduler may activate several robots in the same round.
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: dispersed start
- Every initially occupied node holds exactly one agent (\(\ell=k\)). Also called a scattered start, notably in black hole search.
- Scheduler: SSYNC
- SSYNC: time is divided into rounds; in each round a fair adversary chooses a non-empty subset of robots, which execute one atomic Look–Compute–Move cycle together.
- Activation order: any order
- The adversary chooses which robots to activate, subject only to the scheduler's fairness.
What is known
- every \(k \ge 2\) and every ring, from some start with one robot per node (Proposition 2.1)
- two robots at odd distance activated together stay at odd distance; with more robots, the adversary lets one robot create the first tower alone, after which the snapshots are those of \(k-1\) robots, and induction applies
- stated for ASYNC; the adversary's schedules are semi-synchronous, so the proof holds under SSYNC (not stated in the paper)
Results, in order of publication
No result recorded yet.
Open questions
None recorded for this variant.
Notes
Proposition 2.1 is why Klasing et al. 2008 assume multiplicity detection. Round robin avoids the impossibility for most starts Navarra & Piselli 2025. Checked against the model section and the proof of Proposition 2.1 in Klasing et al. 2008.
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
No catalogued weaker setting.
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.