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›directed, + \(k \le n\), + distinct IDs (eponymous), + no faults›+ \(h\)-hop communication, + synchronous

Directed graphs, 1-hop communication

verified
Time: polynomial gapMemory: polynomial gap

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.

Assumed (added on the last edge are outlined)

+Graph dynamicsstatic graph+Number of agents\(k \le n\)+Identifiersdistinct identifiers (eponymous): agents have pairwise distinct identifiers+Faultsno faults+Communication\(h\)-hop (agents within \(h\) hops communicate)+Timingsynchronous rounds

Not assumed

Edge directiondirected (strongly connected)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: directed
\(G=(V,A)\) with \(A\subseteq V\times V\); an agent at \(u\) may move along \((u,v)\in A\) only, never back along it unless \((v,u)\in A\). \(G\) is strongly connected.
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: \(h\)-hop communication
For a fixed \(h \ge 1\), stated with each result: at every round an agent at \(v\) can read the memory of every agent at a node \(u\) with \(\mathrm{dist}(v,u) \le h\) (in the current snapshot \(G_t\) for a dynamic graph), in addition to the co-located agents. \(h = 1\) is 1-hop communication (agents at neighbouring nodes communicate); local communication is the case \(h = 0\), and global communication the case \(h \ge D\). Reading another agent's memory does not tell an agent which port leads to it.
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

\(G\) is a directed graph with maximum out-degree \(\Delta_{out}\); at a node an agent sees only the out-ports \(1,\dots,\deg_{out}(v)\). Dispersion is not always solvable when \(G\) is not strongly connected, so results assume strong connectivity. \(\phi\) denotes the deficiency of \(G\), the number of arcs whose addition makes \(G\) Eulerian; \(f \le k\) agents may crash. Agents communicate with co-located agents and with agents on nodes at distance 1 (\(h = 1\)); communication does not follow arc directions.

What is known

Time · rounds in the synchronous model, epochs in the asynchronous model, until dispersion is reached
polynomial gap
\(O(kD)\) against \(\Omega(k)\) (and \(\Omega(D^2)\) for \(k = n\)): a factor up to \(D\).
lower bounds
\(\Omega(k)\) Italiano et al. 2022
bottleneckdistance
holds when
  • Theorem 3: deterministic
  • a directed cycle
  • stated for any deterministic algorithm, so it holds with 1-hop communication
\(\Omega(D^2)\) Italiano et al. 2022
bottleneckcollaborative tree exploration
holds when
  • Theorem 4: deterministic, \(k = n\), \(D = \omega(1)\)
  • a strongly connected digraph built from a tree, after the exploration bound of Disser et al. 2020
  • stated for any deterministic algorithm, so it holds with 1-hop communication
\(\text{impossible}\) Italiano et al. 2022
bottleneckno backtracking
holds when
  • Theorem 2: on some digraphs that are not strongly connected
  • a rooted start at a node from which some node is unreachable
  • stated for any deterministic algorithm, so it holds with 1-hop communication
introductory—
current best
\(O(kD)\)
\(h = 1\)
Memory · bits of persistent memory per agent, including its identifier
polynomial gap
\(O(k\log(k+\Delta_{out}))\) against \(\Omega(\log k)\): a factor \(k\).
lower bound
\(\Omega(\log k)\) Italiano et al. 2022
bottlenecksymmetry breaking
holds when
  • Theorem 6: deterministic
  • a rooted start
  • memory counts the identifier
  • stated for any deterministic algorithm, so it holds with 1-hop communication
introductory—
current best
\(O(k\log(k+\Delta_{out}))\)
\(h = 1\)

Results, in order of publication

Italiano et al. 2022 current best
Time \(O(kD)\)Memory \(O(k\log(k+\Delta_{out}))\)
\(h = 1\)

Introductory and current best (Theorem 1(c)): BFS-based; in every \(O(D)\) rounds at least one agent settles on an empty node. The bound also holds with \(f \le k\) crashes, with no extra time.

Open questions

  1. A BFS-based algorithm with \(O(\log(k+\Delta_{out}))\) bits per agent, as with local communication Italiano et al. 2022.

  2. Does \(O(kD)\) improve to \(O(k + D^2)\) or \(O(k)\) with 1-hop communication?

Notes

The lower bounds of Theorems 2, 3, 4 and 6 of Italiano et al. 2022 are stated for every deterministic algorithm and hold here; Theorem 5 bounds only DFS-based algorithms and does not apply to the BFS algorithm. Italiano, Pattanayak and Sharma remark that 1-hop information "is of no use in the DFS based algorithm". Checked against the full text of the JPDC version.

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

Directed graphs
Time \(O(k^2\Delta_{out})\)Memory \(\Theta(\log(k+\Delta_{out}))\)

Lower bounds from stronger settings hold here

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