Getting many nodes to agree on every operation is expensive: every decision needs a round of messages among all participants. A leader removes most of that cost. One process makes decisions, orders operations and coordinates the rest, and the others follow. The price is that the leader becomes a single point of failure, so the system needs a reliable way to notice when the leader is gone and to pick a replacement without ever ending up with two.

This chapter covers the classical election algorithms (bully, next-in-line failover, candidate/ordinary optimisation, invitation, ring), what each assumes and where each breaks, and then the modern view: safe leader election under partitions is itself an instance of consensus, which is why Raft, ZAB and Multi-Paxos fold election into their protocols and protect it with terms, leases and fencing tokens.

In one minute

• A leader is a process other participants defer to for coordination. It reduces message complexity from all-to-all to one-to-all and gives a single place to order operations.
• Election must satisfy liveness (an election eventually terminates with a leader) and safety (at most one leader is recognised at a time). Under partitions, the classical algorithms give up safety.
• Bully algorithm: the highest-ranked live process wins. Simple, but a partition yields one leader per side (split brain), and a flaky high-ranked node causes repeated elections.
• Next-in-line failover: the leader publishes an ordered list of successors; on failure the next candidate takes over with far fewer messages.
• Candidate/ordinary optimisation: only a small subset of nodes may become leader; ordinary nodes start elections but do not stand. Fewer messages, fewer simultaneous elections.
• Invitation algorithm: every node starts as the leader of a one-member group; groups merge when leaders invite each other, so multiple leaders coexist temporarily and converge.
• Ring algorithm: an election message circulates once around a ring collecting live node ids; the highest wins. O(n) messages but O(n) latency, and fragile under concurrent elections.
• In real systems (Raft, ZAB, Chubby, etcd, ZooKeeper), election is a consensus decision with a monotonically increasing term or epoch, a majority quorum, and fencing or leases so that a deposed leader cannot do damage.

Why elect a leader

Coordination cost without a leader

If every node must agree with every other node on every step, the message count grows with the square of the cluster size and the latency of every operation includes the slowest node. Protocols that avoid a leader exist (leaderless Paxos variants, Dynamo-style quorums) but they pay in contention or in weaker consistency.

What a leader does

A leader is a process that other processes recognise as the coordinator for some set of actions: ordering writes, assigning sequence numbers, handing out locks, driving a transaction's commit, or deciding membership. Having one such process means:

• Decisions require one round from the leader to followers instead of a round among everyone.
• There is a single serialisation point, which makes properties like a total order of writes straightforward.
• Followers can be simpler: they apply what the leader sends.

Consensus protocols such as Multi-Paxos, ZAB and Raft rely on a temporary leader for exactly this reason. The leader proposes values and replicates them in one round trip; without it, each value would need the full two-phase Paxos exchange with competing proposers.

When elections happen

An election runs when the system starts and has no leader, and whenever participants decide the current leader has failed. The second case depends on a failure detector (chapter 9), and inherits its uncertainty: a leader that is merely slow may be "replaced" while still running. Every serious election design has to answer what happens then.

Safety and liveness of election

The two properties are the same pair that frame every algorithm in this part, applied to elections:

• Liveness: the election eventually terminates, and most of the time the system has a leader. An algorithm that can run forever because of repeated conflicts fails liveness.
• Safety: at most one process believes it is the leader at any moment, and every other process agrees on who that is. The failure mode is split brain: two leaders accepting writes concurrently, diverging state and corrupting it.

Petrov's classical algorithms optimise liveness and message count and, as he notes, do not guarantee safety under network partitions. That is the central lesson of the chapter: a partitioned cluster running the bully algorithm will have two leaders. Preventing that requires either a majority quorum (which turns election into consensus) or an external arbiter such as a lock service.

Bully algorithm

Highest rank wins

Garcia-Molina's bully algorithm (1982) assumes every process has a unique rank (an identifier or priority) and knows the ranks of all other processes. The highest-ranked live process should be the leader; it "bullies" the rest into accepting it. The algorithm is also called monarchical leader election.

When a process P notices there is no leader (at startup, or because the leader stopped responding):

