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.
Dynamic rings, all agents
verifiedOn a 1-interval connected ring, synchronous agents cannot all end evenly spread: the adversary can block one agent forever.
Assumed (added on the last edge are outlined)
Not assumed
Formal definitions of this setting
- Graph dynamics: connected every round
- \(\mathcal G=(G_t)_{t\ge0}\) is 1-interval connected if every snapshot \(G_t=(V,E_t)\) is connected. More generally it is \(T\)-interval connected if for every \(t\) the graph \(\bigl(V,\bigcap_{i=t}^{t+T-1}E_i\bigr)\) is connected.
- Edge direction: undirected
- \(G=(V,E)\) with \(E\subseteq\binom V2\); every edge can be traversed in both directions.
- 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: synchronous
- Time proceeds in rounds \(t=1,2,\dots\); in every round every agent communicates, computes and moves (at most one edge) simultaneously.
- 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
- whenever \(k\) divides \(n\) (Theorem 1)
- take a run with no missing edge and the last agent to stop; in a second run the adversary removes the edge in front of that agent during its last \(n/2k\) rounds, in which no other agent sees it, so the others stop as before and it stops in the wrong place
- holds even for agents that know \(n\) and \(k\), agree on the clockwise direction, count the agents on their node and carry tokens
Results, in order of publication
No result recorded yet.
Open questions
None recorded for this variant.
Notes
Checked against the full text of Shibata et al. 2022a.
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
Branches from here
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.