Mobility Matters
Home›Mobile agents on graphs›Exploration›Collaborative exploration›Dispersion

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 measurescollapse
1212312311211122334455Start: k = 5 agents on one node; ports numbered at each nodeSmallest ID settles; the rest take the next untried portNo untried port: back through the parent portNode already occupied (agent 1 settled here)Back by the same port; try the next port thereFinal: agent 5 settles; at most one agent per node
Dispersion from a rooted start, by the depth-first search of Augustine & Moses Jr. 2018 and Kshemkalyani & Ali 2019: \(k = 5\) agents start on one node of an anonymous port-labelled graph and move as one group. At each new node the agent with the smallest ID settles (green) and records its parent port; the group tries the ports in order, goes back when a node is occupied, and returns through the parent port when no port is left. One frame per round; the green edges form the depth-first tree.

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.

A first look

the basic problem, a simple algorithm and why some things cannot be done, for a newcomer

Think of \(k\) electric cars arriving in a town where each charging point can serve only one car, and no car has a map. We model the town as a graph: charging points are nodes, roads between them are edges, and each car is an agent. The graph is connected and has \(n\) nodes and \(m\) edges; the nodes are anonymous (they have no names and nothing can be written on them). The \(k \le n\) agents have distinct identifiers (ID numbers) and start on nodes, several possibly on the same node. Time passes in synchronous rounds: in each round, agents at the same node can read each other's memory (local communication), and then each agent may move along one edge, choosing it by its port (the local number of that edge at the node). The agents know nothing about the graph, not even \(n\). They must reach a configuration (the node of each agent) in which every node holds at most one agent; we measure the number of rounds and the number of bits of memory each agent needs.

1AlgorithmDepth-first search with a settled agent per node Rooted initial configuration → Augustine & Moses Jr. 2018

When all \(k\) agents start on one node (the rooted case), the agents move as one group and run a depth-first search (DFS: go forward through an untried port while there is one, go back otherwise), using agents that stay behind on nodes (settled agents) as markers, as in Augustine & Moses Jr. 2018 and Kshemkalyani & Ali 2019.

  1. At the start node, the agent with the smallest ID settles: it stays there for good and remembers by which port the group arrived (its parent port; none at the start).
  2. The rest of the group leaves by the next port not yet tried at this node.
  3. If the node the group reaches already has a settled agent, it has been visited: the group goes back by the port it came in and tries the next port there.
  4. If the node is empty, the smallest ID in the group settles there and records the parent port; go to step 2.
  5. When every port of a node has been tried, the group goes back through that node's parent port, which the settled agent tells it.
  6. The group shrinks by one at each new node, and the procedure ends when the last agent settles.
Why it works and what it costs. This is a depth-first search in which the settled agents replace the "visited" marks that anonymous nodes cannot hold. Each edge is tried at most once from each of its two endpoints, and each try costs two moves (there and back) or turns into a tree edge, so the time is \(O(m)\) rounds; tries happen only at the at most \(k\) nodes that receive an agent, each with at most \(\Delta\) ports, which gives \(O(\min(m, k\Delta))\), where \(\Delta\) is the maximum degree. A settled agent remembers its ID and a few port numbers, \(O(\log(k+\Delta))\) bits. The current best is \(O(k)\) rounds with \(O(\log(k+\Delta))\) bits, from any start Kshemkalyani et al. 2025b: it gets rid of the cost of checking every port, which held the field at \(O(\min(m,k\Delta))\) until Sudo et al. 2026a.

Why it matters. Using the agents themselves as markers is the idea every dispersion algorithm builds on, and it ties dispersion to collaborative exploration with anonymous nodes.

2Lower boundDistance: Omega(k) rounds Arbitrary graph, arbitrary initial configuration → Kshemkalyani & Ali 2019

Put all \(k\) agents on one end of a path (nodes in a row, each joined by an edge to the next). In the end the \(k\) agents must stand on \(k\) different nodes of the path, so one of them stands at least \(k-1\) edges from the end where they all started. An agent crosses at most one edge per round.

