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

Progress map

tight near-optimal polynomial gap unknown impossible· rows follow the assumption tree; each cell: best upper bound vs lower bound, and what forces the lower bound

Setting

Time

Moves

Memory

No assumptions

—

Dynamic rings, all agents + connected every round, + undirected, + no faults, + synchronous, + ring, + dispersed start

0 open · 0 results

impossible — vs \(\text{impossible}\) adversarial edge changes

impossible — vs —

Dynamic rings, all agents but one + all but one

2 open · 2 results

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 + static graph, + no faults, + ring, + dispersed start

0 open · 2 results

tight \(\Theta(n)\) vs \(\Omega(n)\) distance

tight \(\Theta(kn)\) vs \(\Omega(kn)\) distance

unknown \(O(k\log n)\) vs —

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