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 weak Byzantine faults, + local communication, + synchronous

Weak Byzantine agents

verified

Time: polynomial gapMemory: unknown

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.

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\) weak Byzantine agents (arbitrary behaviour, cannot fake identifiers)+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 weak Byzantine faults: Up to \(f\) agents behave arbitrarily but always report their own true identifier.
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

Up to \(f\) agents are controlled by an adversary that knows the algorithm and the honest agents' states; they may move and communicate arbitrarily but cannot change their identifiers. The goal is a configuration in which every node holds at most one non-Byzantine agent, with all non-Byzantine agents terminated. Results below take \(k = n\) and assume the agents know \(n\). \(X(n)\) denotes the time to explore any \(n\)-node graph, \(\tilde O(n^5)\).

What is known

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

polynomial gap

Polynomial, but \(\tilde O(n^9)\) versus \(\Omega(n)\); the bottleneck is Byzantine gathering.

lower bounds

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

bottleneckdistance

holds when

fault-free bound (\(f = 0\))
a path with all \(k\) agents on one endpoint

Fault-free bound; no Byzantine-specific time lower bound is known.

\(\text{impossible}\) Molla et al. 2021

bottleneckindistinguishable Byzantine agents

holds when

\(\lceil k/n\rceil > \lceil (k-f)/n\rceil\)
weak Byzantine agents
deterministic
even with known \(n\), \(k\) and \(f\)

The Byzantine agents can behave exactly like honest agents and occupy nodes, so the honest agents cannot reach the balanced target.

introductory—

current best

\(\tilde O(n^9)\)

Molla et al. 2021

\(k = n\)knows \(n\)\(f \le \lfloor n/2 \rfloor - 1\)

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

unknown

Memory is not bounded in the general-graph algorithms.

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—

current best—

Results, in order of publication

Molla et al. 2021 current best

Time \(\tilde O(n^9)\)

\(k = n\)knows \(n\)\(f \le \lfloor n/2 \rfloor - 1\)

Introductory and current best on general graphs. Precisely \(O(n^4\cdot|\Lambda_{good}|\cdot X(n))\) rounds for arbitrary configurations, \(|\Lambda_{good}|\) the length of the largest honest identifier; \(O(n^4)\) if the agents start gathered; \(O(n^3)\) gathered with \(f \le \lfloor n/3\rfloor - 1\); \(O((f + |\Lambda|)\cdot X(n))\) for \(f = O(\sqrt n)\). Tolerates \(f \le n-1\) in polynomial time on graphs isomorphic to their quotient graph. Memory per agent is not analysed except for that last algorithm (\(O(m\log n)\) bits).

Open questions

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. 2021.
Tolerating more than \(n/2\) weak Byzantine agents on general graphs (possible only on the restricted class so far) Molla et al. 2021.
Byzantine dispersion with bounded memory per agent, on trees, with \(k < n\), or under asynchrony: nothing is known Molla et al. 2020 Chand et al. 2023.

Notes

Byzantine dispersion was introduced on rings Molla et al. 2020 and then on general graphs Molla et al. 2021; no general-graph improvement has appeared since 2021.

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.