Why it holds. So some agent needs at least \(k-1\) rounds, whatever the algorithm: \(\Omega(k)\) Kshemkalyani & Ali 2019. The argument uses only distance, so it holds even for randomised algorithms, unlimited memory and global communication. The \(O(k)\) algorithm of Kshemkalyani et al. 2025b matches it, so the time question is settled up to a constant factor.

Why it matters. It fixed the target: after it, every dispersion algorithm was measured by how far it is from \(k\) rounds.

3Lower boundSymmetry: Omega(log k) bits Arbitrary graph, arbitrary initial configuration → Augustine & Moses Jr. 2018

Suppose all agents run the same deterministic algorithm with the same amount of memory, and put them all on one node. If two of them start with exactly the same memory contents, they see the same things, make the same decisions and take the same ports in every round, so they stay together forever and dispersion fails. Hence the \(k\) agents on that node need \(k\) different memory contents at the start.

Why it holds. With \(b\) bits there are \(2^b\) possible memory contents, so \(2^b \ge k\), that is \(b \ge \log k\) Augustine & Moses Jr. 2018. This is why the bound counts the identifier: the ID is exactly what makes the memories differ. The best algorithms use \(O(\log(k+\Delta))\) bits, so memory is optimal whenever \(\Delta\) is at most polynomial in \(k\); whether the \(\log\Delta\) term is needed has no published proof for agents with identifiers.

Why it matters. It is the simplest instance of symmetry breaking, the obstacle behind the anonymous-agent results in dispersion, rendezvous and gathering.

What is known

The best upper bound against the best lower bound in each catalogued setting. Open a setting for its results, proofs and notes, or see the progress map with the branch points.

