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.
Anonymous agents with randomness
verifiedAgents 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.
Assumed (added on the last edge are outlined)
Not assumed
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: anonymous
- All agents run the same deterministic algorithm on the same input; no agent has a label. Formally the label function is constant: \(\mathrm{id}(a)=\mathrm{id}(b)\) for all agents \(a,b\).
- Randomness: private coins
- Each agent additionally has access to independent fair coin flips; guarantees hold with probability 1, in expectation, or with high probability, as stated per result.
- Faults: no faults
- All agents follow the algorithm forever.
- 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
Agents are identical and run a randomized algorithm; deterministic algorithms are impossible for anonymous agents Das et al. 2021. Memory is measured without an identifier, so bounds below \(\log k\) become possible. Results hold with high probability unless stated otherwise.
What is known
- a path with all \(k\) agents on one endpoint
- no identifiers needed
- holds for randomized algorithms
- all agents have the same memory bound
- an agent with \(b\) bits can choose among at most \(2^b\) ports
- worst case over graphs: a node of degree \(\Delta\) whose ports lead to the free nodes
- holds for randomized algorithms
Results, in order of publication
Local leader election by coin flips replaces identifiers. Rooted graphs: \(O(m)\) rounds with \(O(\max(\log\Delta,\log D))\) or \(O(\Delta)\) bits; rooted rings with \(O(1)\) bits and rooted trees with \(O(\log\Delta)\) bits in \(O(n)\) rounds. Arbitrary configurations (\(k = n\)): a random-walk algorithm with \(O(\log\Delta)\) bits disperses within the cover time of \(G\) but the agents never terminate.
Memory matches the \(\Omega(\log\Delta)\) lower bound; the agents terminate. The time is \(\Theta(k^2)\) in the worst case for this algorithm.
Open questions
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. 2021.
Can anonymous randomized agents disperse from an arbitrary configuration and then stop, rather than staying active forever? Molla & Moses Jr. 2019 Das et al. 2021
On rings the memory bound is \(O(1)\); is \(O(1)\)-bit dispersion with termination possible on rings from arbitrary configurations?
Notes
The deterministic memory bound \(\Omega(\log k)\) comes entirely from storing an identifier. Removing identifiers and adding coins lowers the bound to \(\Omega(\log\Delta)\), achieved for rooted configurations.
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
Lower bounds from stronger settings hold here
No catalogued stronger setting.
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.