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 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.

no assumptions›+ static graph›+ undirected›+ \(k \le n\)›+ distinct IDs (eponymous)›+ at most crash faults, + local communication, + synchronous

Crash faults

verified

Time: polynomial gapMemory: near-optimal

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.

Assumed (added on the last edge are outlined)

+Graph dynamicsstatic graph+Edge directionundirected+Number of agents\(k \le n\)+Identifiersdistinct identifiers (eponymous): agents have pairwise distinct identifiers+Faultsup to \(f\) agents may crash (stop forever)+Communicationlocal (co-located agents communicate)+Timingsynchronous rounds

Not assumed

RandomnessdeterministicNode memoryno whiteboardsNode identifiersanonymous nodesTopologyarbitrary connected graphInitial configurationarbitrary (agents on any \(\ell \le k\) nodes)

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: at most crash faults: Up to \(f\) agents may stop forever at an adversarially chosen time; a crashed agent stays at its node (or vanishes, as stated per result) and never acts again.
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.

Statement for this variant

An adversary may crash up to \(f \le k\) agents at arbitrary times. A crashed agent loses its memory and can no longer move or be seen by others. Dispersion is achieved when the \(k-f\) non-faulty agents occupy \(k-f\) distinct nodes. \(\ell\) is the number of initially occupied nodes.

What is known

Time · rounds in the synchronous model, epochs in the asynchronous model, until dispersion is reached

polynomial gap

\(O(\min(m,k\Delta))\) versus \(\Omega(k)\): a factor \(\Delta\), as in the fault-free DFS era; the fault-free \(O(k)\) techniques (oscillating settled agents) have not been made crash-tolerant.

lower bound

\(\Omega(k)\) Kshemkalyani & Ali 2019

bottleneckdistance

holds when

fault-free bound (\(f = 0\))
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

Fault-free lower bound; no crash-specific lower bound is known.

introductory

\(O(f\cdot\min(m, k\Delta))\)

Pattanayak et al. 2021

rooted

current best

\(O(\min(m, k\Delta))\)

Pattanayak et al. 2023

Memory · bits of persistent memory per agent, including its identifier

near-optimal

\(O(\log(k+\Delta))\) bits are enough but only with an extra factor \((\ell+f)\) in time; the fast algorithm uses \(O(k\log(k+\Delta))\).

lower bound

\(\Omega(\log k)\) Augustine & Moses Jr. 2018

bottlenecksymmetry breaking

holds when

deterministic
all agents have the same memory bound
an initial configuration with co-located agents (rooted suffices)
memory counts the identifier

introductory

\(O(\log(k+\Delta))\)

Pattanayak et al. 2021

rooted

current best

\(O(k\log(k+\Delta))\)

Pattanayak et al. 2023

Results, in order of publication

Pattanayak et al. 2021 introductory

Time \(O(f\cdot\min(m, k\Delta))\)Memory \(O(\log(k+\Delta))\)

rooted

First crash-tolerant dispersion on arbitrary graphs: a DFS that restarts whenever the agent carrying the traversal state crashes.

Chand et al. 2023 also

Time \(O(k^2)\)Memory \(O(\log(k+\Delta))\)

rooted

Independent of \(f\). For arbitrary configurations: \(O((f+\ell)\cdot\min(m, k\Delta, k^2))\) rounds with \(O(\log(k+\Delta))\) bits when \(k\), \(f\), \(\Delta\), \(\ell\) and \(m\) are known, and \(O(k^3)\) when only \(k\) is known.

Pattanayak et al. 2023 current best

Time \(O(\min(m, k\Delta))\)Memory \(O(k\log(k+\Delta))\)

Arbitrary configurations, no knowledge of \(m\), \(\Delta\), \(\ell\), \(k\) or \(f\), time independent of \(f\). A second algorithm trades memory for time: \(O(\min(m,k\Delta)\cdot(\ell+f))\) rounds with \(O(\log(k+\Delta))\) bits.

Open questions

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. 2023.
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. 2023 Pattanayak et al. 2023.
Crash faults under asynchrony: no result exists.

Notes

On 1-interval connected dynamic graphs with global communication, crashes cost nothing: \(O(k-f)\) rounds with \(\Theta(\log k)\) bits Kshemkalyani et al. 2020. The directed-graph algorithms of Italiano et al. 2022 also extend to crash faults (bounds not transcribed here).

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.