Leader election by agents
\(n\) agents in an anonymous graph must elect one leader; how fast, and with how little memory?
Problem statement and measuresexpand
\(n\) agents with distinct identifiers (IDs) are placed on the nodes of an anonymous port-labelled graph with \(n\) nodes, \(m\) edges and maximum degree \(\Delta\). The start is rooted (all agents on one node), dispersed (one agent on each node) or arbitrary. Agents compute only by moving and by talking with agents on the same node. The agents must elect exactly one leader: every agent (or node) learns its part of the output. Time is in synchronous rounds; memory in bits per agent.
Measures: Time, rounds; Memory, bits 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
Memory
No knowledge + static graph, + undirected, + distinct IDs (eponymous), + local communication, + synchronous
0 open · 3 results
unknown
\(O(n)\) vs —
unknown
\(O(\log n)\) vs —
unknown
\(O(n\log^2 n+D\Delta\log n)\) vs —
unknown
\(O(\log n)\) vs —
Know a better result, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.