Mobility Matters
Home›Mobile agents on graphs›Computing with agents›Leader election by agents

Leader election by agents

\(n\) agents in an anonymous graph must elect one leader; how fast, and with how little memory?

Problem statement and measurescollapse
111001min 3min 2min 1111001min 3min 2min 1111001min 3min 2min 1111001min 3min 2min 1111001min 3min 2min 1111001min 3min 2min 1111001min 3min 2min 1111001min 3min 2min 1111001min 2min 1min 1111001min 2min 1min 1111001min 2min 1min 1111001min 2min 1min 1111001min 2min 1min 1111001min 2min 1min 1111001min 2min 1min 1111001min 2min 1min 1111001min 1min 1min 1112233Start: dispersed; IDs written in 2 bitsSim. round 1, block 1: 2, 3 visitSim. round 1, block 2: 1, 3 visitSimulated round 1 done: mins exchangedSim. round 2, block 1: 2, 3 visitSim. round 2, block 2: 1, 3 visitFinal: after n−1 = 2 simulated rounds, 1 leads
Leader election by simulating message passing Kshemkalyani et al. 2024: the agents, already dispersed one per node of a path, write their IDs in 2 bits. In block \(i\) (of \(2\Delta = 4\) rounds) an agent whose \(i\)-th bit is 1 visits each neighbour and comes back, one edge per round, while agents with bit 0 wait at home (the ID-bit schedule); every visit to a waiting neighbour (blue edge) carries the messages of one simulated round, here the smallest ID seen ("min"). Both simulated rounds are shown round by round; after \(n-1 = 2\) of them every agent knows that agent 1 is the leader.

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

A first look

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

Picture \(n\) agents (small mobile computers) dropped into a building with \(n\) rooms, where the rooms carry no names and an agent can only talk to agents standing in the same room. The building is a graph: rooms are its nodes and corridors are its edges; there are \(n\) nodes and \(m\) edges, and from here on we say only node and edge. Two nodes joined by an edge are neighbours. The degree \(\deg(v)\) of a node \(v\) is the number of edges at it, and \(\Delta\) is the maximum degree. Nodes have no names, but the edges at a node \(v\) are numbered \(1, 2, \dots, \deg(v)\); these numbers are ports, so an agent can say "leave by port 3". Every agent carries a distinct identifier (an ID number). Time runs in rounds: in one round every agent may talk to the agents on its node and then move along at most one edge. The task is to pick exactly one agent as leader: at the end the leader knows it is the leader and every other agent knows it is not, and we count the rounds and the bits of memory each agent needs. If all agents start on one node the task is easy (the smallest ID wins), so the interesting case is when they start with one agent on each node (a dispersed start), or in a few clusters.

1AlgorithmDisperse, then simulate message passing by visiting neighbours Knowing \(n\) and \(\Delta\) → Kshemkalyani et al. 2024

This is the idea behind every problem in this family. In the classic message-passing model, a computer sits still on each node and in each round sends a message to every neighbour. Agents can pretend to be such computers, provided there is one agent per node and neighbouring agents can meet once per simulated round. Here the agents know \(n\) and \(\Delta\).

  1. Disperse. Run a dispersion algorithm so that every node holds exactly one agent; that node is the agent's home. Knowing \(n\) tells the agents how long to wait before they can be sure dispersion is over.
  2. Pad the IDs. Each agent writes its ID in binary with the same number of bits, \(O(\log n)\), adding leading zeros (knowing \(n\) fixes this number).
  3. Meet every neighbour. Split time into blocks of \(2\Delta\) rounds, one block per bit. In block \(i\), an agent whose \(i\)-th bit is \(1\) visits its neighbours one by one (leave by port 1, come back, leave by port 2, come back, ...); an agent whose \(i\)-th bit is \(0\) stays at home. This meeting schedule is the ID-bit schedule.
  4. Two neighbouring agents have different IDs, so in some block one of them has bit \(1\) and the other bit \(0\): the first arrives while the second is at home, and they meet. A visitor recognises the agent at home as the one whose current bit is \(0\).
  5. Simulate. When two neighbouring agents meet they hand over the messages the message-passing algorithm would send along their edge. So one pass through all the blocks simulates one round of message passing.
  6. Run any message-passing leader election this way, for example one that needs \(O(D)\) rounds, where \(D\) is the diameter (the largest distance between two nodes).
