Leader Election in Distributed Systems: Methods and Split-Brain Risk

When a primary dies, the fleet has to promote a replacement itself; there is no operator in the room, and the availability budget is measured in seconds. That is the job description for leader election in a distributed system: the machinery underneath database replication failover, the first act of every consensus deployment, and the quiet dependency of systems that look nothing like each other (databases, message brokers, service meshes) all choosing one node to trust.

Election is also consensus’s most common application: one decision, visible to all, that everything else hangs off. The machinery that makes majority elections safe (quorum arithmetic, the FLP caveat) lives in distributed consensus, the comparison of algorithms in consensus algorithms, and Raft’s built-in election in the Raft consensus algorithm. This article covers election itself: the methods that predate consensus, the coordination-service recipes most systems actually deploy, and the split brain every one of them is trying to prevent.

Leader election is the process by which the nodes of a cluster choose one of themselves to act as coordinator (primary, master, captain) until it fails, and then choose again. Done right, at most one leader exists at any moment, and the cluster learns of the new one quickly. Done naively, two nodes both believe they are leader, and the split brain that follows quietly corrupts data.

What a leader is for and when you don’t need one

Clusters elect a leader for three overlapping reasons: to serialize decisions one node at a time, which makes mutual exclusion nearly free; to own the hard state (the write log, the lock table, the assignment of work) so the fleet has one place to look; and to pre-position a failover target with a known promotion path. A leader also concentrates cost: one node everyone can see is one node everyone can monitor, and “who is in charge?” has an answer.

Not every design pays that cost. Stateless tiers behind a load balancer elect nothing; any node serves any request, and a dead node is routed around, not replaced. Leaderless designs spread coordination across a quorum; Dynamo-family stores let any replica accept writes and reconcile later, buying partition-side availability at the price of conflict resolution. And a sharded fleet often wants many small leaders (one per shard) rather than one big one, which is why per-range elections inside distributed databases look nothing like the single-coordinator picture.

The rest of this article is for the designs that do need one, which is most of them, because the moment a fleet holds state, something has to decide who applies the next write.

Leader election algorithms

The methods divide by how much machinery they assume and which failure they fear:

• Bully algorithm: every node has a unique, ranked ID, and the highest-ranked live node wins by challenging all higher IDs into answering or staying silent. Simple to reason about, message-hungry, and blind to partitions.
• Ring elections: nodes pass an election message around a logical ring; each appends its own ID, and the message that returns carrying everyone’s IDs announces the winner to all. Orderly, but it takes rounds proportional to cluster size, and one lost message stalls it.
• Lease and heartbeat methods: leadership is a time-boxed grant, renewed by heartbeats and held until the grants stop arriving. What a lease cannot do is distinguish a dead leader from a slow one; expiry is a clock decision, not a fact.
• Quorum-based elections: a candidate wins only with votes from a majority of a fixed configuration, the same arithmetic that makes consensus safe. Raft and ZAB are built this way; the term number in Raft’s elections doubles as a fencing epoch, and the majority vote is what makes the claim to leadership real.

The first two families come from the 1980s literature and still live in textbooks and interviews. The last two are what production runs: either directly, as consensus protocols with elections inside them, or indirectly, by renting election from a coordination service. The next two sections cover the textbook classic and the rented-out version in depth, because each one teaches a failure the quorum methods were built to fix.

The bully algorithm

The bully algorithm (Garcia-Molina, 1982) is the textbook answer: give every node a unique numeric ID and let seniority rule. The name is the specification; the node with the highest ID bullies its way into office, on the theory that rankings are stable and known to all.

The protocol starts at any node that notices the leader is gone:

1. The noticing node sends an ELECTION message to every node with a higher ID.
2. If any higher node answers, the noticing node stands down; the responders will take it from there, and the highest of them will finish the job.
3. If no higher node answers within a timeout, the noticing node declares itself leader and sends a COORDINATOR announcement to everyone below it.
4. A node that receives an ELECTION message answers, and starts its own round if it also believes the leader is dead.

On a friendly network the cascade terminates: the highest-ID live node eventually announces itself, everyone falls in line, and the election costs a bounded storm of messages, on the order of n² in the worst case, when every node notices the failure at once and the rounds restart inside each other.

