Uniform deployment on graphs
Spread \(k \le n\) agents that start on distinct nodes of an \(n\)-node graph so that they end evenly spread, on a ring every two consecutive agents at distance \(\lfloor n/k\rfloor\) or \(\lceil n/k\rceil\), and stop.
Problem statement and measuresexpand
\(k\) agents start on distinct nodes of an anonymous graph \(G\) with \(n \ge k\) nodes and must reach a configuration in which they are evenly spread, and stop there. On a ring, evenly spread means that every two agents that are consecutive along the ring are at distance \(\lfloor n/k\rfloor\) or \(\lceil n/k\rceil\); on other graphs the target is stated with each result (one side of a complete bipartite graph, or every node at chosen depths of a perfect tree). Almost uniform deployment asks this of all agents but one. Measures: time in rounds (ideal time units for asynchronous agents), the total number of moves, a move being the traversal of one edge by one agent, and memory in bits per agent.
Measures: Time, rounds (ideal time units for asynchronous agents) until the agents are evenly spread and have stopped; Moves, total number of edge traversals by all agents; Memory, bits of memory per agent.
Dynamic rings, all agents but one
verifiedIf one agent may end out of place, synchronous agents that know \(n\) spread evenly on a 1-interval connected ring in \(O(n\log k)\) rounds with \(O(kn)\) moves, which is optimal in moves.
Assumed (added on the last edge are outlined)
Not assumed
Formal definitions of this setting
- Graph dynamics: connected every round
- \(\mathcal G=(G_t)_{t\ge0}\) is 1-interval connected if every snapshot \(G_t=(V,E_t)\) is connected. More generally it is \(T\)-interval connected if for every \(t\) the graph \(\bigl(V,\bigcap_{i=t}^{t+T-1}E_i\bigr)\) is connected.
- Edge direction: undirected
- \(G=(V,E)\) with \(E\subseteq\binom V2\); every edge can be traversed in both directions.
- Identifiers: anonymous
- All agents run the same deterministic algorithm on the same input; no agent has a label. Formally the label function is constant: \(\mathrm{id}(a)=\mathrm{id}(b)\) for all agents \(a,b\).
- Randomness: deterministic
- The next state and move of an agent are a function of its current state and what it observes.
- Faults: no faults
- All agents follow the algorithm forever.
- Communication: no communication
- Agents exchange no messages; an agent at \(v\) observes only the number of agents at \(v\) (and, where stated, whether that number changed).
- Timing: synchronous
- Time proceeds in rounds \(t=1,2,\dots\); in every round every agent communicates, computes and moves (at most one edge) simultaneously.
- Topology: ring
- \(G\) is a cycle \(C_n\) (every node of degree 2), or a path when stated.
- Initial configuration: dispersed start
- Every initially occupied node holds exactly one agent (\(\ell=k\)). Also called a scattered start, notably in black hole search.
- Goal: all but one
- All agents but one end evenly spread and stop; the remaining agent may stop on any node.
What is known
- when \(k \le pn\) for a constant \(p < 1\) (Theorem 3)
- already on a static ring, from a start with all agents close together, as in Shibata et al. 2018
Results, in order of publication
Introductory and current best (Theorem 4, Section 3): each agent leaves its token at its start node and moves forward for \(3n\) rounds. Either it goes once around the ring and reads the distances between tokens, from which all agents pick the same base node (one per period if the start is periodic), or missing edges have piled all agents on one node, which they detect by counting. Each agent then moves to its target relative to the base node; one agent may stay blocked, which almost uniform deployment allows.
Theorem 5, Section 4: knowing \(k\) instead of \(n\) costs \(O(n^2)\) rounds and moves; knowing \(n\) and knowing \(k\) are equivalent on static rings but not here.
Open questions
Is \(O(n)\) time possible on a 1-interval connected ring? Shibata et al. 2022a reach \(O(n\log k)\) against \(\Omega(n)\) and leave the lower bound on time to future work.
Can almost uniform deployment be reached without chirality or without strong multiplicity detection Shibata et al. 2022a?
Notes
Shibata, Sudo, Nakamura and Kim assume eight things (Section 1.3): anonymous agents, knowledge of \(k\) or \(n\), chirality, strong multiplicity detection, no messages, one token per agent, distinct start nodes and synchronous rounds, and show that anonymity, no messages, tokens and distinct starts are the weakest choices. Knowing \(n\) and knowing \(k\) are not equivalent here, unlike on static rings. Checked against the full text of Shibata et al. 2022a.
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
No catalogued stronger setting.
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.