Leader Election Visualization | Bully vs Ring (Chang

The idea: when the leader dies, agree on a new one

Many distributed systems let one node, the leader (or coordinator), make the decisions: it orders writes, hands out locks or assigns work. When it crashes, the others must pick a new leader, and every live node must end up agreeing on the same one. That is leader election. The two classic algorithms on this page give every node a unique id and pick the highest id that is still alive. They differ in how they find it: the Bully algorithm asks every higher node directly, the ring algorithm of Chang and Roberts sends one token around a ring.

Time runs down. Nodes 3, 4, 5 and the crashed 6 are columns. 3 sends ELECTION to 4, 5 and 6; the one to 6 is lost. 4 and 5 answer OK to 3. 4 sends ELECTION to 5 and 6, 5 sends ELECTION to 6; 5 answers OK to 4. No OK reaches 5, so after its timeout 5 sends COORDINATOR to 1, 2, 3 and 4. — Bully, Demo 1: every OK hands the election to a higher node, and the node that hears no OK is the winner.

On the page	Meaning
circles 1 to 6	nodes, labelled by id; green = leader, orange = in an election, yellow = got OK and waits for the winner, grey = down
row (Bully)	nodes sorted by id; ELECTION boxes fly right above the row, OK and COORDINATOR fly left below it
ring (Chang–Roberts)	arrows show the direction (clockwise); a down node is skipped
right panel	messages of the current election by type, the total since reset, and the leader each node believes in
`t`	the clock: a message sent at tick t arrives at t + 1

Noticing that the leader is gone

Nobody tells the others that a node crashed. Each node sends the leader heartbeats (or expects them) and starts an election when they stop for longer than a timeout. The page does not draw the heartbeats: Start Election means "this node's heartbeats to the leader just timed out". Both algorithms assume this failure detector is right, which is only true in a synchronous system, where message delays have a known upper bound. How a large cluster detects failures without asking one node to watch everybody: Gossip and SWIM.

The Bully algorithm

Garcia-Molina described it in 1982. Every node knows the ids of all the others. A node that notices the failure:

sends ELECTION to every node with a higher id. It does not know which of them are alive, so a message to a crashed node is simply lost;
a live higher node answers OK ("I am alive and bigger, I take over") and starts its own election, unless it is already in one;
a node that gets an OK stops and waits for the result; if no result comes in time, it starts again;
a node that gets no OK within its timeout (2 ticks here: one tick there, one back) knows that every higher node is down. It is the leader and sends COORDINATOR to every lower id.

The name comes from the last rule's consequence: the biggest live node always wins, and it pushes everybody else aside. Demo 1: node 3 notices that 6 is gone; 4 and 5 answer OK and take over; 5 hears nothing from 6 and wins with 13 messages.

How many messages Bully needs

It depends on who notices. If the second-highest node notices, it sends one ELECTION (to the dead leader), hears nothing and sends COORDINATOR to the n − 2 others: about n messages. If the lowest id notices, every node starts an election in turn and each one sends ELECTION to all nodes above it: about n²/2 ELECTION messages plus as many OK replies. Demo 2 shows that worst case with 6 nodes: 15 + 10 + 4 = 29 messages, against 13 in Demo 1. The time is short in both cases (a few ticks), because the messages of one tick travel in parallel.

The ring algorithm (Chang–Roberts)

Here the nodes form a logical ring and every node only talks to the next one clockwise. Chang and Roberts (1979) improved an earlier ring algorithm by Le Lann, which carried a list of every id around the ring:

the starter marks itself as a participant and sends ELECTION(its id) to the next node;
a node that gets a larger id passes it on (and joins);
a node that gets a smaller id puts its own id in instead, the first time; if it has already joined, it drops the message, because a token with a larger id is already on its way;
a node that gets its own id back knows its token passed every live node: it has the largest id and is the leader. It sends ELECTED(id) once around, so everyone learns the result.

Six nodes on a ring, clockwise 1 to 6, with 6 crashed. Node 2 starts: ELECTION(2) to 3, which sends ELECTION(3) to 4, then ELECTION(4) to 5, then ELECTION(5) skips 6 and goes to 1, then on through 2, 3 and 4 back to 5. 5 sees its own id, becomes leader and sends ELECTED(5) once around the ring. — The token always carries the largest id it has passed, so it returns to its owner only if that owner has the largest live id.

A crashed node is skipped: the sender passes the message to the next live node (a real ring notices the dead neighbour from a missing acknowledgement). Demo 5: node 2 starts; the token becomes 3, 4 and 5, goes round to 5 again, and ELECTED(5) makes one more lap: 8 + 5 = 13 messages, one hop per tick.

Bully vs Ring

	Bully	Ring (Chang–Roberts)
who talks to whom	everyone with everyone (needs every id)	only the next live node
messages, one starter	about n (best) to n² (worst)	between 2n and 3n
messages, all start at once	O(n²)	O(n log n) on average, O(n²) worst
time	a few ticks plus one timeout	up to 3 laps of the ring: grows with n
needs timeouts	yes, to decide "nobody higher is alive"	only to skip a dead neighbour
a node comes back	the highest one takes over at once	a new election runs round the ring

Several starters

Two nodes often notice the failure at the same moment. Neither algorithm breaks. In Bully every OK silences a lower node, so only the highest live node can survive its timeout (Demo 3: 2 and 4 start together, 5 still wins). In the ring, every token except the one with the largest id is dropped by some node that has already joined with a larger id (Demo 6: 4 drops ELECTION(3)). Exactly one token gets home, so there is exactly one winner.

A crashed node comes back

A node that restarts does not know the current leader, so it holds an election. In Bully, if its id is the highest, it skips the questions and sends COORDINATOR at once (Demo 4: 6 returns and 5 steps down after only 5 messages). That keeps the rule "highest live id leads", but every restart of the top node moves the leadership again, which costs a handover each time. Systems that want a stable leader do not let a returning node take over unasked.

The weak spot: timeouts that lie

Both algorithms trust the failure detector. In a real network a slow or cut-off leader looks exactly like a dead one. If node 6 is only partitioned away, the others elect 5 while 6 still believes it leads: two leaders, or split brain. Bully and Chang–Roberts have no way to stop the old leader. Modern systems therefore elect with a majority vote and number every leadership with a term or epoch, so that a stale leader's requests are rejected: see Raft and Paxos, and the CAP theorem for why the minority side has to stop. Redis Sentinel shows a vote-based failover in practice.

See also Raft vs Multi-Paxos: how the two consensus protocols elect a leader, and why Paxos needs an extra election rule.

What the page leaves out

Heartbeats and the failure detector itself (Start Election stands for a timeout that already happened); message loss other than to a crashed node; nodes that crash in the middle of an election (an action always runs to the end); real timeouts, which must cover the slowest round trip; the ring's acknowledgements, which are how a node learns that its neighbour is dead; Le Lann's and the Hirschberg–Sinclair ring algorithms (the latter guarantees O(n log n) messages); elections by majority vote with terms, which is what Raft, ZooKeeper (ZAB) and etcd do; and leases that let a leader know when it may still act.