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.
Arbitrary graph, arbitrary initial configuration
standard settingverifiedThe standard setting: \(k \le n\) agents with unique identifiers, anywhere on an arbitrary anonymous graph, synchronous rounds, local communication, no faults, no knowledge of the graph.
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.
- 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.
- 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.
- Topology: any topology
- \(G\) is any connected graph in the class allowed by the other axes.
- Initial configuration: any start
- Agents start at arbitrary nodes; \(\ell\le k\) nodes are initially occupied, possibly with several agents each.
What is known
- worst case over inputs: a path with all \(k\) agents on one endpoint
- one edge per round
- holds for randomized algorithms, unbounded memory and global communication
- deterministic
- all agents have the same memory bound
- an initial configuration with co-located agents (rooted suffices)
- memory counts the identifier
Results, in order of publication
Also \(O(m)\) time with \(O(n\log n)\) bits. Introduces the problem and the memory–time trade-off view.
First treatment of \(k \le n\). Also \(O((m-n)k)\) time with \(O(\log k + \log\Delta)\) bits.
Parallel DFS traversals merged over \(O(\log \ell)\) passes (\(\ell\) = number of initially occupied nodes, so \(\log\ell \le \log k\)). Without knowing \(m\): \(O(k\Delta\log k)\) time with \(O(\log(k+\Delta))\) bits.
Same time as Kshemkalyani et al. 2019 with no knowledge of \(m\), \(k\) or \(\Delta\).
Removes the \(\log\ell\) factor; matches single-source DFS. Optimal in time and memory on constant-degree graphs. Holds in the asynchronous model too.
First bound independent of \(m\) and \(\Delta\): \(O(k\log^2 k)\). Terminating all agents simultaneously needs upper bounds on \(k\) and on the number of edges among any \(k\) nodes.
Time-optimal. Settled agents oscillate between their node and a neighbour so that the DFS head can test whether a neighbour is occupied in \(O(1)\) rounds; multiple DFS traversals are merged without the \(\log\) factors.
Open questions
Can the memory be reduced to \(O(\log k)\) bits, independent of \(\Delta\), while keeping \(O(k)\) time? Equivalently, is there an \(\Omega(\log\Delta)\) memory lower bound for deterministic agents with identifiers? The bound \(\Omega(\log(k+\Delta))\) is quoted in several papers but only the \(\log k\) term is argued.
Can all agents terminate explicitly in \(O(k)\) rounds without any knowledge of \(k\), \(m\) or \(\Delta\)? Sudo et al. 2024 terminates the rooted case in \(O(k)\) extra rounds but needs global upper bounds in the general case; Kshemkalyani et al. 2025 does not address termination detection for arbitrary initial configurations.
Ongoing dispersion Kshemkalyani & Ali 2019: agents that have settled must periodically leave (for example to recharge) and the configuration must be re-dispersed; no bounds beyond the original proposal are known.
Notes
Progression. Augustine & Moses Jr. 2018 posed the problem for \(k = n\) with \(O(mn)\) time and \(O(\log n)\) bits, or \(O(m)\) time with \(O(n\log n)\) bits, and asked whether \(o(m)\) time was possible. Kshemkalyani & Ali 2019 allowed \(k \le n\), gave \(O(m)\) time with \(O(k\log\Delta)\) bits and proved the \(\Omega(k)\) time bound that every later paper is measured against. Kshemkalyani et al. 2019 reached \(O(\min(m,k\Delta)\log k)\) time with logarithmic memory but needed \(m\), \(\Delta\) and \(k\); Shintaku et al. 2020 removed that knowledge; Kshemkalyani & Sharma 2021 removed the \(\log\) factor and reached the DFS bound \(O(\min(m,k\Delta))\), optimal for constant degree. The DFS barrier was broken by Sudo et al. 2024 with \(O(k\log^2 k)\), and Kshemkalyani et al. 2025 closed the time question with \(O(k)\).
What the DFS barrier was. A DFS head arriving at a node \(v\) cannot tell which neighbours already hold an agent without visiting them, which costs \(\Theta(\deg(v))\) rounds per node and \(\Theta(\min(m,k\Delta))\) in total. The near-linear and linear algorithms avoid this by letting settled agents advertise themselves at neighbours (Sudo et al. 2024: time slots; Kshemkalyani et al. 2025: oscillation), or in the asynchronous case by exploiting the port-one tree structure (Pattanayak et al. 2025).
Knowledge. Where a result needs knowledge of a parameter it is listed on the result. The 2025 linear-time algorithms do not state any parameter knowledge explicitly; their descriptions use \(k\) (for example, to select \(\lceil k/3\rceil\) seekers), so treat "no knowledge" for them as unconfirmed.
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
Branches from here
Trees
Rooted initial configuration
Rings and paths
Grids
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.