1. P sends an election message to every process with a higher rank than itself.
2. If no higher-ranked process answers within the timeout, P declares itself leader and sends a coordinator message to every lower-ranked process.
3. If one or more higher-ranked processes answer, P stops; the highest-ranked responder takes over and runs step 1 and 2 itself (or, in the simplest form, P defers to the highest responder and that process announces itself).

Problems

• No safety under partition. If the network splits, each side runs an election and the highest-ranked node on each side wins. Both accept writes. When the partition heals, the system has two histories to reconcile and no principled way to do it.
• Rank fixation. The highest-ranked node always wins, even if it is the one that keeps failing. A node with a flaky network link or a leak that crashes it every few minutes will win every election and be deposed every few minutes, generating constant churn and repeated unavailability.
• Message cost. A low-ranked initiator triggers messages to every higher-ranked node, and the winner broadcasts to everyone. With n nodes the worst case is O(n squared) messages when many nodes detect the failure at once.
• Timeout dependence. Step 2 relies on a timeout to conclude that higher-ranked nodes are dead, with all the false-positive risk of chapter 9. A slow high-ranked node that misses the timeout will later announce itself and depose the newly elected leader.

The next three algorithms are refinements aimed at the message cost and the churn; none fixes the partition problem.

Next-in-line failover

Successor list

Instead of letting every node contest the election, the current leader publishes an ordered list of failover candidates alongside its coordinator message. When a process detects that the leader has failed:

1. It contacts the highest-ranked candidate on the list.
2. If that candidate responds, it becomes the new leader and announces itself.
3. If it does not respond, the process tries the next candidate, and so on.
4. If the process itself is the highest-ranked live candidate, it takes over directly and notifies the others.

This cuts the election to a handful of messages in the common case, because the successor is already agreed in advance and only needs to be confirmed alive. It also lets the outgoing leader choose a successor ordering that reflects health or load rather than a static rank, which softens the churn problem of the pure bully algorithm.

Example: Chubby

Google's Chubby lock service keeps a small replica set (typically five) with one master. Replicas use a Paxos-based election to pick the master, and the master holds a master lease that followers promise not to contest while it is valid. If the master fails, the remaining replicas elect a new one when the lease expires. The failover-list idea shows up as the known set of replicas that are all eligible to take over, while the lease supplies the safety that the bully algorithm lacks.

Candidate/ordinary optimisation

Splitting roles

The next refinement separates nodes into two sets:

• Candidate nodes are eligible to become leader.
• Ordinary nodes can detect failures and start elections but never stand for leadership.

An ordinary node that suspects the leader sends an election message to all candidates, picks the highest-ranked candidate that responds, and announces the result to everyone. Candidates respond but do not initiate. Because the candidate set is small, each election exchanges far fewer messages than a bully round among all nodes, and because only ordinary nodes trigger elections there are fewer competing simultaneous rounds.

To avoid two ordinary nodes kicking off duplicate elections for the same failure, the scheme adds a short delay (the book calls it the delta parameter) before an ordinary node starts a round, giving an in-progress election a chance to complete first.

Example: ZooKeeper participants and observers

ZooKeeper has a direct analogue. Participants vote in leader election and acknowledge proposals; observers receive the replicated state and serve reads but neither vote nor stand for election. Observers let an ensemble scale read capacity across many nodes and data centres without slowing down election or commit, which depend only on the small participant set. The trade-off is that the candidate set is a configuration decision: lose all candidates and no election can succeed even if many ordinary nodes are healthy.

Invitation and ring algorithms

Invitation algorithm: groups that merge

Garcia-Molina's invitation algorithm (from the same 1982 paper) is designed for environments where partitions happen and the system should keep working inside each partition. It explicitly allows multiple leaders to coexist and then merges them.

• Every process starts as the leader of a group containing only itself.
• Periodically, a group leader contacts other processes and invites them to join its group.
• If the contacted process is itself a leader, the two groups merge into one.
• If the contacted process is a follower, it replies with its leader's identity so that the two leaders can negotiate a merge.
• When groups merge, the leader of the larger group normally becomes leader of the merged group, so the smaller group's members are the ones notified of the change, which minimises messages.

When a partition heals, the groups on each side simply discover each other and merge. The algorithm trades the single-leader invariant for availability inside partitions, so it only makes sense when the application can tolerate independent groups making independent decisions for a while and reconciling afterwards. That is the model behind partition-tolerant membership systems, and it is also why systems that need a single ordering of writes do not use it.

