Mobility Matters
Home›Mobile agents on graphs›Exploration›Uniform deployment on graphs

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 measurescollapse
startselectionround 1selectionround 2selectionround 3selectionround 4selectionround 5selectionround 6selectionround 7selectionround 8selectionround 9selectionround 10selectionround 11selectionround 12selectionround 13selectionround 14selectionround 15selectionround 16selectionround 17selectionround 18selectionround 19deploymentround 20deploymentround 21deploymentAABBCCStart: A, B, C drop their tokens (squares) and walk clockwise for 3n = 18 roundsRound 2: the edge in front of C is missing; C is blocked and waitsRound 6: A and B have gone once around and know the gaps between tokensRound 8: C has gone once around too; all keep walking until round 18Round 18: base node = A's home; ranks A 0, B 2, C 1; targets 0, 4, 2 edges past itFinal: every two consecutive agents are n/k = 2 edges apart; all stop
Almost uniform deployment on a dynamic ring, the algorithm of Shibata et al. 2022a for agents that know \(n\): \(k = 3\) identical agents on a ring of \(n = 6\) nodes agree on the clockwise direction. In the selection phase each agent drops its token on its home node and walks clockwise for \(3n\) rounds, blocked whenever the edge in front of it is missing (dashed red; at most one edge is missing per round). Having gone once around, it knows the gaps between consecutive tokens. The rotation of the gap sequence that is smallest in dictionary order, here \((1, 2, 3)\), starts at the same token for every agent: the base node. An agent whose own sequence must be rotated \(r\) times to reach it has rank \(r\) and walks to the node \(r \cdot n/k\) edges clockwise from the base node (green circles), where it stops (green). In this run no edge is missing after round 3; when one stays missing, the agents still walking split into two groups that walk in opposite directions, and at most one agent ends out of place. One frame per round.