The problems are the assumptions. Seniority is arbitrary; the highest ID says nothing about which node has the most recent data, the most capacity, or the fewest competing jobs. The timeouts are guesses, and a cluster under load votes repeatedly on pauses it cannot diagnose. Worst, the algorithm is partition-blind: two disconnected groups each conclude that their own highest-ID survivor is the leader, and both keep serving, a textbook-perfect setup for the split brain covered below. Bully lives on in interviews and small clusters where an operator can see the whole room; production systems mostly keep its ranking idea and replace its assumptions.

Zookeeper leader election

The pattern most systems actually deploy is to rent the hard part. ZooKeeper (a coordination service built on its own consensus protocol, ZAB, covered in consensus algorithms) provides the ingredients: durable shared nodes, ephemeral nodes that vanish when the owning client’s session dies, and notifications when a watched node disappears. Leader election becomes a recipe:

1. Every candidate creates an ephemeral, sequential znode under a known path (/election/n_0000000001, /election/n_0000000002, and so on) holding its own node ID or address.
2. Each candidate reads the path’s children and checks its own number. The lowest sequence wins: that node is the leader, and it knows so without a single extra message.
3. Every other candidate sets a watch on the child immediately below its own, never on the leader, never on the whole directory.
4. If the leader dies, its session dies with it, ZooKeeper deletes its ephemeral znode, and exactly one watch fires; the candidate just below, which re-runs step 2 and promotes itself.
5. The recipe continues down the list. One death, one watch, one promotion; no election storm, and no cleanup code, because ephemeral nodes do the janitor’s work.

Two details in that recipe are load-bearing. Sequential numbering makes leadership a comparison instead of an argument: no voting rounds, no dueling candidates. Watching only the immediate predecessor avoids the herd effect: if every candidate watched the leader, one death would wake the entire fleet and stampede the coordination service; watching one node each wakes exactly one process. etcd runs the same shape over Raft instead of ZAB (candidates take a lease on a key and renew it, and the lease expires when the holder dies) so zookeeper leader election and etcd leader election are one recipe over two different consensus engines. What the engines add, and the recipe alone cannot give, is the split-brain defense, the next section.

Split brain: two leaders are worse than none

Split brain is the state in which two nodes simultaneously believe they are the leader of the same cluster, each accepting writes the other never sees. The term comes from medicine for a reason: one body, two minds, both issuing orders. It is not a crash mode (a crashed leader is a clean failure) but a disagreement mode, and it is worse than useless. Both halves keep serving, both logs keep growing, and the damage is discovered only when the partition heals and the two histories cannot be reconciled.

The sequence that produces it is almost always the same. The cluster partitions. On the majority side, the election runs: the leader is unreachable, a replacement is chosen, traffic continues. On the minority side, the old leader is alive and still serving, because from where it sits, a partition is indistinguishable from a slow network, and heartbeats fail to arrive either way. This is the failure-detection trap from distributed consensus: slow and dead cannot be told apart without a quorum’s testimony, and the minority side has no quorum to consult.

Which points to the two-part defense. First, make election quorum-dependent: a leader is valid only with votes from a majority of the full configuration, so the minority side structurally cannot elect one and must stand down and refuse writes: the consistency-versus-availability trade-off, chosen at election time. Second, fence the deposed: because the old leader does not know it lost, every action it takes must carry evidence of its era (a term number, an epoch, a fencing token) and the systems on the other end must reject evidence from an older era on sight. Raft’s terms work exactly this way: a leader from term 4 is ignored the moment any node has seen term 5. Storage writes carry the same defense as fencing tokens, whose mechanics belong to distributed locks.

Skipping either half fails quietly. Two primaries accepting writes across a partition produce conflicting histories, and if both survive to the merge, one must be discarded wholesale or merged by hand. Split-brain incidents rarely end in a lost election; they end in lost data, found hours later by reconciliation jobs. The recipes in the previous section give a cluster its election; the quorum rule and the fencing are what keep that election honest.

Leases and fencing

Most production elections end with a lease: the leader holds office for a bounded term, renews it on a heartbeat, and loses it automatically when renewal stops. The idea (Gray and Cheriton, 1989) elegantly turns a liveness question into a clock question, but clocks are exactly where the elegance leaks. A lease is only safe if it expires later than the worst case for its renewals: a leader whose process pauses, a heartbeat that queues behind a garbage collection stop, a network that delays without dropping. Every lease period is therefore a bet on bounded clock drift, and the bet loses quietly on a VM that pauses for migration or a scheduler that throttles the leader mid-renewal.