Why it works and what it costs. A block lasts \(2\Delta\) rounds because a visit to a neighbour and back takes 2 rounds and there are at most \(\Delta\) neighbours. So one message-passing round costs \(O(\log n)\) blocks of \(2\Delta\) rounds, that is \(O(\Delta\log n)\) rounds, and a message-passing algorithm of \(R\) rounds costs \(O(\Delta R\log n)\) rounds, plus the time to disperse (\(O(n\log^2 n)\) rounds with the dispersion algorithm the paper uses Sudo et al. 2024). With an \(O(D)\)-round election this gives \(O(\Delta D\log n + n\log^2 n)\) rounds. The catch is memory: each agent must store whatever a message-passing node stores, which can be large; Kshemkalyani et al. 2026 reach a bound of the same form, \(O(n\log^2 n + D\Delta\log n)\), with only \(O(\log n)\) bits per agent.

Why it matters. It turns decades of message-passing algorithms into agent algorithms at a cost of a factor \(\Delta\log n\), and the ID-bit schedule is reused by almost every later paper on computing with agents.

2AlgorithmWalk every edge and come home No knowledge → Kshemkalyani et al. 2024

Without knowing \(n\) or \(\Delta\), the agents cannot use blocks of fixed length, and an agent that starts alone on its node does not even know whether the others are also alone. The first algorithm for this setting works as follows (simplified here for a dispersed start).

  1. Each agent visits its neighbours once and returns home. It stays a candidate only if its node has the smallest degree among its neighbours, with ties broken by ID; otherwise it gives up. At least one candidate survives.
  2. Each surviving candidate tells a neighbouring agent where its home is, so that others do not mistake its empty home for an unvisited node.
  3. Each candidate then performs a depth-first walk (it leaves by a port it has not tried yet when there is one, and otherwise goes back the way it came) that crosses every edge of the graph, carrying a tag (start round, ID).
  4. When two walks meet, the one with the smaller tag stops and its owner gives up.
  5. A candidate whose walk crosses every edge and returns home declares itself leader.
Why it works and what it costs. A depth-first walk crosses each edge at most twice (once out, once back), so it ends within \(O(m)\) rounds. The delicate part, which the paper proves, is that once one candidate declares itself leader no other can; this needs the home markers of step 2 and care when walks pass each other. When the agents start in clusters the same paper first disperses them with depth-first walks, and then needs \(O(n\log n)\) bits per agent. Later work brought the time down to \(O(n)\) rounds with \(O(\log n)\) bits Chand & Molla 2026, building on optimal dispersion Kshemkalyani et al. 2025.

Why it matters. It showed that leader election, and with it MST, MIS and dominating sets, can be solved with no knowledge of the graph at all, which is the setting all later papers aim for.

3ImpossibilityWhy the agents need distinct identifiers No knowledge →

Every setting in this catalogue gives the agents distinct IDs. Here is why. Take a ring of 6 nodes, one agent on each, and number the ports so that at every node port 1 leads clockwise and port 2 counter-clockwise. Suppose the 6 agents are identical (no IDs) and follow the same deterministic program. In round 1 they all see exactly the same thing, so they all do the same thing: all stay, or all move clockwise, or all move counter-clockwise. After the move each agent again sees exactly what every other agent sees. By the same reasoning round after round, all 6 agents are always in the same state. If one of them ever decides "I am the leader", all 6 decide it at the same moment.