\(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.

A first look

the basic problem, a simple algorithm and why some things cannot be done, for a newcomer

Picture \(k\) guards on a circular wall with \(n\) towers, who must spread out so that the gaps between neighbouring guards are as equal as possible, and then stand still. The wall is a ring: a cycle of \(n\) nodes (the towers), each joined by an edge (a stretch of wall) to the next. The guards are agents: mobile entities with memory that move along edges and see only the node they stand on. The nodes have no names and the agents are identical. The \(k \le n\) agents start on distinct nodes and must become evenly spread: every two agents that are consecutive along the ring are \(\lfloor n/k\rfloor\) or \(\lceil n/k\rceil\) edges apart. Then they stop. In the standard version each edge can be crossed in one direction only (the ring is unidirectional), the agents are asynchronous (each acts at its own unpredictable speed), and they know \(k\) or \(n\). We count moves (a move is one agent crossing one edge), time and memory. Time is counted in rounds; in a round every agent may cross one edge.

1AlgorithmGo once around, then agree on a base node Dynamic rings, all agents but one → Shibata et al. 2022a

This version is harder. The ring is dynamic: in every round an adversary, an opponent who knows the algorithm, may remove one edge. An agent that tries to cross the missing edge is blocked and stays where it is. The agents move in synchronous rounds, know \(n\), and agree on which way is clockwise. Each agent can count the agents on its node, and carries a token, a marker it can leave on a node. A token carries no name.

  1. Every agent leaves its token on its start node, its home node. It then walks clockwise for \(3n\) rounds, waiting whenever it is blocked.
  2. On the way it writes down the distances between consecutive tokens. Once it has gone around, this list of gaps describes the start, read from its own home node.
  3. Every agent rotates its list to the rotation that comes first in dictionary order. That rotation starts at the same token for every agent, unless the start repeats itself around the ring (then there is one such token per repetition). The node of that token is the base node. The number of steps the agent rotated is its rank \(r\).
  4. If missing edges stopped an agent from going once around, the agents notice it: they have all piled up on one node. They count themselves there and take ranks in the order in which they arrived; that node becomes the base node.
  5. The agent of rank \(r\) walks clockwise to the node \(r \cdot n/k\) edges past the base node and stops there. If an edge stays missing, the agents still walking split into two groups that walk in opposite directions. The adversary can hold back only one group, so the other group arrives.
Why it works and what it costs. In \(3n\) rounds an agent either goes once around or is blocked more than \(2n\) times. Only one edge is missing per round, so while it is blocked every other agent gets one edge closer to it; in the second case they all end on its node (Lemma 1). Splitting halves the number of agents still walking each time, so after about \(\log k\) phases of \(O(n)\) rounds at most one agent is left out of place. The goal allows exactly that: almost uniform deployment asks that all agents but one be evenly spread. In total this takes \(O(n \log k)\) rounds and \(O(kn)\) moves, since the walking agents halve from phase to phase; each agent needs \(O(k \log n)\) bits to store the list of gaps Shibata et al. 2022a. The moves are optimal, and the time is within a factor \(\log k\) of the lower bound \(\Omega(n)\). On a ring whose edges never go missing, the same idea of going once around and then choosing gives \(\Theta(n)\) time and \(\Theta(kn)\) moves Shibata et al. 2018, as reported by Shibata et al. 2022a.

Why it matters. Anonymous agents that see only their own node can still agree on a common reference point by reading the same circular list from different starting points. That is the core of deployment on rings.

2ImpossibilityThe adversary blocks the last agent Dynamic rings, all agents → Shibata et al. 2022a

Suppose some algorithm made all \(k\) agents evenly spread on every dynamic ring, with \(k\) dividing \(n\).

  1. Run it on a ring whose edges never go missing. Let \(a\) be the last agent to stop, at round \(t\); the proof considers an \(a\) that is still walking towards its place in its last rounds.
  2. When the agents stop, \(a\)'s neighbours are \(n/k\) edges away. Two agents get at most two edges closer per round, so during its last \(n/2k\) rounds \(a\) shares a node with no other agent.
  3. Run the algorithm again, identically until \(n/2k\) rounds before \(t\). From then on the adversary removes the edge that \(a\) tries to cross, so \(a\) never moves again. One missing edge per round is allowed.
  4. No other agent meets \(a\) in these rounds, so the others behave exactly as in the first run and stop at the same nodes.
Why it holds. In the second run, \(a\) stays on the node where it stood \(n/2k\) rounds before \(t\), short of the node where it stopped in the first run, while every other agent stops where it stopped before. So \(a\) ends in the wrong place and the algorithm fails Shibata et al. 2022a. The argument still works when the agents know \(n\) and \(k\), agree on the clockwise direction, count the agents on their node and carry tokens. This is why the task on dynamic rings asks only for almost uniform deployment.

Why it matters. It shows the adversary's weapon, holding one agent where nobody can see it, and it fixes the relaxed goal that the algorithm above reaches.

3Lower boundDistance: \(\Omega(kn)\) moves Dynamic rings, all agents but one → Shibata et al. 2022a

Start the \(k\) agents on \(k\) consecutive nodes, with \(k\) small compared with \(n\). In the end, consecutive agents are about \(n/k\) edges apart, so the agents are spread over the whole ring. The nodes at least \(n/4\) edges from the starting block make up more than a third of the ring once \(k\) is small. Spread evenly, the agents put a fixed fraction of themselves there.

Why it holds. So a fixed fraction of the \(k\) agents each cross at least \(n/4\) edges, in total \(\Omega(kn)\) moves; leaving one agent out of place changes nothing. Such an agent needs \(n/4\) rounds, which gives \(\Omega(n)\) time. Shibata et al. 2022a state these bounds for \(k \le pn\) with a constant \(p < 1\), following Shibata et al. 2018. They already hold on a ring whose edges never go missing.

Why it matters. It shows that the \(O(kn)\) moves of the algorithm above cannot be improved, so the remaining question is time: \(O(n \log k)\) against \(\Omega(n)\).

What is known

The best upper bound against the best lower bound in each catalogued setting. Open a setting for its results, proofs and notes, or see the progress map with the branch points.

tight near-optimal polynomial gap unknown impossible· one row per catalogued setting, in tree order; each cell: best upper bound vs lower bound, and what forces the lower bound
Setting
Time
Moves
Memory
Dynamic rings, all agents
On a 1-interval connected ring, synchronous agents cannot all end evenly spread: the adversary can block one agent forever.
impossible — vs \(\text{impossible}\) adversarial edge changes
impossible — vs —
impossible — vs —
Dynamic rings, all agents but one
If one agent may end out of place, synchronous agents that know \(n\) spread evenly on a 1-interval connected ring in \(O(n\log k)\) rounds with \(O(kn)\) moves, which is optimal in moves.
near-optimal \(O(n\log k)\) vs \(\Omega(n)\) distance
tight \(O(kn)\) vs \(\Omega(kn)\) distance
unknown \(O(k\log n)\) vs —
Asynchronous unidirectional rings standard
On a static unidirectional ring, asynchronous agents that know \(k\) or \(n\) spread evenly in \(\Theta(n)\) time with \(\Theta(kn)\) moves, as reported.
tight \(\Theta(n)\) vs \(\Omega(n)\) distance
tight \(\Theta(kn)\) vs \(\Omega(kn)\) distance
unknown \(O(k\log n)\) vs —

Open questions 2

Dynamic rings, all agents but one

  1. Is \(O(n)\) time possible on a 1-interval connected ring? Shibata et al. 2022a reach \(O(n\log k)\) against \(\Omega(n)\) and leave the lower bound on time to future work.
  2. Can almost uniform deployment be reached without chirality or without strong multiplicity detection Shibata et al. 2022a?

What the community started looking at

Uniform deployment asks agents that start on distinct nodes to end evenly spread. Look–Compute–Move robots that see several nodes were deployed on rings and grids first; Shibata et al. studied agents that have memory but see only their own node, on asynchronous unidirectional rings, with \(\Theta(n)\) time and \(\Theta(kn)\) moves Shibata et al. 2018 (as reported by Shibata et al. 2022a). On a dynamic ring the adversary can block one agent forever, so Shibata, Sudo, Nakamura and Kim ask for almost uniform deployment and reach it with an optimal number of moves Shibata et al. 2022a. Other graphs have their own targets: every node at chosen depths of a perfect tree Shibata & Tixeuil 2023, and one side of a complete bipartite graph Shibata et al. 2025.

Related problems

Dispersion: With \(k = n\) agents, dispersion and uniform deployment ask for the same final configuration, one agent on every node; dispersion also allows agents to share nodes at the start, uniform deployment does not Shibata et al. 2022a.

Uniform deployment on a ring: The same task for robots on a continuous ring in the plane, where the target spacing is a length rather than a number of edges Flocchini et al. 2008b.

Further reading

Papers on this problem that are not yet placed in a setting.

  • Shibata & Tixeuil 2023 Semi-uniform deployment of mobile robots in perfect \(\ell\)-ary trees. Semi-uniform deployment on a perfect tree (every internal node has the same number of children, all leaves at the same depth): \(k\) opaque Look–Compute–Move robots with lights, on distinct nodes, must occupy every node at depths forming an arithmetic progression, \(k\) being the number of such nodes, without collisions, and stop (Definition 1). With one colour, that is oblivious robots, no algorithm does so even under FSYNC (Theorem 2); with two colours a collision-free algorithm works under ASYNC in \(O(kD)\) rounds (Theorem 3), against \(\Omega(D + k)\) (Theorem 1). Read in full.
  • Shibata et al. 2025 Uniform Deployment of Mobile Robots in Complete Bipartite Graphs. Uniform deployment on the complete bipartite graph \(K_{k,k}\) (their \(K_{n,n}\); anonymous nodes, local port numbers): \(k\) oblivious, anonymous Look–Compute–Move robots without lights stand on distinct nodes and must occupy every node of one side, so that any two robots are at distance 2. A start with a bijection between the two sides that preserves what every node sees is unsolvable even under FSYNC (Theorem 2); with visibility range 1 the task cannot be solved even under FSYNC (Theorem 4); with visibility range \(2\lceil\log k\rceil + 2\) the robots detect the unsolvable starts (Theorem 7) and from every other one finish in \(O(1)\) epochs, each robot moving at most once, even under ASYNC (Theorem 9). Whether a constant visibility range suffices is open (Section 6). Read.

All settings

The assumption tree (3 settings, 1 branch points)

The root assumes nothing. Going down, each edge adds the assumptions on its chips (+blue); a grey chip names the branch that leaves that axis unassumed while a sibling assumes something. Solid nodes are catalogued variants with their status per measure (Time, Moves, Memory); dashed nodes are branch points with no catalogued variant, named after the axis on which their branches differ. Axis order: Graph dynamics › Edge direction › Identifiers › Randomness › Faults › Communication › Timing › Topology › Initial configuration › Goal.

tight near-optimal polynomial gap unknown impossible no variant

Assumptions specific to this problem

Goal

0uniform deployment1almost uniform deployment

Exact deployment cannot be reached on a dynamic ring, where the adversary may block one agent forever, so Shibata, Sudo, Nakamura and Kim relax it to all agents but one Shibata et al. 2022a. The relaxed goal is the weaker requirement, hence the higher level.

Formal definitions
0all agents
Every agent ends evenly spread and stops.
1all but one
All agents but one end evenly spread and stop; the remaining agent may stop on any node.

Know a better result, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.