The engineering answer is to stop trusting the lease alone and pair it with fencing. Leadership grants a fencing token (a number that only increases across elections (term 4, term 5, term 6)) and every write the leader issues carries its token. Storage rejects any write bearing a stale token, so a deposed leader that wakes mid-write, lease long expired and renewal refused, discovers its token is worthless instead of discovering that it corrupted the log. The token is Raft’s term machinery seen from the election side; how tokens apply to locks (and the Redlock debate over whether leases alone are ever enough) belongs to distributed locks.

One distinction is worth making before the FAQ: elections as recipe versus elections as protocol. The ZooKeeper recipe rents an outcome from a consensus engine; a black box that answers “who leads?” but does not tell the rest of the system to distrust the old answer. Consensus-grade elections are welded to the protocol that consumes them: Raft’s term numbers travel in every message the leader sends, so fencing is not a discipline the application must remember; it is the data format. Systems that elect by recipe and then forget to fence get the election right and the split brain anyway. Systems that elect by protocol get both, because the election’s evidence never leaves the message.

Common mistakes

• Electing without a quorum. A minority that promotes a replica by node count alone has not elected a leader; it has scheduled a split brain. Election must require a majority of the full configuration, and the minority side must stand down.
• Timeouts tuned to the happy path. A failure detector set at 100 ms will fire on every garbage collection pause and load spike, promoting a new leader while the old one lives, the opening move of most split-brain stories. Timeouts belong at several multiples of the observed worst case, not the average.
• No fencing on writes. Elections get all the attention; the fence is what protects data. A leader whose writes carry no token is a leader whose removal nobody enforces.
• Non-ephemeral leadership nodes. A coordination-service recipe that creates a plain znode instead of an ephemeral one leaves the leadership record behind after a crash, and a fleet that obediently refuses to elect because the record says someone holds office. Ephemeral is not an optimization; it is the cleanup story.
• Assuming election transfers state. A newly promoted primary is a leader with a stale copy until it catches up. Promotion without replication-lag checks (covered in database replication) hands the crown to the node least ready to wear it.

FAQ

How do ZooKeeper and etcd differ for leader election?
Under the hood, ZooKeeper elects with ZAB and etcd with Raft, but from the application side both run the same recipe: a leadership record held under a session, watched by the other candidates, and deleted automatically when the holder dies. The practical differences are client ergonomics (ephemeral znodes and watches versus leases and concurrency keys) and which consistency engine the rest of the stack already depends on.

Can leader election work with an even number of nodes?
A cluster can run any node count, but majorities behave better on odd ones. With 4 nodes a majority is 3, so the cluster tolerates exactly 1 failure: the same tolerance as 3 nodes, which cost less. With 5, a majority is 3 and the cluster tolerates 2. Even counts buy nothing for elections, which is why nearly every consensus deployment runs an odd-sized cluster. The arithmetic is covered in distributed consensus.

If two nodes both think they are the leader, what actually happens?
Whatever the fencing allows. With quorum-based election and fenced writes, the stale leader’s actions are rejected on sight and the worst outcome is a burst of errors. Without fencing, both sides keep writing and the damage surfaces at merge time; two divergent histories of which at most one can survive. Split brain is not an event; it is a window, and its size is the gap between “lost the election” and “found out.”

Does every distributed system need a leader election?
No. Stateless services behind a load balancer route around failures instead of electing through them, and leaderless stores spread writes across a quorum and reconcile conflicts later. Elections belong where one node must own a decision (a write log, a lock manager, a work queue) and even then some systems appoint their leader out-of-band at deploy time, trading automatic failover for operational simplicity.

What is the difference between leader election and distributed locking?
Leader election answers “who is in charge of the cluster”; a distributed lock answers “who holds this resource right now.” Elections are usually long-lived and system-wide, locks are usually short-lived and per-resource, but the machinery rhymes, because both are leases with fencing underneath. Locks, Redlock, and fencing tokens are covered in distributed locks.

Related articles

• Next read: distributed locks; the close cousin this article set up: who holds the lock, lease semantics, fencing tokens, and the Redlock debate.
• the Raft consensus algorithm: the consensus-grade election most modern systems actually run, term machinery included.
• distributed consensus, why majority elections are safe: quorum arithmetic, FLP, and the slow-versus-dead problem.
• fault-tolerant systems; failure detection and failover, the judgment every election depends on.
• service discovery, where the leader list gets published, and what clients do when it changes.