Leader election in the plane
Anonymous robots must agree on one of them, using only their positions.
Problem statement and measuresexpand
\(n\) anonymous robots (identical, with no names) at distinct points must agree on a single robot (the leader), each deciding from its own snapshot.
Measures: Time, rounds (FSYNC, SSYNC) or epochs (ASYNC) until the task is done; "finite" when only solvability is known; Colours, colours of the light per robot (0 for oblivious robots).
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
Colours
Disoriented robots, with or without chirality + point, + unlimited visibility, + transparent, + no faults
0 open · 1 results
unknown
\(\text{finite}\) vs \(\text{impossible}\)
symmetry
tight
\(0\) vs —
unknown
\(\text{finite}\) vs \(\text{impossible}\)
symmetry breaking
tight
\(0\) vs —
Know a better result, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.