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.
Oriented grids
verifiedA \(\sqrt n \times \sqrt n\) grid with consistent North, East, South and West ports: \(\Theta(\sqrt k)\) rounds and \(\Theta(\log k)\) bits with local communication, by a 2026 preprint.
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: oriented
- The graph is a grid with nodes \((x,y)\), and every node labels its ports North, East, South and West consistently: the port North of \((x,y)\) leads to \((x,y+1)\), East to \((x+1,y)\), South to \((x,y-1)\) and West to \((x-1,y)\), whenever that neighbour exists. The same direction carries the same label at every node, so an agent can keep moving along a row or column; a boundary node is recognised by its missing ports.
- 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\) whose ports are labelled North, East, South and West consistently at every node (an oriented grid); a boundary node is recognised by its missing ports. Otherwise as on unoriented grids: \(k \le n\) agents with unique identifiers start in an arbitrary configuration, communicate locally and move synchronously.
What is known
- \(k\) agents on one node: a grid ball of radius \(r\) holds at most \(2r^2+2r+1\) nodes
- any algorithm
- holds on oriented grids, hence also on unoriented ones
- 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
Preprint, not peer reviewed. Spread–Reverse–Collect: each group of \(m\) co-located agents sweeps a square of side \(2\lceil\sqrt m\rceil\) from its own position and reflects it at the boundary; groups merge by label priority and at least double in size from level to level. Any initial configuration, no knowledge of \(n\), \(k\) or the diameter, no detection of agents crossing on an edge; the authors state it runs unchanged on the infinite oriented grid. Optimal in both measures for every \(k \le n\); matches with local communication the global-communication bound of Kshemkalyani et al. 2020c.
Open questions
Rectangular \(W \times H\) oriented grids with \(W \le H\): from a corner at most \(W(t+1)\) nodes are reachable in \(t\) rounds, so \(\lceil k/W\rceil - 1\) rounds are needed; an algorithm matching a bound that depends on \(W\) and \(H\), with local communication and no knowledge of \(W\) and \(H\), is open Kumar et al. 2026a.
\(O(\sqrt k)\) rounds on oriented grids with asynchronous agents, or on the oriented torus Kumar et al. 2026a.
Dispersion in \(O(\sqrt k)\) rounds on oriented grids with explicit termination: every agent knows when it may stop (see notes).
Notes
Kshemkalyani, Molla and Sharma left a gap between \(O(\min(k,\sqrt n))\) rounds with local communication and \(O(\sqrt k)\) rounds with global communication Kshemkalyani et al. 2020c; Banerjee, Kumar and Molla asked again whether local communication suffices Banerjee et al. 2025. Kumar, Molla, Pattanayak and Pramanick answer it on oriented grids: \(O(\sqrt k)\) rounds and \(O(\log k)\) bits Kumar et al. 2026a (arXiv preprint, v1, October 2026, not peer reviewed). Earlier grid algorithms gather the agents at the boundary or at a corner and spread from there; Spread–Reverse–Collect starts each sweep where its agents are and reflects it at the boundary, so no knowledge of \(n\) is needed. Kshemkalyani et al. 2020c is placed on unoriented grids (see that setting for the dispute about its orientation); its algorithm carries over here, and so do the crash-tolerant \(O(\sqrt n)\) algorithms for oriented grids Banerjee et al. 2024 Banerjee et al. 2025. Not independently checked. The model, theorem statements and algorithm were read in full, but the proofs were not checked step by step, and three points need care. (1) Theorem 2 bounds the number of rounds in which each agent is active and concludes \(T(k) = O(\sqrt k)\); a settled agent can be recruited again by a later Collect, so the step from active rounds to total time needs an argument along the chain of recruiters, which is not written out. (2) The proof of Lemma 7 assumes that same-labelled settled agents stay in place during the next Spread, while Section 3.5 lets a Collect un-settle every settled agent of equal or lower label that it reaches. (3) Theorem 3 says every agent terminates, but the paper does not say how a settled agent, which may be recruited again, knows that it may stop, and on the infinite grid no whole-grid sweep happens; the result is read here as reaching a dispersed configuration that no agent leaves afterwards. The infinite-grid claim (Section 5) has no separate proof.
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.