Uniform deployment on graphs
Spread \(k \le n\) agents that start on distinct nodes of an \(n\)-node graph so that they end evenly spread, on a ring every two consecutive agents at distance \(\lfloor n/k\rfloor\) or \(\lceil n/k\rceil\), and stop.
Problem statement and measuresexpand
\(k\) agents start on distinct nodes of an anonymous graph \(G\) with \(n \ge k\) nodes and must reach a configuration in which they are evenly spread, and stop there. On a ring, evenly spread means that every two agents that are consecutive along the ring are at distance \(\lfloor n/k\rfloor\) or \(\lceil n/k\rceil\); on other graphs the target is stated with each result (one side of a complete bipartite graph, or every node at chosen depths of a perfect tree). Almost uniform deployment asks this of all agents but one. Measures: time in rounds (ideal time units for asynchronous agents), the total number of moves, a move being the traversal of one edge by one agent, and memory in bits per agent.
Measures: Time, rounds (ideal time units for asynchronous agents) until the agents are evenly spread and have stopped; Moves, total number of edge traversals by all agents; Memory, bits of memory per agent.
Asynchronous unidirectional rings
standard settingdraftOn a static unidirectional ring, asynchronous agents that know \(k\) or \(n\) spread evenly in \(\Theta(n)\) time with \(\Theta(kn)\) moves, as reported.
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: 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.
- 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: 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: asynchronous
- Each agent's Communicate–Compute–Move steps take finite but unbounded, adversarially chosen time. Time is measured in epochs. An epoch is an interval of time in which every agent completes at least one full Communicate–Compute–Move step; it need not be the shortest such interval. Time is counted by dividing the execution into consecutive epochs, and a bound of \(X\) epochs holds for every such division.
- Topology: ring
- \(G\) is a cycle \(C_n\) (every node of degree 2), or a path when stated.
- Initial configuration: dispersed start
- Every initially occupied node holds exactly one agent (\(\ell=k\)). Also called a scattered start, notably in black hole search.
- Goal: all agents
- Every agent ends evenly spread and stops.
What is known
- as reported by Shibata et al. 2022a; not read
- as reported by Shibata et al. 2022a (Section 2 and Table 1); not read
Results, in order of publication
Introductory and current best, as reported by Shibata et al. 2022a (Table 1, Result 1); not read. Knowing \(n\) and knowing \(k\) are equivalent on static rings.
Less memory at the price of a \(\log k\) factor in time, as reported by Shibata et al. 2022a (Table 1, Result 2); not read.
Open questions
None recorded for this variant.
Notes
Draft: Shibata et al. 2018 has no open copy and was not read; its bounds are taken from Table 1 of Shibata et al. 2022a, which also reports algorithms without knowledge of \(k\) or \(n\) for agents that can communicate, and a follow-up on memory (Shibata, Kakugawa and Masuzawa, TCS 2020, not in this atlas).
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.