Ring algorithm: one pass around the ring

Chang and Roberts' ring algorithm (1979) arranges nodes in a logical ring; each node knows its successor. An election proceeds in a single pass:

1. A node that detects the leader's failure sends an election message to its successor, containing its own id.
2. If the successor does not respond, the sender skips it and tries the next node in the ring, continuing until a live node accepts the message.
3. Each node that receives the message adds itself to the live node set carried in the message and forwards it.
4. When the message returns to the initiator after one full traversal, the initiator picks the highest-ranked id in the set and sends a coordinator message around the ring announcing the new leader.

In the original Chang-Roberts variant, each node forwards only the maximum id seen so far rather than the whole set, and a node that receives its own id back knows it has won.

Ring properties

• Message count is O(n) for one election, better than the bully worst case, but latency is also O(n) because the message visits every node sequentially.
• Concurrent initiators create multiple messages circulating at once; the algorithm needs extra rules (drop messages carrying a lower initiator id) to converge.
• Like the bully algorithm, it has no answer to partitions: each ring segment elects its own leader.

Ring elections are mostly of historical interest; modern databases use consensus-based election.

How election relates to consensus

Election is a consensus decision

Choosing a leader means all participants agreeing on a single value (the leader's id for this period). That is the consensus problem of chapter 8, and it comes with the FLP caveat: it cannot be solved with guaranteed termination in a fully asynchronous system. The classical algorithms above achieve termination only because they rely on timeouts and assume failures are crashes rather than partitions. Raft, ZAB and Multi-Paxos take the opposite approach: they make election a consensus instance protected by a majority quorum, so safety holds under any partition and liveness holds when the network is eventually well behaved.

Terms and epochs

Each election in these protocols happens within a monotonically increasing term (Raft) or epoch (ZAB, Paxos ballot numbers). A candidate increments its term, votes for itself and asks the others for votes. Each node grants at most one vote per term and persists its vote to disk before answering. A candidate becomes leader only after collecting votes from a majority. Because two majorities always intersect and each node votes once per term, two leaders cannot be elected in the same term. A node that sees a higher term than its own immediately steps down to follower, so an old leader that was partitioned away cannot keep acting once it hears from the new majority.

Raft adds two details that answer the bully algorithm's problems. Randomised election timeouts make it unlikely that many followers become candidates simultaneously, which breaks split votes without ranks. And a voter only grants its vote to a candidate whose log is at least as up to date as its own, which guarantees the winner holds every committed entry; rank is replaced by "has the most complete log", which is what the system actually needs.

ZooKeeper's ZAB works similarly with an epoch embedded in the high bits of every transaction id (zxid), so any proposal from a previous epoch is recognisable and rejected. Multi-Paxos uses the ballot number of the Prepare phase as its epoch; a proposer that gets a majority of promises for a ballot is in effect the leader for that ballot.

Preventing split brain: quorums, leases and fencing

A majority quorum prevents two leaders from being elected in the same term. It does not by itself stop an old leader that has not yet heard about the new term from continuing to serve clients. Three mechanisms close that gap.

Quorum writes. If every write must be acknowledged by a majority, a stale leader partitioned away from the majority cannot commit anything. Its writes fail, and clients reading from the majority never see them. This is how Raft and ZAB stay safe even while a stale leader still believes it is in charge.

Leases. A leader holds a time-bounded lease and must renew it (by heartbeating a majority) before expiry. Followers do not start an election until the lease could have expired, and a leader stops serving when it cannot renew. Leases let a leader serve reads locally without a quorum round, at the cost of a clock-skew assumption: the lease must be measured so that the old leader's lease ends before the new leader starts, which is why implementations shrink the leader's view of the lease by a safety margin. Chubby's master lease and Raft leader leases in etcd and CockroachDB are examples.

Fencing tokens. When election is arbitrated by an external service (a ZooKeeper lock, a Chubby lock, a database row), the service hands the winner a monotonically increasing fencing token, typically the epoch or the lock's version number. The leader includes the token in every request to downstream resources (storage, a shared queue), and those resources reject any request whose token is lower than the highest they have seen. A deposed leader that wakes from a long pause and keeps writing is fenced out even if it never learns it lost. Martin Kleppmann's Redlock analysis is the standard argument for why a lock without fencing is not enough.

Election in the wild

System	Election mechanism	Epoch concept	Split-brain guard
Raft (etcd, Consul, TiKV, CockroachDB)	Randomised timeouts, majority votes, log-completeness check	Term	Majority quorum for commits; optional leader lease for reads
ZooKeeper (ZAB)	Fast leader election among participants; observers do not vote	Epoch in zxid	Majority acks; epoch rejects stale proposals
Multi-Paxos (Chubby, Spanner groups)	Prepare phase with ballot numbers; leader is the holder of the highest accepted ballot	Ballot number	Majority promises; master lease
Applications using a lock service	Acquire an ephemeral znode or lock; lowest sequence number is leader	Lock version	Fencing token checked by the downstream resource

Design trade-offs

Algorithm	Messages per election	Latency	Safe under partition	Handles flaky high-ranked node	Where it fits
Bully	O(n squared) worst case	One or two round trips	No	No, it keeps winning	Teaching; small trusted LANs
Next-in-line failover	O(n) to announce, O(1) to pick	One round trip	No	Partially, via successor ordering	Clusters with a known, stable successor list
Candidate/ordinary	O(candidates) per initiator	One round trip plus delta	No	Partially, candidates are chosen	Large clusters with a few eligible coordinators (ZooKeeper observers)
Invitation	Proportional to group merges	Converges over time	Yes, by allowing multiple leaders	N/A	Partition-tolerant membership where groups may act independently
Ring	O(n)	O(n) sequential hops	No	No	Historical; token-based group communication
Consensus-based (Raft, ZAB, Paxos)	O(n) per round, usually one round	One or two round trips plus randomised timeout	Yes, majority quorum	Yes, randomised timeouts and log checks	Every modern database that needs a single ordered log

When to pick what: if the system already runs a consensus protocol, use its election; it is the only option in the table that is safe under partitions. If the system does not and cannot run one (an application tier that just needs one active worker), delegate to a lock service that runs one (ZooKeeper, etcd, Chubby) and propagate its fencing token to every resource the leader touches. Know the classical algorithms for the design space and failure modes they expose, not to implement them.

Interview angle

• Why do distributed databases bother with a leader at all? A leader turns an all-to-all agreement into one-to-many replication: the leader orders operations and followers apply them, so each write needs one round trip instead of a multi-round negotiation among all nodes. It also provides a single serialisation point, which makes linearizable writes and a total-order log simple. The cost is a failover window and an election protocol.

• Explain the bully algorithm and its biggest weakness. A process that detects a missing leader messages all higher-ranked processes; if none respond it declares itself leader, otherwise it defers to the highest responder. Its biggest weakness is that a network partition produces one leader per partition, and the algorithm has no way to prevent or even detect that. A secondary weakness is that the highest-ranked node always wins, even if it is the node that keeps failing.

• What is split brain and how does Raft prevent it? Split brain is two nodes simultaneously acting as leader and accepting conflicting writes. Raft prevents it with terms and majority votes: each node votes once per term, a leader needs a majority, and majorities intersect, so there is one leader per term. A stale leader from an older term cannot commit because commits also require a majority, and it steps down the moment it sees a higher term.

• Is a majority election enough, or do you also need fencing? Majority voting prevents two leaders in the same term, but an old leader that has not yet observed the new term can keep issuing requests. If every operation goes through the quorum, those requests fail harmlessly. If the leader also writes to external resources (a blob store, a queue), those resources must check a fencing token (the term or lock version) and reject lower values. Otherwise a paused-and-resumed old leader can corrupt state.

• How do leader leases let Raft serve reads without a quorum, and what assumption do they add? The leader knows that no other leader can exist until its lease expires, because followers will not start an election before then. So within the lease it can answer reads locally. The assumption is bounded clock drift: the leader's lease timer must expire no later than the followers' timers, so implementations shorten the leader's view of the lease by a margin to tolerate skew.

• Design leader election for a service with twenty stateless workers where exactly one should run a scheduled job. Do not implement an election algorithm. Use an existing coordination service: each worker creates an ephemeral sequential node under a ZooKeeper path (or an etcd lease-backed key), the lowest sequence number is the leader, others watch their predecessor. Include the node's sequence number or etcd revision as a fencing token on every side effect the job performs, and make the job idempotent so that a brief double-run after a false failover is harmless.

Pitfalls and misconceptions

• "The bully algorithm guarantees a single leader." It guarantees one leader per connected component. During a partition that means several leaders.
• "Highest rank should win because it is the most capable node." Rank is arbitrary. A node that keeps crashing but has the highest rank will win every election and cause constant churn. Raft replaces rank with log completeness and randomised timeouts for a reason.
• "Once a node is elected, it stays the leader until it crashes." Any protocol that uses terms will depose a leader that cannot reach a majority, even if it is healthy. Leadership is a lease on a role, not ownership.
• "A distributed lock gives me mutual exclusion." Only if the resources protected by the lock verify a fencing token. A lock holder that pauses, loses the lock and resumes will otherwise act concurrently with the new holder.
• "Leader election and consensus are different problems." Election is consensus on a single value (who leads this term). Any election that is safe under partitions is a consensus protocol, whether or not it is called one.
• "Leases are free safety." Leases trade a quorum round for a clock assumption; skew larger than the safety margin breaks them.
• "If the leader is slow, replacing it quickly is always better." Aggressive failover plus an imperfect failure detector equals leader flapping. Each election costs availability; tune detection against the cost of a false positive.

Key terms

Term	Meaning
Leader	A process that other participants defer to for coordination, ordering or decision making
Leader election	The procedure by which processes agree on a leader at startup or after the leader fails
Liveness (of election)	An election eventually terminates and the system has a leader most of the time
Safety (of election)	At most one process is recognised as leader at any time
Split brain	Two or more leaders acting concurrently, typically one per partition
Rank	A unique priority assigned to each process; the bully algorithm elects the highest live rank
Bully algorithm	Highest-ranked live process declares itself leader after higher-ranked processes fail to respond; also called monarchical election
Next-in-line failover	The leader publishes an ordered successor list so failover needs only a confirmation of the next candidate
Candidate / ordinary nodes	Nodes eligible to lead versus nodes that only detect failures and start elections
Invitation algorithm	Processes start as single-member groups and merge by invitation; multiple leaders coexist and converge
Ring algorithm	An election message traverses a logical ring collecting live ids; the highest becomes leader
Term / epoch / ballot	A monotonically increasing number identifying one leadership period; one leader per number
Majority quorum	More than half the participants; any two majorities overlap, which prevents two leaders in one term
Randomised election timeout	Raft's technique for avoiding simultaneous candidates and split votes without fixed ranks
Lease	A time-bounded grant of leadership renewed by heartbeats; followers do not elect before it could expire
Fencing token	A monotonically increasing value issued at election that resources check to reject requests from stale leaders
Observer (ZooKeeper)	A node that replicates state and serves reads but neither votes nor stands for election
Log-completeness rule	Raft voters refuse candidates whose log is less up to date than their own, ensuring the winner holds all committed entries

Further reading

• Database Internals, Chapter 10; Chapter 14 for the consensus protocols that embed election.
• Garcia-Molina, "Elections in a Distributed Computing System", IEEE Transactions on Computers, 1982 (source of the bully and invitation algorithms).
• Chang, Roberts, "An Improved Algorithm for Decentralized Extrema-Finding in Circular Configurations of Processes", CACM 1979 (ring algorithm).
• Ongaro, Ousterhout, "In Search of an Understandable Consensus Algorithm" (Raft): https://raft.github.io/raft.pdf
• Burrows, "The Chubby Lock Service for Loosely-Coupled Distributed Systems", OSDI 2006: https://static.googleusercontent.com/media/research.google.com/en//archive/chubby-osdi06.pdf
• Junqueira, Reed, Serafini, "Zab: High-performance broadcast for primary-backup systems", DSN 2011.
• Apache ZooKeeper, "ZooKeeper Observers": https://zookeeper.apache.org/doc/current/zookeeperObservers.html
• Martin Kleppmann, "How to do distributed locking" (fencing tokens): https://martin.kleppmann.com/2016/02/08/how-to-do-distributed-locking.html
• Kyle Kingsbury's distributed systems class notes: https://github.com/aphyr/distsys-class