Why it holds. So no deterministic algorithm elects a leader among identical agents on this ring, no matter how many rounds it uses or how much memory the agents have. The argument is a standard symmetry argument, not a result of a particular paper in this catalogue. Distinct IDs break the symmetry; the algorithms above use them both to decide who wins and, through the bits of the IDs (the ID-bit schedule), to schedule meetings.

Why it matters. Symmetry is the basic obstacle to leader election, and it explains why identifiers (or randomness) are part of every model in which leaders are elected.

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
Memory
No knowledge standard
Without any knowledge of the graph, leader election takes \(O(n)\) rounds with \(O(\log n)\) bits.
unknown \(O(n)\) vs —
unknown \(O(\log n)\) vs —
Knowing \(n\) and \(\Delta\)
With \(n\) and \(\Delta\) known, leader election takes \(O(n\log^2 n+D\Delta\log n)\) rounds with \(O(\log n)\) bits.
unknown \(O(n\log^2 n+D\Delta\log n)\) vs —
unknown \(O(\log n)\) vs —

What the community started looking at

The agent-based model asks what graph problems agents can solve on an anonymous network, with rounds first and memory second as the measures Kshemkalyani et al. 2024. Leader election came first because it unlocks the rest (MST, BFS trees, gathering).

Perspectives

  • Symmetry is the adversary Identical agents running the same deterministic program can be kept in lockstep forever. Across graphs, the plane and programmable matter, the papers break this symmetry with identifiers, with randomness, with asymmetric starts, or with the scheduler, and leader election keeps reappearing as the common core.
  • From exploration to dispersion, and beyond How collaborative exploration asks how much a team speeds up a search, how dispersion arose as the case k = n under weaker assumptions, what dispersion gives back to exploration, and why dispersing first has become the standard opening move for computing graph structures with agents.

All settings

The assumption tree (2 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, 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 › Communication › Timing › Knowledge › Initial configuration › Topology.

tight near-optimal polynomial gap unknown impossible no variant

Assumptions specific to this problem

Knowledge

0no knowledge of graph parameters1\(n\) and \(\Delta\) are known

Whether agents know global parameters is inherited from message passing, where nodes typically know \(n\) or an upper bound on it, and possibly \(\Delta\) and \(D\); Kshemkalyani, Kumar, Molla and Sharma set the agent-based model against this and asked for algorithms that rely on no such knowledge, "neither exact nor an upper bound" Kshemkalyani et al. 2024. Knowing \(n\) and \(\Delta\) tells an agent how long to wait: in the arbitrary-start minimal dominating set algorithm of Chand, Molla and Sivasubramaniam every robot waits \(\kappa n\Delta\) rounds before leader election begins Chand et al. 2023, and the introductory maximal independent set algorithm assumes both \(n\) and \(\Delta\) Pattanayak et al. 2024 (as reported by Kaur et al. 2026 and Kshemkalyani et al. 2024). Kshemkalyani et al. state the trade-off: solutions without knowledge "are more resilient to network changes and device faults", but "algorithm design becomes challenging since devices may not know how long to run a procedure to guarantee a solution" Kshemkalyani et al. 2024. Later papers remove the assumption by first dispersing with termination detection and electing a leader, after which a spanning tree lets the agents compute \(\Delta\) and the largest identifier themselves Chand et al. 2026; knowing only that largest identifier \(L\) is a weaker assumption, recorded on results rather than as a level of this axis Chand et al. 2025. For leader election both levels are catalogued: without knowledge Kshemkalyani et al. 2024 Chand & Molla 2026, and faster with \(n\) and \(\Delta\) known Kshemkalyani et al. 2026.

Formal definitions
0no knowledge
Agents know no graph parameter (\(n\), \(m\), \(\Delta\), \(D\)).
1knows \(n\), \(\Delta\)
Every agent knows \(n\) and \(\Delta\) (upper bounds suffice where stated).

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