Leader election in programmable matter
Anonymous constant-memory particles must elect exactly one leader, which most shape-formation algorithms need first.
Problem statement and measuresexpand
A connected configuration (the set of nodes occupied by particles) of \(n\) anonymous particles (initially contracted) must reach a state in which exactly one particle is the leader and all others know they are not. Time is in asynchronous rounds; \(L_{out}\) is the length of the outer boundary and \(D\) the diameter of the configuration.
Measures: Time, asynchronous rounds; Moves, total expansions and contractions (work).
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
unknown
\(O(L_{out}+D)\) vs —
unknown
— vs —
unknown
\(O(n)\) vs —
tight
— vs —
polynomial gap
\(O(L_{out}n^2)\) vs —
unknown
— vs —
unknown
\(O(n^3)\) vs \(\text{explicit termination impossible}\)
symmetry breaking
tight
— vs —
Stationary, fair scheduler, no orientation, no holes no orientation, stationary, + no holes
0 open · 1 results
unknown
\(\text{finite}\) vs —
tight
— vs —
unknown
\(O(n^2)\) vs —
tight
— vs —
Stationary, asynchronous, no orientation, no holes weak scheduler, no orientation, + no holes
1 open · 1 results
unknown
\(\text{finite}\) vs —
tight
— vs —
unknown
\(O(n)\) vs —
tight
— vs —
impossible
\(O(n^2)\) vs \(\text{impossible}\)
symmetry breaking
unknown
— vs —
unknown
\(O(n)\) vs —
unknown
— vs —
Oblivious, common compass, holes allowed oblivious, + sequential, + common compass, + may move
0 open · 1 results
unknown
\(\text{finite}\) vs —
unknown
— vs —
Know a better result, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.