Leader election

Imagine 10 servers running the same code. They share a database. They need to run a nightly cron. If all 10 run the cron, you charge every customer 10 times. If none of them does, you don't bill anyone. You need exactly one to run it. Which one? And what happens when that one crashes halfway through?

This is the leader election problem — the distributed version of "pick a boss." It sounds simpler than consensus. It isn't. Every solution has to answer three questions: (1) How do we pick a leader when there isn't one? (2) How do we detect the leader has died? (3) How do we prevent two nodes from thinking they're both leader at the same time ("split brain")?

There are 4 industrial answers to these questions: Bully (Garcia-Molina, 1982), Ring (Chang & Roberts, 1979), Raft-style randomized timeout (Ongaro, 2014), and Lease-based (Chubby / etcd). Each makes a different trade-off. Every production system picks one.

The four industrial patterns

The Bully algorithm — deterministic priority

Garcia-Molina's 1982 algorithm. Every node has a unique priority ID (usually just a number). The rule is stupid-simple: the highest-priority live node wins. If you notice the leader is gone, you send an ELECTION message to every node with higher priority than you. If any of them respond, they "bully" you out — one of them takes over the election. If none respond, you're the highest live node and you declare yourself leader with a COORDINATOR message.

Bully is deterministic (given who's alive, exactly one node wins) but chatty — worst case is O(N²) messages. It relies on reliable failure detection — if you incorrectly think a higher-priority node is dead, you start an election it'll interrupt. Not great for large clusters or unreliable networks.

The Ring algorithm — pass the token

Chang & Roberts 1979. Every node knows the address of the next node in a logical ring. When a node notices the leader is gone, it starts an election by passing an ELECTION message with its ID clockwise. Every receiver replaces the message's ID with its own if higher, then forwards. When the message returns to the initiator, the highest ID is the winner. A second pass carries the winner's ID as the COORDINATOR announcement.

Ring is O(N) messages — much cheaper than Bully. But it's fragile: if any node in the ring dies mid-election, the message never returns. Real deployments use ring only for small, stable-membership clusters (Cassandra used it in the past for certain internal elections).

The Raft-style randomized timeout

The pattern we saw in the Consensus concept. Every follower waits 150-300ms for a heartbeat. If it doesn't come, follower becomes candidate, bumps its term, votes for itself, requests votes from others. Majority wins. Randomization prevents split votes. This is what etcd, Consul, CockroachDB, TiKV, and Kafka KRaft all use — it's the modern default.

Two properties are key: monotonic terms (a higher term always beats a lower one, so stale leaders auto-demote when they see a higher term) and random timeouts (spread out election attempts so exactly one candidate wins per round with high probability).

The Lease-based approach

Popularized by Chubby (Google, 2006) and copied by etcd, ZooKeeper, and every modern coordination service. A leader holds a lease — a time-limited grant of leadership, say 10 seconds. The leader must renew the lease before it expires; if it fails to renew (crash, network partition), the lease expires and any other node can acquire it.

The genius of leases is that they turn leader election into a single atomic operation: acquire the lease. Whoever gets the lease is leader. If nobody has the lease, someone can take it. Split brain becomes impossible if you respect the lease timeout — because when leader-A's lease expires, leader-A must stop acting as leader (because it can't know if someone else already took over). This is why leases require clock sync — you're trusting the clock to tell you when your lease is up.

The split-brain trap

Every leader election protocol has to prevent split brain — two nodes simultaneously believing they're leader. The failure modes are subtle:

• Bully — Assumes failure detection is reliable. If node A thinks node B (higher priority) is dead because of a network hiccup, A elects itself. When B is reachable again, both think they're leader.
• Ring — Same failure mode as Bully, plus the election message can get lost mid-ring.
• Raft — Prevents split brain via terms: a leader in term N stops accepting writes the moment it sees term N+1. But it needs a stable majority to elect a new leader — minority partitions can't elect.
• Lease-based — Prevents split brain via clock: leader stops acting as leader when its lease expires. Needs clock synchronization (bounded drift).

Applied in real systems

Key takeaways

• 4 industrial patterns: Bully (deterministic priority), Ring (token-pass), Raft (randomized timeout + terms), Lease-based (time-limited grant).
• Bully and Ring are historically important but rarely used in modern production — they rely on reliable failure detection.
• Raft-style is the default for consensus-based systems (etcd, CockroachDB, Kafka KRaft).
• Lease-based is the default for coordination services (Chubby, etcd, Kubernetes). Simpler mental model, requires clock sync.
• Every protocol must prevent split brain — the scenario where two nodes both believe they're leader. Terms (Raft) or leases (Chubby) are the two mechanisms that actually work at scale.
• Leases need bounded clock drift. If clocks disagree by more than the lease duration, split brain becomes possible.

References

• Chang & Roberts (1979) — "An Improved Algorithm for Decentralized Extrema-Finding in Circular Configurations of Processes." The Ring algorithm.
• Garcia-Molina (1982) — "Elections in a Distributed Computing System." The Bully algorithm.
• Burrows (2006) — "The Chubby Lock Service." OSDI 2006. The lease-based reference.
• Ongaro & Ousterhout (2014) — The Raft paper.
• Kubernetes client-go leaderelection package source code — the industrial implementation of etcd-lease-based election.