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.
Asynchronous agents
verifiedEach agent's communicate–compute–move step takes finite but unbounded time; time is counted in epochs, intervals in which every agent completes at least one step.
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: asynchronous
- Each agent's Communicate–Compute–Move steps take finite but unbounded, adversarially chosen time. Time is measured in epochs. An epoch is an interval of time in which every agent completes at least one full Communicate–Compute–Move step; it need not be the shortest such interval. Time is counted by dividing the execution into consecutive epochs, and a bound of \(X\) epochs holds for every such division.
- 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.
Statement for this variant
Same task; an adversarial scheduler activates agents at arbitrary speeds. An epoch is an interval of time in which every agent performs at least one full step; it need not be the shortest one, and bounds hold for every division of the execution into consecutive epochs. Settled agents must typically stay active, because an agent that stops cannot be told that it is needed.
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
- counted in epochs
- 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
Three asynchronous algorithms; the only terminating one uses \(O(D\log\Delta)\) bits and \(O(\Delta^D)\) time. Kshemkalyani 2025 is the journal treatment: \(O(\min(m,k\Delta))\) time with \(O(k\log\Delta)\) bits and no parameter knowledge.
Same bounds as its synchronous algorithm, in epochs.
First near-linear asynchronous bound, for rooted and arbitrary configurations.
Time-optimal, rooted and arbitrary configurations. Uses the port-one tree: following port 1 from every node defines a structure that lets an agent check a neighbour's status in \(O(1)\) epochs without timing assumptions.
Open questions
Can an asynchronous algorithm let every agent terminate in polynomial time without knowledge of the graph? The only terminating asynchronous algorithm known uses \(O(\Delta^{\min(D,k)+1})\) time Kshemkalyani 2025; the linear-time algorithms keep settled agents active.
Semi-synchronous schedulers sit between the two models; no separation or dedicated bound is known.
Notes
The asynchronous time gap closed in two steps in 2025: \(O(k\log k)\) Kshemkalyani et al. 2025, then \(O(k)\) Pattanayak et al. 2025. Sudo et al. 2024's rooted algorithms also work under any fair scheduler with atomic moves, but its general-configuration algorithm needs full synchrony.
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
Branches from here
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.