Skip to content
Tutorials Center
My learning

Topics

Lesson 20 of 36 ยท Consensus and Coordination

Leader Election

Learn how a cluster picks one leader: the bully and ring algorithms, terms and epochs, split brain, and fencing tokens. Includes a runnable simulation.

Many distributed systems work best when exactly one node is in charge. One node orders the writes, one node hands out work, one node owns a shard. A single decision-maker is simple to reason about. The hard part is that the decision-maker is a machine, and machines crash. When it does, the rest of the cluster must agree on a replacement, quickly, and without ending up with two bosses.

That process is leader election. This lesson covers the classic algorithms, the idea of terms (also called epochs), and the most dangerous failure of all: split brain, where two nodes both believe they are the leader. You will run a bully election and see how fencing tokens protect your data even when an election goes wrong. It builds on failure detectors and heartbeats, which are how the cluster notices that a leader is gone in the first place.

What an election must guarantee

Whatever algorithm you pick, a good election gives you two properties:

  • Safety: at most one leader is recognized at any time (or, more realistically, at most one leader per term).
  • Liveness: if the current leader fails, a new leader is eventually chosen.

Safety is the one you cannot give up. A cluster with no leader for a few seconds is slow. A cluster with two leaders corrupts data.

Why have a leader at all?

One order A single node decides the order of writes.
Less coordination Followers just obey instead of negotiating every request.
Simple logic No conflicts to merge when one node writes.

The price is an election whenever the leader dies.

1 / 2

The bully algorithm

The bully algorithm assumes every node has a unique, comparable ID and that the highest ID alive should lead. It is called the bully because the strongest node always wins.

When a node notices that the leader is unresponsive, it starts an election:

  1. It sends an ELECTION message to every node with a higher ID.
  2. If nobody answers within a timeout, it wins and announces itself with COORDINATOR messages to everyone.
  3. If a higher node answers with OK, the sender steps back. The higher node then runs its own election.

The rule repeats upward until the highest alive node hears no answer and takes over. In the example below there are five nodes. Node 5 was the leader and has crashed. Node 2 is the first to notice.

Python Bully election after the leader crashes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the output from the top. Node 2 contacts 3, 4 and 5. Nodes 3 and 4 answer, node 5 is silent because it is crashed. Node 3 then asks 4 and 5, and node 4 asks only 5. Nobody answers node 4, so node 4 becomes leader and informs nodes 1, 2 and 3.

The weakness is visible too: the number of messages grows quickly when a low-numbered node starts the election, because every higher node runs its own round. In the worst case the algorithm sends O(nยฒ) messages. It also assumes a reliable failure detector. If a slow node 5 comes back and answers late, it will bully its way back in, and the cluster may change leaders twice.

The ring algorithm

In the ring algorithm the nodes are arranged in a logical ring, and each node only talks to its successor. A node that notices the failure sends an ELECTION message around the ring carrying a list of IDs. Every node adds its own ID and passes the message on, skipping dead successors. When the message returns to the starter, it knows every live ID, picks the highest as leader, and sends a COORDINATOR message around the ring.

The ring needs only about 2n messages in a single election, and it needs no all-to-all connections. But it is slow, since messages travel node by node, and a node failing in the middle of an election can break the chain. Real systems rarely use a pure ring. They usually build elections on top of consensus, which you will meet in the next lesson.

Terms and epochs

Bully and ring assume the world stops while an election runs. In reality, messages are delayed and nodes pause. The fix is to number leadership periods. A term (Raft's word) or epoch (ZooKeeper's and many others') is an integer that increases with each election:

  • Every message carries the sender's term.
  • A node that sees a higher term than its own immediately adopts it and steps down if it was a leader.
  • A node that sees a lower term ignores the message: it comes from a stale leader.

With terms, an old leader that wakes up after a pause is corrected the first time it hears from anyone. You will see this in detail in Raft. A common rule is to allow at most one leader per term, enforced by letting each node vote only once per term.

Split brain

Imagine a network cable fails and a five-node cluster is cut into groups of three and two. If both groups hold elections independently, both elect a leader. Clients connected to either side keep writing. When the network heals, the two histories conflict. That is split brain.

The standard defense is a majority quorum: a node becomes leader only if it gets votes from more than half of all nodes in the cluster, not half of the nodes it can reach. Of the groups of three and two, only the group of three can win. The group of two stalls, which is correct: it is better to be unavailable than to be wrong. This is the same trade-off described in CAP and PACELC.

A majority quorum stops two nodes being elected at once. It does not stop an old leader, which has not yet learned it was replaced, from acting. That old leader may have been frozen by a garbage-collection pause or a slow disk. For that you need fencing.

Fencing tokens

A fencing token is a number that increases every time leadership changes. Each election returns a new token, which is usually just the term. The leader attaches its token to every write it sends to a resource. The resource remembers the highest token it has seen and rejects anything lower.

That moves the safety check from the (possibly confused) leader to the resource, which is the only party that can see the whole story. The simulation below runs the same story twice: once with no fencing, and once with the storage checking tokens.

Python Fencing tokens stop a stale leader

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Without fencing, the stale write from A lands last and silently overwrites B's newer data. With fencing, the storage compares token 1 with the highest token it has seen (2) and rejects the write. A's pause could be arbitrarily long and the result would be the same.

The idea comes up again in distributed locks and leases, where a lock service plays the role of the election and a token protects the resource.

Practical advice

  • Don't write your own election for production. Use a system that already runs consensus (etcd, ZooKeeper, Consul) and take a leader lease from it.
  • Keep election timeouts well above your typical network round trip, and add random jitter so that two nodes don't start elections at the same instant.
  • Always check what the protected resource does with a leader's writes. If it cannot check a token, the election alone does not make it safe.
  • Plan for the old leader's return: it must step down on seeing a higher term.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In the bully algorithm, which node becomes the leader?

    Every node that receives an ELECTION message from a lower ID answers and takes over, so the election climbs until the highest alive ID hears no reply.
  2. 2. What does a majority quorum prevent during an election?

    Only one group can contain more than half of all nodes, so at most one side of a partition can collect enough votes.
  3. 3. A stale leader wakes up after a long pause and sends a write. How do fencing tokens help?

    The resource, not the paused leader, keeps the highest token and rejects older ones. That protects the data even if the old leader is confused.
  4. 4. What does a node do when it receives a message with a higher term than its own?

    A higher term proves a newer leadership period exists, so the node must update its term and stop acting as leader.

Summary

  • Leader election picks one node to coordinate and replaces it when it fails; safety (at most one leader) matters more than speed.
  • The bully algorithm elects the highest alive ID; the ring algorithm passes a list of IDs around a logical ring.
  • Terms or epochs number leadership periods so stale leaders are recognized and corrected.
  • A majority quorum prevents split brain during elections; fencing tokens protect resources from old leaders that have not noticed they were replaced.
  • In practice, use an existing consensus-based service for leases and elections.

Next: Consensus and Paxos.