Dispersion
Spread \(k \le n\) agents over the nodes of an \(n\)-node anonymous graph so that no node hosts more than one agent, as fast as possible and with as little memory per agent as possible.
Problem statement and measuresexpand
Given a connected graph \(G\) with \(n\) nodes and \(m\) edges, and \(k \le n\) agents placed on the nodes of \(G\) in any initial configuration (the node of each agent; several agents may share a node), the agents must reach a configuration in which every node hosts at most one agent, and stay there.
Time is the number of rounds (synchronous) or epochs (asynchronous; an epoch is an interval in which every agent completes at least one full Communicate–Compute–Move step, not necessarily the shortest one) until the dispersed configuration is reached; where a result also makes every agent terminate explicitly, the notes say so. Memory is the number of bits of persistent memory each agent needs, counting its \(O(\log k)\)-bit identifier. Unless a variant or a result says otherwise, agents know nothing about \(n\), \(m\), \(k\), \(\Delta\) or \(D\).
Dispersion is the natural "one agent per node" problem: it is equivalent to leaving one agent at every node of a depth-first search (DFS) tree of \(k\) nodes, which is why depth-first search bounds such as \(\min(m, k\Delta)\) appear throughout, and it is a building block for exploration, leader election and self-deployment of agents.
Measures: Time, rounds in the synchronous model, epochs in the asynchronous model, until dispersion is reached; Memory, bits of persistent memory per agent, including its identifier.
Dynamic rings
verifiedA ring from which the adversary removes at most one edge per round (or permutes the nodes); solvable without communication if agents can see the whole ring.
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.
- Number of agents: \(k \le n\)
- The number of agents satisfies \(1\le k\le n\).
- Identifiers: distinct IDs (eponymous)
- Distinct identifiers (eponymous agents): the label function \(\mathrm{id}:\{1,\dots,k\}\to\{1,\dots,L\}\) is injective; usually \(L=k^{O(1)}\), so a label takes \(O(\log k)\) bits.
- Randomness: deterministic
- The next state and move of an agent are a function of its current state and what it observes.
- Topology: ring
- \(G\) is a cycle \(C_n\) (every node of degree 2), or a path when stated.
- Grid orientation: unoriented
- Port labels carry no global meaning: at every node \(v\) the \(\delta_v\) incident edges get the labels \(1,\dots,\delta_v\) in an arbitrary order, chosen independently at each node, so an agent that enters \(v\) cannot tell from the labels which port continues in the same row or column. This is the default on every graph; on a grid it is called an unoriented grid.
- Faults: no faults
- All agents follow the algorithm forever.
- Communication: local communication
- Agents at the same node at the same time can read each other's entire memory (face-to-face communication). Agents crossing on an edge do not meet.
- Timing: synchronous
- Time proceeds in rounds \(t=1,2,\dots\); in every round every agent communicates, computes and moves (at most one edge) simultaneously.
- Node memory: no whiteboards
- Nodes have no storage: no information can be left at a node except by an agent staying there.
- Node identifiers: anonymous nodes
- Nodes have no identifiers; an agent at \(v\) sees only \(\deg(v)\) and the port numbers \(1,\dots,\deg(v)\), which are assigned locally and independently at each endpoint of an edge.
- Initial configuration: any start
- Agents start at arbitrary nodes; \(\ell\le k\) nodes are initially occupied, possibly with several agents each.
Statement for this variant
Two kinds of dynamism are studied: 1-interval connectivity (at most one edge missing per round) and vertex permutation (the adversary reorders the nodes every round, keeping a ring). Visibility is a parameter: with full visibility an agent sees which nodes of the ring are empty, single or multiply occupied.
What is known
- rooted configuration on an \(n\)-node ring, static or 1-interval connected
- \(k = n\)
Results, in order of publication
Introductory and current best. \(O(n)\) rounds under vertex permutation, under 1-interval connectivity, and under both. Without chirality: \(O(n)\) for rooted configurations and for odd \(n\), \(O(1)\) for \(n = 4\). The algorithms are essentially memoryless. Without any visibility the problem is impossible (vertex permutation, \(n \ge 3\); 1-interval connectivity, \(n \ge 2\)).
Distance-\(k\)-dispersion on a 1-interval connected ring with local communication; \(k = 1\) is dispersion. Impossible under a semi-synchronous scheduler if the initial configuration has a multiplicity node. Memory not recorded here.
Arbitrary initial configurations without chirality; partially answers the even-ring question of Agarwalla et al. 2018.
Open questions
Visibility strictly between none and full: how much must an agent see of a dynamic ring for dispersion to be possible? Agarwalla et al. 2018
Achiral agents on even rings of size at least 6 under vertex permutation and 1-interval connectivity: is \(O(n)\) time possible from arbitrary configurations? Agarwalla et al. 2018; \(O(\ell n)\) is known without vertex permutation Mondal et al. 2025b.
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.