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.
Complete graphs, FSYNC, strong multiplicity detection
verifiedOn a complete graph, FSYNC robots that start on distinct nodes and see how many robots each node holds gather exactly when the least prime factor of \(k\) exceeds the number \(n-k\) of empty nodes, in \(O(\log k)\) epochs.
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: complete graph
- \(K_n\): every two nodes are neighbours.
- Multiplicity detection: strong detection
- A snapshot gives the number of robots on every node.
- 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: FSYNC
- FSYNC: in every round every robot executes one atomic Look–Compute–Move cycle.
- Activation order: any order
- The adversary chooses which robots to activate, subject only to the scheduler's fairness.
What is known
- every start with \(k = n\), and every start in which the least prime factor \(p\) of \(k\) is at most \(n-k\) (Theorems 1 and 10)
- all nodes of a complete graph look alike, so an algorithm must send moving robots to empty nodes (Corollary 3); the adversary sends them to \(p\) empty nodes, \(k/p\) robots on each, and every later move rebuilds such a configuration
- holds even with strong multiplicity detection and FSYNC
- a complete graph with \(F_{\ell+1}\) nodes and \(k = F_\ell\) robots, \(F_\ell\) a Fibonacci number, on distinct nodes (Theorem 16, Corollary 17)
- the adversary keeps the nodes in classes of equivalent nodes, each of Fibonacci size and holding equal towers, and the smallest class loses at most two Fibonacci indices per round
- by Theorem 10 this start is solvable only when \(F_\ell\) is prime
Results, in order of publication
Introductory and current best (Theorems 10 and 11): in the first round every robot moves to an empty node; from then on, the robots outside the smallest class of nodes holding equal towers (the class of larger towers on a tie) move into it. As \(p > n-k\), two classes remain until all robots are on one node, and the adversary can do no better than halve the class each round, so \(O(\log(n-k)) = O(\log k)\) rounds.
Open questions
Does every algorithm need \(\Omega(\log k)\) epochs on complete graphs for infinitely many \(k\), without assuming infinitely many Fibonacci primes? The lower bound of Cicerone et al. 2021b uses \(k = F_\ell\) robots and \(F_{\ell-1}\) empty nodes, solvable only when \(F_\ell\) is prime.
Notes
Cicerone, Di Stefano and Navarra also give a condition for general graphs: a start of \(k\) SSYNC robots with strong multiplicity detection is solvable if the graph has a minimal recognizable subgraph \(H\) (an induced subgraph that every automorphism maps onto itself, minimal with this property) whose number of connected components and their size are both smaller than the least prime factor of \(k\) (Theorem 9). On complete bipartite graphs with \(k_1\) and \(k_2\) robots on the two sides, they characterise the solvable starts for FSYNC robots (Theorem 13; for instance, every start with both sides occupied and \(k_1\), \(k_2\) coprime) and gather in \(O(\log k + \delta(k))\) rounds, \(\delta(k)\) the number of divisors of \(k\) (Corollary 14). Diameter is the general lower bound on time. Checked against the full text of Cicerone et al. 2021b (journal pre-proof).
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.