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.
Unoriented grids
verifiedA \(\sqrt n \times \sqrt n\) anonymous grid without a consistent compass; the diameter gives an \(\Omega(\sqrt k)\) bound, and whether local communication reaches it for small \(k\) is open here, while on oriented grids it does.
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.
- Topology: grid
- \(G\) is a \(\sqrt n\times\sqrt n\) grid graph; whether ports are globally consistent (oriented) is stated per result.
- 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
The graph is a \(\sqrt n\times\sqrt n\) grid with \(\Delta = 4\), and the ports at each node are labelled arbitrarily: an agent has no consistent compass (an unoriented grid). Grids with consistent North, East, South and West ports are the setting Oriented grids.
What is known
- \(k\) agents on one node: a grid ball of radius \(r\) holds \(O(r^2)\) nodes
- any algorithm
- holds on oriented and unoriented grids: the argument does not use port labels
- 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
Introductory and current best for square grids with local communication; optimal in both measures when \(k = \Omega(n)\). Placed on unoriented grids following the arXiv text, which says the agents have no consistent compass; later papers call the setting oriented (see notes). With global communication: \(O(\sqrt k)\) rounds and \(O(\log k)\) bits for every \(k\), as reported by Banerjee et al. 2024 and Kumar et al. 2026a; that result is not in the arXiv version.
The first paper to state an unoriented grid explicitly (its Theorem 6); no knowledge of \(k\), and the authors note the algorithm can be adapted to unknown \(n\). If Kshemkalyani et al. 2020c assumes an oriented grid, this is the best result on unoriented grids. Crash-tolerant versions are under the crash-fault branch.
No knowledge of \(n\); the agents compute \(\sqrt n\) themselves.
Open questions
Can \(k \le n\) agents disperse on an unoriented grid in \(O(\sqrt k)\) rounds with local communication? On oriented grids \(O(\sqrt k)\) rounds are reached with local communication Kumar et al. 2026a (preprint), and with global communication by Kshemkalyani et al. 2020c (as reported); asked in Banerjee et al. 2025, and for unoriented grids in Kumar et al. 2026a.
A lower bound in terms of \(k\) for \(k = o(\sqrt n)\) with \(O(\log n)\) memory on unoriented grids Banerjee et al. 2024.
Unoriented grids with no knowledge of \(n\) and with faults, matching the fault-free bounds Banerjee et al. 2024.
Notes
With global communication \(O(\sqrt k)\) rounds were known on grids, against \(O(\min(k,\sqrt n))\) with local communication Kshemkalyani et al. 2020c. On oriented grids Kumar, Molla, Pattanayak and Pramanick reach \(O(\sqrt k)\) rounds with local communication Kumar et al. 2026a (preprint), so there global communication is no longer known to help; on unoriented grids the question is open. Orientation of Kshemkalyani et al. 2020c. The arXiv version (1812.05352v3) says "robots do not have access to a consistent compass to determine which direction to follow to reach boundary nodes", and its port labels at different nodes are uncorrelated; the result is placed here on that text. Banerjee, Kumar and Molla Banerjee et al. 2024 Banerjee et al. 2025 and Kumar et al. Kumar et al. 2026a describe the same setting as an oriented ("planar") grid. The WALCOM 2020 text was not checked. If it assumes an oriented grid, the result belongs to Oriented grids, where Kumar et al. 2026a supersedes it, and the best result here is \(O(\sqrt n)\) rounds with \(O(\log n)\) bits Banerjee et al. 2024. Rectangular \(x\times y\) grids with \(x, y\) known: \(O(\min(k, \max(x,y)))\) rounds with \(\Theta(\log k)\) bits (arXiv version of Kshemkalyani et al. 2020c).
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.