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 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)›+ no faults›no communication, + synchronous›+ ring

Silent agents on rings

verified
Time: tightMemory: tight

On an oriented ring, silent agents from arbitrary configurations disperse in optimal \(\Theta(k + \log L)\) rounds.

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+Faultsno faults+Timingsynchronous rounds+Topologyring or path

Not assumed

RandomnessdeterministicCommunicationnone (silent agents; only see how many agents are co-located)Node memoryno whiteboardsNode identifiersanonymous nodesInitial 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: no faults
All agents follow the algorithm forever.
Communication: no communication
Agents exchange no messages; an agent at \(v\) observes only the number of agents at \(v\) (and, where stated, whether that number changed).
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: ring
\(G\) is a cycle \(C_n\) (every node of degree 2), or a path when stated.
Initial configuration: any start
Agents start at arbitrary nodes; \(\ell\le k\) nodes are initially occupied, possibly with several agents each.

What is known

Time · rounds in the synchronous model, epochs in the asynchronous model, until dispersion is reached
tight
\(\Theta(k + \log L)\).
lower bound
\(\Omega(k + \log L)\) Das et al. 2025
bottlenecktiming is the only channel
holds when
  • no communication: only alone / count-change sensing
  • identifiers in \([0,L]\), unknown to the other agents
introductory—
current best
\(O(k + \log L)\)
oriented ring
Memory · bits of persistent memory per agent, including its identifier
tight
\(\Theta(\log L)\).
lower bound
\(\Omega(\log L)\) Gorain et al. 2022
bottleneckencoding the identifier
holds when
  • additional bits beyond the identifier
  • \(\Delta = 2\), so only the \(\log L\) term remains
\(\Delta = 2\).
introductory—
current best
\(O(\log L)\)
oriented ring

Results, in order of publication

Das et al. 2025 current best
Time \(O(k + \log L)\)Memory \(O(\log L)\)
oriented ring

Introductory and current best; arbitrary initial configurations.

Open questions

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

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

Silent agents (no communication)
Time \(O(k\log L + k^2\log\Delta)\)Memory \(O(\log L + \log\Delta)\)

Lower bounds from stronger settings hold here

Rings and paths
Time \(\Omega(k)\)Memory \(\Omega(\log k)\)

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