tight near-optimal polynomial gap unknown impossible· one row per catalogued setting, in tree order; each cell: best upper bound vs lower bound, and what forces the lower bound
Setting
Time
Memory
Asynchronous agents
Each 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.
tight \(O(k)\) vs \(\Omega(k)\) distance
near-optimal \(O(\log(k+\Delta))\) vs \(\Omega(\log k)\) symmetry breaking
Arbitrary graph, arbitrary initial configuration standard
The 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.
tight \(O(k)\) vs \(\Omega(k)\) distance
near-optimal \(O(\log(k+\Delta))\) vs \(\Omega(\log k)\) symmetry breaking
Rooted initial configuration
All \(k\) agents start on the same node, so a single DFS traversal that drops one agent per new node solves the problem; the question is how fast and with how little memory.
tight \(O(k)\) vs \(\Omega(k)\) distance
near-optimal \(O(\log(k+\Delta))\) vs \(\Omega(\log k)\) symmetry breaking
Global communication
Any agent can read the state of any other agent at any time, but still does not know the graph or where the others are.
tight \(O(k)\) vs \(\Omega(k)\) distance
near-optimal \(O(\log(k+\Delta))\) vs \(\Omega(\log k)\) symmetry breaking
Silent agents (no communication)
Agents cannot exchange any information; at its node an agent only learns whether it is alone and whether the number of agents there went up or down since the last round.
polynomial gap \(O(k\log L + k^2\log\Delta)\) vs \(\Omega(k + \log L)\) timing is the only channel
tight \(O(\log L + \log\Delta)\) vs \(\Omega(\log L + \log\Delta)\) encoding identifier and ports
Oriented grids
A \(\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.
tight \(O(\sqrt k)\) vs \(\Omega(\sqrt k)\) distance
tight \(O(\log k)\) vs \(\Omega(\log k)\) symmetry breaking
Crash faults on oriented grids
On oriented grids crashes are free for \(k = \Omega(n)\): the fault-free \(\Theta(\sqrt n)\) bound survives any number of crashes.
polynomial gap \(O(\sqrt n)\) vs \(\Omega(\sqrt k)\) distance
tight \(O(\log n)\) vs \(\Omega(\log k)\) symmetry breaking
Weak Byzantine agents on oriented grids
Time-optimal \(O(\sqrt n)\) rounds on oriented grids for any number of weak Byzantine agents, at the price of \(O(n\log n)\) bits.
tight \(O(\sqrt n)\) vs \(\Omega(\sqrt n)\) distance
polynomial gap \(O(n\log n)\) vs \(\Omega(\log n)\) symmetry breaking
Unoriented grids
A \(\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.
polynomial gap \(O(\min(k, \sqrt n))\) vs \(\Omega(\sqrt k)\) distance
tight \(O(\log k)\) vs \(\Omega(\log k)\) symmetry breaking
Crash faults on unoriented grids
Without a consistent compass the only crash-tolerant grid algorithm takes \(O(\sqrt n\log n)\) rounds and \(O(\sqrt n\log n)\) bits, against \(O(\sqrt n)\) rounds and \(O(\log n)\) bits on oriented grids.
polynomial gap \(O(\sqrt n\log n)\) vs \(\Omega(\sqrt k)\) distance
polynomial gap \(O(\sqrt n\log n)\) vs \(\Omega(\log k)\) symmetry breaking
Rings and paths
Degree two everywhere; both measures are settled.
tight \(O(k)\) vs \(\Omega(k)\) distance
tight \(O(\log k)\) vs \(\Omega(\log k)\) symmetry breaking
Silent agents on rings
On an oriented ring, silent agents from arbitrary configurations disperse in optimal \(\Theta(k + \log L)\) rounds.
tight \(O(k + \log L)\) vs \(\Omega(k + \log L)\) timing is the only channel
tight \(O(\log L)\) vs \(\Omega(\log L)\) encoding the identifier
Weak Byzantine agents on rings
Optimal \(O(n)\) time and \(O(\log n)\) bits are possible on rings when fewer than \(n/17\) agents are Byzantine and \(f\) is known.
tight \(O(n)\) vs \(\Omega(n)\) distance
tight \(O(\log n)\) vs \(\Omega(\log n)\) symmetry breaking
Trees
No cycles, so a DFS never needs to test for revisits; the difficulty is spreading agents that start far apart across long branches.
polynomial gap \(O(k)\) vs \(\Omega(D^2)\) collaborative tree exploration
near-optimal \(O(\log(k+\Delta))\) vs \(\Omega(\log k)\) symmetry breaking
Rooted trees
All agents start at one node of a tree; the time is governed by the diameter, as in collaborative tree exploration.
polynomial gap \(O(D^2)\) vs \(\Omega(D^2)\) collaborative tree exploration
tight \(O(\log n)\) vs \(\Omega(\log k)\) symmetry breaking
Crash faults
Up to \(f \le k\) agents may crash at any time; a crashed agent disappears with everything it knew, and the surviving \(k - f\) agents must still end on distinct nodes.
polynomial gap \(O(\min(m, k\Delta))\) vs \(\Omega(k)\) distance
near-optimal \(O(k\log(k+\Delta))\) vs \(\Omega(\log k)\) symmetry breaking
Weak Byzantine agents
Up to \(f\) agents behave arbitrarily and may lie, but cannot fake their identifiers; the non-faulty agents must still settle on distinct nodes and terminate.
polynomial gap \(\tilde O(n^9)\) vs \(\Omega(k)\) distance
unknown — vs \(\Omega(\log k)\) symmetry breaking
Strong Byzantine agents
Byzantine agents can also fake identifiers; polynomial time is known only from a gathered start, or with a trusted shepherd agent.
polynomial gap \(O(X(n) + n^3)\) vs \(\Omega(k)\) distance
unknown — vs —
Anonymous agents with randomness
Agents have no identifiers but private coins. Both axes change together: identical deterministic agents on one node can never behave differently, so randomness is needed to break symmetry.
polynomial gap \(O(k^2)\) vs \(\Omega(k)\) distance
tight \(O(\log\Delta)\) vs \(\Omega(\log\Delta)\) port addressing
More agents than nodes
With \(k > n\) the target is a balanced configuration: at most \(\lceil k/n\rceil\) agents per node. Only randomized anonymous results exist.
unknown \(O(m + k)\) vs —
polynomial gap \(O(\Delta)\) vs \(\Omega(\log\Delta)\) port addressing
Directed graphs
Edges can be traversed in one direction only, so an agent cannot backtrack; the problem is solvable only on strongly connected digraphs and the known time bounds are quadratic in \(k\).
polynomial gap \(O(k^2\Delta_{out})\) vs \(\Omega(k)\) distance
near-optimal \(\Theta(\log(k+\Delta_{out}))\) vs \(\Omega(\log k)\) symmetry breaking
Directed graphs, 1-hop communication
On strongly connected digraphs, agents that also talk to agents on neighbouring nodes disperse in \(O(kD)\) rounds by breadth-first search, at the price of \(O(k\log(k+\Delta_{out}))\) bits.
polynomial gap \(O(kD)\) vs \(\Omega(k)\) distance
polynomial gap \(O(k\log(k+\Delta_{out}))\) vs \(\Omega(\log k)\) symmetry breaking
Dynamic graphs (1-interval connected)
An adversary changes the edge set every round, keeping the graph connected in every round. With only local communication the problem is impossible.
impossible — vs \(\text{impossible}\) adversarial edge changes
impossible — vs \(\text{impossible}\) adversarial edge changes
Dynamic graphs with global communication
Global communication plus 1-neighbourhood knowledge make dispersion solvable on 1-interval connected graphs, and in optimal \(\Theta(k)\) time.
tight \(\Theta(k)\) vs \(\Omega(k)\) adversarial edge changes
tight \(\Theta(\log k)\) vs \(\Omega(\log k)\) symmetry breaking
Dynamic rings
A 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.
tight \(O(n)\) vs \(\Omega(n)\) distance
tight \(O(1)\) vs —

Open questions 55

Asynchronous agents

  1. 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.
  2. Semi-synchronous schedulers sit between the two models; no separation or dedicated bound is known.

Arbitrary graph, arbitrary initial configuration

  1. 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.
  2. Can all agents terminate explicitly in \(O(k)\) rounds without any knowledge of \(k\), \(m\) or \(\Delta\)? Sudo et al. 2026a terminates the rooted case in \(O(k)\) extra rounds but needs global upper bounds in the general case; Kshemkalyani et al. 2025b does not address termination detection for arbitrary initial configurations.
  3. 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.

Rooted initial configuration

  1. Is \(O(k)\) time achievable with \(O(\log k)\) bits? Memory \(O(\log(k+\Delta))\) is needed by every known algorithm to remember a port number.

Global communication

  1. Does global communication buy anything for dispersion? Since \(O(k)\) time with \(O(\log(k+\Delta))\) bits holds with local communication, a separation could only come from memory (\(O(\log k)\) bits), from termination detection, or from the BFS-style question of achieving time close to \(O(D)\)-dependent bounds for small \(D\).
  2. Kshemkalyani et al. 2022 asks for \(O(\min(m,k\Delta))\) time with only \(O(\log(k+\Delta))\) bits in the global model; this is implied by the later local-model result, so the live version of the question is the memory question above.

Silent agents (no communication)

  1. Close the time gap on general graphs: is \(O(k + \log L)\) achievable, as on rings?
  2. Arbitrary (multi-source) initial configurations on general graphs; only rings are solved Das et al. 2026a.
  3. Weaker sensing: agents that only learn whether they are alone and whether the count decreased, and agents that wake up at different times (a 2026 ICDCIT paper by Gorain, Mandal and Sharma treats this; its bounds are not recorded here).

Oriented grids

  1. 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.
  2. \(O(\sqrt k)\) rounds on oriented grids with asynchronous agents, or on the oriented torus Kumar et al. 2026a.
  3. Dispersion in \(O(\sqrt k)\) rounds on oriented grids with explicit termination: every agent knows when it may stop (see notes).

Crash faults on oriented grids

  1. Crash-tolerant dispersion in \(O(\sqrt k)\) rounds on oriented grids for \(k = o(n)\); the fault-free case is solved by Kumar et al. 2026a (preprint), which names fault tolerance as future work.

Weak Byzantine agents on oriented grids

  1. Reduce the memory below \(O(n\log n)\) bits on grids with weak Byzantine agents.
  2. Strong Byzantine agents (able to fake identifiers) on grids Banerjee et al. 2025.
  3. Weak Byzantine agents on unoriented grids, and on oriented grids with \(k = o(n)\) agents in \(O(\sqrt k)\) rounds; fault tolerance is named as future work in Kumar et al. 2026a.

Unoriented grids

  1. 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.
  2. A lower bound in terms of \(k\) for \(k = o(\sqrt n)\) with \(O(\log n)\) memory on unoriented grids Banerjee et al. 2024.
  3. Unoriented grids with no knowledge of \(n\) and with faults, matching the fault-free bounds Banerjee et al. 2024.

Crash faults on unoriented grids

  1. Unoriented grids with crashes: close the gap between \(O(\sqrt n\log n)\) rounds with \(O(\sqrt n\log n)\) bits and the fault-free \(O(\sqrt n)\) rounds with \(O(\log n)\) bits Banerjee et al. 2024.

Rings and paths

  1. Anonymous randomized agents disperse from a rooted ring configuration with \(O(1)\) bits in \(O(n)\) rounds Molla & Moses Jr. 2019. From an arbitrary configuration the known algorithm never terminates; is \(O(1)\)-bit dispersion with termination possible on rings?

Silent agents on rings

  1. Unoriented rings, and rings where agents cannot detect count changes.

Weak Byzantine agents on rings

  1. Keep \(O(n)\) time and \(O(\log n)\) bits while dropping any of: identifiers in \([1,n]\), knowledge of \(f\), the bound \(f \le (n-4)/17\), the follow primitive Molla et al. 2021a.
  2. Asynchronous Byzantine dispersion on rings Molla et al. 2021a.

Trees

  1. Augustine & Moses Jr. 2018 asked for \(o(n)\)-round dispersion on arbitrary trees. Precisely: for \(k = n\) and an arbitrary initial configuration, is there an algorithm whose time is bounded by a function of \(D\) alone, ideally \(O(D^2)\) as in the rooted case? No tree-specific algorithm has appeared since 2018; the linear-time general algorithms give only \(O(n)\).
  2. With global communication, trees admit \(O(D\cdot\max(D,k))\) rounds with \(O(\max(D, \Delta\log k))\) bits (arXiv version of Kshemkalyani et al. 2020b); whether the \(\max(D,k)\) factor can be reduced to \(D\), and whether local communication suffices, is open.

Rooted trees

  1. For \(k < n\) the lower bound \(\Omega(D^2)\) no longer applies (only \(k\) nodes must be reached). Whether \(O(\min(k, D^2))\) time is achievable, and whether it is necessary, has not been addressed.
  2. For \(k=n\) agents rooted on a tree of height \(D\) much larger than \(\sqrt{\log n}\), is \(\Omega(D^2)\) time necessary? The known bound is existential in \(D\) Disser et al. 2020.

Crash faults

  1. Is \(O(k)\) time achievable with crash faults, or does fault tolerance cost a factor of \(\Delta\)? No lower bound beyond the fault-free \(\Omega(k)\) is known, even with \(O(\log(k+\Delta))\) memory Chand et al. 2025a.
  2. Simultaneously \(O(\min(m,k\Delta))\) (or better) time and \(O(\log(k+\Delta))\) memory for arbitrary configurations, without knowledge of \(f\), \(\ell\), \(\Delta\) or \(m\) Chand et al. 2025a Pattanayak et al. 2023.
  3. Crash faults under asynchrony: no result exists.

Weak Byzantine agents

  1. Faster Byzantine dispersion on general graphs: the time is dominated by Byzantine gathering, and the authors ask whether building a map before settling is necessary Molla et al. 2021b.
  2. Tolerating more than \(n/2\) weak Byzantine agents on general graphs (possible only on the restricted class so far) Molla et al. 2021b.
  3. Byzantine dispersion with bounded memory per agent, on trees, with \(k < n\), or under asynchrony: nothing is known Molla et al. 2021a Chand et al. 2025a.

Strong Byzantine agents

  1. Polynomial-time strong-Byzantine dispersion from arbitrary configurations without a trusted agent, and the largest tolerable \(f\).
  2. Asynchronous versions: a slow agent cannot be distinguished from a silent Byzantine one Moses Jr. & Redlich 2024.

Anonymous agents with randomness

  1. Close the gap between \(\Omega(k)\) and \(\Theta(k^2)\) rounds for anonymous agents from a rooted configuration with \(O(\log\Delta)\) bits Das et al. 2023.
  2. Can anonymous randomized agents disperse from an arbitrary configuration and then stop, rather than staying active forever? Molla & Moses Jr. 2019 Das et al. 2023
  3. On rings the memory bound is \(O(1)\); is \(O(1)\)-bit dispersion with termination possible on rings from arbitrary configurations?

More agents than nodes

  1. Deterministic dispersion with \(k > n\) agents with identifiers on static graphs has not been studied: no algorithm and no lower bound beyond \(\Omega(k)\) is recorded in the literature surveyed here. (Related work exists only on dynamic rings and dynamic graphs under the name balanced dispersion.)
  2. Is \(O(k)\) time possible for rooted configurations when \(k > n\), matching the \(k \le n\) case?
  3. Terminating dispersion with \(k > n\) on general rooted graphs with \(O(\log\Delta)\) bits per agent (Open Problem 2 of Molla & Moses Jr. 2019).

Directed graphs

  1. Close the time gaps; in particular \(O((k+f)k\Delta_{out})\) with \(f\) crashes Italiano et al. 2025.
  2. BFS-based dispersion in the local model, without 1-hop communication Italiano et al. 2025.
  3. Dispersion on dynamic directed graphs, and in semi-synchronous and asynchronous settings Italiano et al. 2025.

Directed graphs, 1-hop communication

  1. A BFS-based algorithm with \(O(\log(k+\Delta_{out}))\) bits per agent, as with local communication Italiano et al. 2025.
  2. Does \(O(kD)\) improve to \(O(k + D^2)\) or \(O(k)\) with 1-hop communication?

Dynamic graphs (1-interval connected)

  1. Which combination of communication range and visibility is necessary for dispersion on \(T\)-interval connected graphs with \(T > 1\), where the impossibility proof for \(T = 1\) does not apply? Saxena & Mondal 2025
  2. Dynamic graphs with a bounded number of missing edges per round: Saxena et al. 2026a gives impossibilities on 1-bounded 1-interval connected graphs for several weaker communication and visibility combinations and an \(O(k)\) algorithm with global communication and 1-hop visibility; the local-communication case with few missing edges is not settled.

Dynamic graphs with global communication

  1. Byzantine agents on dynamic graphs Kshemkalyani et al. 2020a.
  2. Memory \(O(\log k)\) instead of \(O(\log\max(k,T))\) on \(T\)-path connected graphs when \(T\) need not be known Saxena & Mondal 2025.

Dynamic rings

  1. 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
  2. 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 the community started looking at

Augustine and Moses Jr. posed dispersion as a study of memory–time trade-offs Augustine & Moses Jr. 2018: the primary aim was to minimise the number of rounds, and then the memory per agent, with \(\Omega(k)\) rounds and \(\Omega(\log k)\) bits as the targets. Most of the later work closes these two gaps under weaker assumptions (arbitrary start, asynchrony, faults, dynamic graphs); the time-optimal \(O(k)\) algorithm with \(O(\log(k+\Delta))\) bits came in 2025 Kshemkalyani et al. 2025b. Its roots are in \(n\)-agent collaborative exploration, which a dispersion with \(k = n\) solves.

Derived from Collaborative exploration

With \(k = n\) agents, a dispersed configuration has an agent on every node, so any dispersion algorithm solves \(n\)-agent collaborative exploration under the same assumptions Augustine & Moses Jr. 2018. Consequently every lower bound for \(n\)-agent exploration is a lower bound for dispersion (this is how the \(\Omega(D^2)\) tree bound of Disser et al. 2020 enters), and every dispersion algorithm is an exploration algorithm for anonymous graphs with local communication. For \(k < n\) dispersion asks for less: only \(k\) nodes must be occupied.

Related family: Computing with agents

Most algorithms first bring the \(n\) agents into a dispersed configuration, one agent per node, so that every node has an agent to compute for it Kshemkalyani et al. 2026 Chand & Molla 2026. Problems: Leader election by agents, Maximal independent set by agents, Minimal dominating set by agents, Triangle and butterfly counting by agents, Minimum spanning tree by agents, BFS tree by agents, Deciding graph properties by mobile agents.

Related problems

Uniform deployment on graphs: With \(k = n\) agents, dispersion and uniform deployment ask for the same final configuration, one agent on every node; dispersion also allows agents to share nodes at the start, uniform deployment does not Shibata et al. 2022a.

Perspectives

  • Why compute by moving The atlas collects four models that grew out of four different wishes: software that travels through a network, swarms of robots that are as weak as possible, searchers that must find something at an unknown place, and matter that reshapes itself. They share an adversary, locality and symmetry; they differ in what they count.
  • Symmetry is the adversary Identical agents running the same deterministic program can be kept in lockstep forever. Across graphs, the plane and programmable matter, the papers break this symmetry with identifiers, with randomness, with asymmetric starts, or with the scheduler, and leader election keeps reappearing as the common core.
  • From exploration to dispersion, and beyond How collaborative exploration asks how much a team speeds up a search, how dispersion arose as the case k = n under weaker assumptions, what dispersion gives back to exploration, and why dispersing first has become the standard opening move for computing graph structures with agents.
  • When agents fail A node that destroys visitors, a robot that stops, an agent that lies, a searcher that misses the target: the papers motivate each fault by the hardware or the network, and each kind of fault changes a different measure, from team size to feasibility to an exact constant.
  • What forces the bounds Every lower bound in the atlas names the resource the adversary exploits. Read side by side, a few bottlenecks (distance, symmetry, missing information, an adversary that acts) explain most tight results, and the open entries cluster where no bottleneck beyond distance is known.
  • The most consequential open problems Ten open questions ranked by how far a solution would propagate through the atlas, with the chain of problems each one feeds.

Further reading

Papers on this problem that are not yet placed in a setting.

  • Himani et al. 2026b Location-Aware Dispersion on Anonymous Graphs. Location-aware dispersion, a generalisation in which every node and every agent has a colour and each agent must settle alone on a node of its own colour (with one colour it is dispersion). Agents with distinct identifiers, local communication, synchronous rounds, \(k \le n\): a single agent cannot solve it without knowing \(n\) (Theorem 1); trees and rings take \(O(n)\) rounds with \(O(\log(k+\Delta))\) bits (Corollary 1); from a rooted start, \(O(m)\) rounds and \(O(\log k)\) bits when \(k = n\) and both are known (Theorem 3), \(O((n/k)\,m)\) rounds and \(O((n/k)\log(k+\Delta))\) bits knowing \(n\) (Theorem 4), and \(O(\log(n/k)\,(n/k)\,m)\) rounds without knowing \(n\) (Theorem 5); arbitrary and dispersed starts are reduced to these, the latter by first gathering the agents, in up to \(\tilde O(n^5)\) rounds (Theorems 6–10). The stated lower bound of \(\Omega(\min\{n^2/k, m\})\) rounds and \(\Omega((n/k)\log k)\) bits (Theorem 2) is argued only for memory, and informally. Preprint. Read.
  • Kaur & Mondal 2023 Distance-2-Dispersion: Dispersion with Further Constraints. Distance-2-dispersion: settled agents may not be adjacent, and an agent may share a node only when no node is left to settle; with \(k \ge n\) agents the settled nodes form a maximal independent set (see the MIS problem). From a rooted start with \(O(\log\Delta)\) bits besides the identifier, \(2\Delta(8m-3n+3)\) rounds (Theorem 3.4), against \(\Omega(m\Delta)\) for agents with that memory (Theorem 4.1). An arbitrary start is solved in Kaur et al. 2026c. Read (arXiv v1).
  • Amir & Bruckstein 2020 Fast Uniform Dispersion of a Crash-prone Swarm. Uniform dispersal: identical asynchronous robots enter an unknown graph over time from a source node, settle on empty nodes and guide the others; each node holds a bounded number of robots, and moving robots may crash. If at most \(ct/4\) crashes occur before time \(t\), with \(0 \le c < 1\), every node is settled by time \(8((1-c)^{-1}+o(1))n\) asymptotically almost surely (Theorem III.1), by comparison with a totally asymmetric simple exclusion process. Read (arXiv v3).
  • Rappel et al. 2022 Exploration and Coverage with Swarms of Settling Agents. Simple finite-memory airborne agents explore and fill an unknown connected region of the square grid, settling one per cell. A preprint; abstract read.
  • Himani et al. 2026a Efficient Dispersion of Mobile robots in Torus Networks. Dispersion on a \(\sqrt n \times \sqrt n\) torus, with oriented or unoriented port numbers, by synchronous agents that read the memory of agents on their node and know neither \(n\) nor \(k\): \(O(\sqrt n)\) rounds with \(O(\log n)\) bits per agent, from any start (Theorem 1; Section 6 removes the knowledge of \(n\), Sections 8 and 9 the orientation); this extends the oriented-grid algorithm of Kshemkalyani et al. 2020c. Read (model, algorithm and theorems).

All settings

The assumption tree (25 settings, 13 branch points)

The root assumes nothing. Going down, each edge adds the assumptions on its chips (+blue); a grey chip names the branch that leaves that axis unassumed while a sibling assumes something. Solid nodes are catalogued variants with their status per measure (Time, Memory); dashed nodes are branch points with no catalogued variant, named after the axis on which their branches differ. Axis order: Graph dynamics › Edge direction › Number of agents › Identifiers › Randomness › Topology › Grid orientation › Faults › Communication › Timing › Node memory › Node identifiers › Initial configuration.

tight near-optimal polynomial gap unknown impossible no variant

Assumptions specific to this problem

Grid orientation

0unoriented (no consistent compass)1oriented grid (consistent North, East, South, West ports)

In the graph model of dispersion the port labels at a node are local and independent of those at its neighbours Augustine & Moses Jr. 2018. Kshemkalyani, Molla and Sharma posed dispersion on grids Kshemkalyani et al. 2020c; later papers describe their setting as an oriented ("planar") grid Banerjee et al. 2024 Banerjee et al. 2025 Kumar et al. 2026a, although the arXiv version of Kshemkalyani et al. 2020c says the agents have no consistent compass (see the grid settings). Banerjee, Kumar and Molla made the distinction explicit and studied both kinds of grid, with and without crash faults Banerjee et al. 2024. Orientation matters because a grid is symmetric and the known algorithms steer by its geometry: they walk straight to the boundary, follow it to a corner and sweep rows. In an unoriented grid, in their words, "robots cannot distinguish whether they are moving in the same direction (i.e., along a row or column) or traversing in a cycle or zigzag manner across the unoriented grid" Banerjee et al. 2024. With a consistent compass, sweeps can start where the agents are, which gives \(O(\sqrt k)\) rounds with local communication Kumar et al. 2026a.

Formal definitions
0unoriented
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.
1oriented
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.

Know a better result, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.