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.
More agents than nodes
verifiedWith \(k > n\) the target is a balanced configuration: at most \(\lceil k/n\rceil\) agents per node. Only randomized anonymous results exist.
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: any \(k\)
- The number of agents \(k\ge1\) is arbitrary; \(k>n\) is allowed.
- 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
\(k > n\) agents must reach a configuration in which every node hosts at most \(\lceil k/n \rceil\) agents (sometimes called \(k\)-dispersion). Agents do not know \(n\).
What is known
- all agents have the same memory bound
- model assumption of Molla & Moses Jr. 2019: an agent with \(b\) bits sees at most \(2^b\) ports of its node, and the adversary chooses which
- holds for randomized algorithms
Results, in order of publication
Introductory and current best. Rooted configurations on arbitrary graphs; the bound is a sketched modification of the rooted algorithm in Section 8, not a numbered theorem. The same paper gives \(O(mk/n)\) rounds with \(O(\max\{\log\Delta,\log D\})\) bits, and \(O(k)\) rounds with \(O(\log\Delta)\) bits on rooted rings and rooted trees.
With high probability; this algorithm does not terminate: settled agents stay active forever.
Open questions
Deterministic dispersion with \(k > n\) agents with identifiers on static graphs has not been studied: no algorithm and no lower bound beyond \(\Omega(k)\) is recorded in the literature surveyed here. (Related work exists only on dynamic rings and dynamic graphs under the name balanced dispersion.)
Is \(O(k)\) time possible for rooted configurations when \(k > n\), matching the \(k \le n\) case?
Terminating dispersion with \(k > n\) on general rooted graphs with \(O(\log\Delta)\) bits per agent (Open Problem 2 of Molla & Moses Jr. 2019).
Notes
The balanced target, at most \(\lceil k/n\rceil\) agents per node, is the formulation of Molla & Moses Jr. 2019 itself. Many agents may cross one edge in the same round, so the \(\Omega(k)\) argument for \(k \le n\) does not carry over. Checked against the full text (arXiv 1902.10489).
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
No catalogued weaker setting.
Lower bounds from stronger settings hold here
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.