Leader Election
Many distributed systems require a single coordinator: the Kafka controller that assigns partitions, the primary database that accepts writes, the scheduler that prevents duplicate job runs, the lock server that serializes access.
Leader election is the process by which distributed nodes agree on a single leader from among themselves — and then recover by electing a new one when the current leader fails.
This page is the conceptual overview: what an election must guarantee, the classical algorithms, the three ways production systems actually elect leaders (built-in consensus, a coordination service, or a lease in a shared store), and — most importantly — what goes wrong, walked through as concrete failure timelines. For a longer, implementation-heavy companion with Kubernetes and graceful-transfer details, see Leader Election in the consensus section.
Why You Need a Leader
Not all distributed systems need a leader. Leaderless systems (Cassandra, Dynamo) avoid the complexity entirely. But a leader simplifies:
- Serialization — one node orders all operations, no conflicts
- Coordination — one node makes decisions others follow
- Consistency — reads from the leader always see the latest writes
The cost: the leader is a single point of bottleneck and a single point of failure. Leader election is the mechanism that handles the failure case.
"Reads from the leader always see the latest writes" needs a qualifier
That is only true if the node really is still the leader. A leader that has been partitioned away and replaced, but has not yet noticed, will happily serve stale reads. Raft handles this with ReadIndex or lease-based reads; a naive "read from whoever thinks they are leader" does not. The worked timelines below show exactly how this happens.
Most strongly consistent systems are leader-based for these reasons (Raft, Multi-Paxos, ZAB, Viewstamped Replication), and why most leaderless systems (quorums and leaderless replication) give up strong consistency in exchange for not having one.
Requirements
A correct leader election algorithm must guarantee:
- Safety — At most one leader at any time (no split-brain)
- Liveness — A leader is eventually elected if enough nodes are up
- Validity — The elected leader is a live node
These map directly to the consensus problem. Leader election is a form of consensus — agreeing on the value "which node is the leader."
"At most one leader at any time" — at which time?
The safety property as written above is the intuitive one, and it is not achievable in a real asynchronous network. There is no global clock, and a node cannot know instantly that it has been replaced. What real algorithms guarantee is weaker and more precise:
At most one leader per epoch (term, ballot, view, zxid epoch, generation). Epochs are totally ordered, and any action taken under an old epoch is rejected by everyone who has seen a newer one.
Under this definition, two nodes can both believe they are leader at the same wall-clock instant — an old one in term 7 and a new one in term 8. The system stays safe because the term-7 leader cannot get a majority to accept anything once a majority has moved to term 8. This shift — from "one leader in time" to "one leader per epoch, plus enforcement" — is the single most important idea on this page. Everything about split brain and fencing follows from it.
| Property | Naive version | What production algorithms actually provide |
|---|---|---|
| Safety | Never two leaders at once | At most one leader per epoch, and stale epochs are rejected |
| Liveness | A leader is always elected quickly | A leader is eventually elected once the network behaves (partial synchrony) |
| Validity | The leader is alive | The leader was alive and reachable by a majority when elected |
Why liveness cannot be unconditional
Because election is consensus, the FLP impossibility result applies: in a fully asynchronous system with even one crash failure, no deterministic algorithm can guarantee that an election always terminates. In practice this shows up as repeated split votes or flapping leadership during bad network periods. Every practical algorithm relies on timing assumptions (timeouts) for liveness while keeping safety independent of timing. See system models for the synchrony assumptions involved.
Leader Election Is a Failure-Detection Problem First
Before any algorithm runs, someone has to decide that the current leader is gone. That decision comes from a failure detector, and failure detectors in real networks are unreliable: a timeout cannot distinguish a crashed node from a slow one, a paused one, or one behind a broken link.
flowchart LR
T["No heartbeat for T ms"] --> Q{"Why?"}
Q --> C["Leader crashed"]
Q --> S["Leader slow - GC, disk stall, CPU starvation"]
Q --> N["Network dropped or delayed messages"]
Q --> P["Asymmetric partition - leader can send, cannot receive"]
C --> OK["Election is correct"]
S --> BAD["Election creates a second leader that the old one does not know about"]
N --> BAD
P --> BAD
Three of the four causes leave the old leader alive and convinced it is still in charge. This is why an election algorithm alone is never enough: you also need the old leader to stop (leases, step-down on lost quorum) and the rest of the system to ignore it if it does not (epochs, fencing).
The timeout trade-off
| Election timeout | Failover speed | False positives | Typical use |
|---|---|---|---|
| 100–300 ms | Very fast | Frequent on busy or cross-AZ networks, GC pauses trigger elections | LAN, tuned JVMs, Raft paper examples |
| 1–2 s | Fast | Occasional | etcd default (1000 ms election, 100 ms heartbeat) |
| 10–30 s | Slow | Rare | ZooKeeper sessions, Kubernetes leases (15 s), Patroni (30 s TTL) |
| Minutes | Very slow | Almost none | Manual or human-approved failover |
Total unavailability during failover is roughly:
The detection term usually dominates. A system with a 10-second lease that elects in 50 ms is still a ten-second-failover system.
The Bully Algorithm
The classic algorithm for fully-connected networks where every node knows every other node's ID.
Assumption: Higher ID = "stronger" node. Strongest healthy node wins.
Hector Garcia-Molina described it in 1982 ("Elections in a Distributed Computing System"). It uses three message types: ELECTION, OK (sometimes called ANSWER), and COORDINATOR.
How It Works
When a node P notices the leader is dead:
1. P sends Election(P.id) to all nodes with higher IDs
2. If no response within timeout: P declares itself leader
→ P sends Coordinator(P.id) to all nodes with lower IDs
3. If a higher-ID node Q receives Election(P.id):
→ Q sends OK to P (suppressing P's election)
→ Q starts its own election
Worked example
Five nodes, IDs 1–5. Node 5 is the leader and crashes. Node 2 is the first to notice.
sequenceDiagram
participant N1 as Node 1
participant N2 as Node 2
participant N3 as Node 3
participant N4 as Node 4
participant N5 as Node 5 (crashed)
Note over N5: Leader crashes
Note over N2: Heartbeat timeout fires
N2->>N3: ELECTION
N2->>N4: ELECTION
N2-xN5: ELECTION (no reply)
N3->>N2: OK
N4->>N2: OK
Note over N2: A higher node answered, so N2 waits for COORDINATOR
N3->>N4: ELECTION
N3-xN5: ELECTION (no reply)
N4->>N3: OK
N4-xN5: ELECTION (no reply)
Note over N4: No higher node answered within the timeout
N4->>N1: COORDINATOR 4
N4->>N2: COORDINATOR 4
N4->>N3: COORDINATOR 4
Notice two timeouts in play: the one that tells N4 nobody above it is alive, and a second one on N2 and N3 — if they receive OK but never receive COORDINATOR (say N4 crashed mid-election), they must restart the election.
Problems:
- O(n²) messages in the worst case
- Assumes synchrony (relies on timeouts)
- A slow node with a high ID can suppress a faster, lower-ID node from leading
And the big one: the bully algorithm has no quorum. If the network splits {1,2,3} from {4,5}, node 5 stays leader on its side and node 3 wins on the other. Both sides happily act. The algorithm's correctness argument assumes timeouts are accurate — that a node that does not answer has crashed — which is exactly the assumption real networks violate. It is a good teaching algorithm and a poor production one.
Ring Election
Nodes are arranged in a logical ring. Each node knows its successor.
Chang-Roberts Algorithm
Proposed by Ernest Chang and Rosemary Roberts in 1979, as an improvement on an earlier ring algorithm by Gérard Le Lann (1977) that forwarded every ID all the way round.
1. Node P suspects leader has crashed
2. P sends Election(P.id) to its successor
3. Each node Q that receives Election(id):
- If id > Q.id: forward Election(id) to successor
- If id < Q.id: send Election(Q.id) instead (suppress smaller IDs)
- If id == Q.id: Q is the leader, send Coordinator(Q.id) around the ring
A detail the summary above glosses over: each node keeps a participant flag. A node replaces a smaller ID with its own only if it has not already sent its own ID in this election; if it is already a participant, it simply discards the smaller ID. Without the flag, several initiators would each inject their own ID repeatedly and the message count would blow up.
Correction
An earlier version of the diagram below showed node 3 forwarding Election(5) and two separate nodes labelled 5. Under Chang-Roberts, node 3 receiving Election(2) would substitute its own, larger ID; and the winner is the highest live ID. The diagram now shows a ring where the old leader (5) has crashed and node 4 wins.
graph LR
N2(("2")) -->|"Election(2)"| N3(("3"))
N3 -->|"Election(3)"| N4(("4"))
N4 -->|"Election(4), skips crashed 5"| N1(("1"))
N1 -->|"Election(4)"| N2
N4 -.->|"Coordinator(4) sent around the ring"| N1
Step by step, with node 2 initiating:
| Step | Node | Receives | Action |
|---|---|---|---|
| 1 | 2 | — | Suspects leader 5, sends Election(2) to 3 |
| 2 | 3 | Election(2) | 2 < 3, not yet a participant, sends Election(3) |
| 3 | 4 | Election(3) | 3 < 4, sends Election(4) to 5 — 5 does not acknowledge, so 4 skips to 1 |
| 4 | 1 | Election(4) | 4 > 1, forwards |
| 5 | 2 | Election(4) | 4 > 2, forwards |
| 6 | 3 | Election(4) | 4 > 3, forwards |
| 7 | 4 | Election(4) | Its own ID came back — 4 is leader, sends Coordinator(4) round the ring |
Skipping a dead successor requires each node to know more than just its immediate neighbour (or to get an acknowledgement and route around failures), which is one of the reasons ring algorithms are awkward in practice.
Complexity: O(n) messages in the best case, O(n²) worst case (multiple simultaneous initiators).
More precisely, with a single initiator Chang-Roberts uses at most about messages (up to to get the winning ID round, plus for the coordinator announcement). With every node initiating and IDs arranged in the worst order, it is ; averaged over random ID placements it is . The Hirschberg-Sinclair algorithm (1980), which probes in both directions with doubling distances, achieves in the worst case.
Real-world use: Token Ring networks historically used ring election. Modern systems rarely use it — Raft is better.
Ring algorithms are mostly of theoretical interest today. Their real value is pedagogical: they show that election cost depends on topology and on how many nodes start at once, and they share the bully algorithm's fatal flaw — no quorum, so a partitioned ring can elect two leaders.
Raft Leader Election
The algorithm used by etcd, CockroachDB, TiKV, and most modern distributed databases. Built into Raft's design — not a separate mechanism.
In Raft, election is not a service the system calls — it is part of replicating the log. The leader is whoever currently holds the right to append to the log in the current term, and the election rules are designed so that only a node with every committed entry can win. The full protocol is covered in Raft: a full walkthrough and, more gently, Raft in plain English. Here we focus on the election part.
Roles
- Follower — passive, responds to requests from leaders/candidates
- Candidate — actively trying to become leader
- Leader — handles all client requests, sends heartbeats
Terms
Time is divided into terms (monotonically increasing integers). Each term begins with an election. If a candidate wins, it serves as leader for the rest of the term. Terms act as logical clocks — stale messages from old terms are rejected.
Three rules make terms work:
- Every node persists
currentTermandvotedForto disk before answering a vote request. A node that crashes and restarts must not vote twice in the same term. - Any message carrying a higher term than the receiver's causes the receiver to adopt that term and become a follower — including a leader.
- Any message carrying a lower term is rejected, and the reply tells the sender the current term.
Rule 2 is how a deposed leader finds out; rule 3 is how its stale requests are neutralised.
The Algorithm
Trigger: Follower receives no heartbeat within election timeout (150-300ms)
1. Follower increments its term, becomes Candidate
2. Votes for itself, sends RequestVote(term, candidateId, lastLogIndex, lastLogTerm) to all
3. Votes granted if:
- Voter hasn't voted this term AND
- Candidate's log is at least as up-to-date as voter's log
4. If candidate receives votes from majority: becomes Leader
5. Leader sends heartbeats (empty AppendEntries) to prevent new elections
The 150–300 ms range comes from the Raft paper's evaluation. Real deployments usually run longer: etcd defaults to a 100 ms heartbeat and a 1000 ms election timeout, and recommends setting the election timeout to at least ten times the round-trip time between members.
stateDiagram-v2
[*] --> Follower
Follower --> Candidate: Election timeout\nno heartbeat received
Candidate --> Leader: Receives majority\nvotes
Candidate --> Follower: Discovers higher\nterm or another leader
Leader --> Follower: Discovers higher\nterm
Candidate --> Candidate: Election timeout\n(split vote — retry)
An election, message by message
Five servers. S1 was leader in term 4 and has crashed. S3's randomized timer fires first.
sequenceDiagram
participant S3 as S3 (candidate)
participant S2
participant S4
participant S5
Note over S3: Timeout. term 4 to 5, votes for itself, persists
S3->>S2: RequestVote term 5, lastLogIndex 12, lastLogTerm 4
S3->>S4: RequestVote term 5, lastLogIndex 12, lastLogTerm 4
S3->>S5: RequestVote term 5, lastLogIndex 12, lastLogTerm 4
Note over S2: Log is not newer than S3's. Persist votedFor S3
S2-->>S3: VoteGranted term 5
Note over S4: Log is not newer than S3's. Persist votedFor S3
S4-->>S3: VoteGranted term 5
Note over S3: 3 of 5 votes - becomes leader of term 5
S3->>S2: AppendEntries heartbeat term 5
S3->>S4: AppendEntries heartbeat term 5
S3->>S5: AppendEntries heartbeat term 5
Note over S3: Appends a no-op entry in term 5 to commit earlier entries
S5's reply never mattered: three votes out of five is a majority. The final note is a detail that bites implementers: a new Raft leader cannot consider entries from previous terms committed just by counting replicas; it commits them indirectly by committing an entry from its own term. Appending a no-op on election does this immediately.
Split Vote Handling
If two candidates start elections simultaneously, votes may split and neither wins. Raft uses randomized election timeouts (each node picks a random timeout in 150-300ms range) to prevent simultaneous elections. The first node to time out usually wins before others even start.
Correction
This page previously said randomized timeouts are "how Raft escapes the FLP impossibility — randomization breaks the deterministic adversary." That overstates it. Raft is not a randomized consensus algorithm in the Ben-Or sense, and its liveness is not guaranteed with probability 1 in a fully asynchronous network. Raft keeps safety under full asynchrony and gets liveness from a partial-synchrony assumption: once message delays settle below the election timeout, an election succeeds. Randomized timeouts make split votes unlikely in that regime; they do not, on their own, defeat FLP.
The FLP impossibility page covers the real escapes — partial synchrony, randomized protocols, and failure detectors — and where Raft sits among them.
Log Safety Constraint
A candidate can only win if its log is at least as up-to-date as the majority of the cluster. This prevents electing a leader that's missing committed entries:
More precisely, each voter compares the candidate's log with its own: it grants its vote only if the candidate's last entry has a higher term, or the same term and an index at least as large. A committed entry is by definition stored on a majority; any winning candidate needs votes from a majority; the two majorities overlap in at least one node, and that node refuses to vote for a candidate missing the entry.
Candidate A: log = [1,2,3,4,5]
Candidate B: log = [1,2,3]
Nodes with log [1,2,3,4,5] will NOT vote for B
→ B cannot win majority → A wins
→ No committed entries are lost
(If entry 5 is committed, it is on a majority, so B cannot collect a majority without one of those nodes. If entry 5 was not committed, B may still win — and entry 5 is then legitimately discarded.)
Two refinements that matter in production: PreVote and CheckQuorum
Basic Raft has two well-known pathologies, both described in Diego Ongaro's thesis, and both fixed in mature implementations (etcd's raft library, hashicorp/raft, TiKV) by optional features.
The disruptive rejoiner. A node that was partitioned away keeps timing out and incrementing its term: 5, 6, 7, … 40. When the partition heals, its first RequestVote carries term 40, which forces the healthy leader (term 5) to step down — even though the rejoiner's log is stale and it cannot win. The cluster loses its leader for no reason.
PreVote fixes this by adding a dry run: before incrementing its term, a would-be candidate asks "would you vote for me if I started an election?" Peers say yes only if they have not heard from a leader recently and the candidate's log is up to date. The partitioned node never gets a yes, so it never bumps its term.
The deaf leader. A leader that can send but not receive (an asymmetric partition), or that has lost contact with a majority, may keep believing it is leader indefinitely, serving clients that can still reach it.
CheckQuorum makes the leader step down if it has not heard from a majority within an election timeout. This bounds how long a deposed leader can go on believing it is in charge — which is also the prerequisite for safe lease-based reads.
Election in Paxos and ZAB
Raft is not the only consensus protocol with a built-in election:
- Multi-Paxos does not strictly need a unique leader for safety. Any node may run phase 1 with a higher ballot number; the ballot plays the role of Raft's term. A "leader" is just a distinguished proposer that has completed phase 1 and can skip it for subsequent slots. Two nodes that both think they are leader only hurt liveness (dueling proposers), never safety. See Paxos.
- ZAB (ZooKeeper's protocol) elects a leader with the most recent transaction history using "fast leader election," then runs a discovery and synchronization phase before broadcasting. The epoch is embedded in the high 32 bits of every zxid. See ZAB.
- Viewstamped Replication rotates leadership deterministically by view number (
leader = view mod n), so electing is just agreeing to move to the next view. See Viewstamped Replication.
Same pattern in all four: a monotonically increasing epoch number, a majority quorum, and a rule that the new leader must know everything a previous majority committed.
ZooKeeper-Based Election
For systems that don't implement their own consensus, ZooKeeper (or etcd) provides leader election as a service.
The idea is to outsource the hard part. ZooKeeper (or etcd) runs consensus internally on a small ensemble; your application nodes just create keys and watch them. Your service can have two nodes or two hundred — the quorum lives in the coordination service, not in your application.
The building blocks
| ZooKeeper concept | What it gives election |
|---|---|
| Session | A client's liveness, maintained by heartbeats. Expires if the ensemble hears nothing for the session timeout (negotiated within 2× to 20× tickTime). |
| Ephemeral znode | Deleted automatically when the creating session expires — the "I am alive" marker. |
| Sequential znode | ZooKeeper appends a monotonically increasing 10-digit counter to the name — a total order of candidates. |
| Watch | A one-shot notification when a znode changes or is deleted. |
| zxid | The transaction ID of every change; the creation zxid of the leader's znode is a natural fencing token. |
Pattern: Ephemeral Sequential Nodes
1. Each candidate creates a ZNode: /election/candidate-{seq_num}
(Sequential: ZooKeeper auto-assigns incrementing numbers)
2. List all /election/ children, sort by sequence number
3. If I have the lowest number: I am the leader
4. Otherwise: watch the node with the next lower sequence number
5. When watched node is deleted (leader died): repeat from step 2
/election/
candidate-0000000001 ← Leader
candidate-0000000002 ← Watches 0001
candidate-0000000003 ← Watches 0002
Why watch the predecessor, not the leader? If all nodes watch the leader's ZNode, when it dies, all nodes simultaneously try to read the children list → herd effect (thundering herd). Watching only the predecessor serializes the election without the thundering herd.
Step 5 says "repeat from step 2", not "become leader", and that matters. The predecessor may have been deleted because it crashed while not being leader; the watcher must re-list the children to check whether it is now actually the lowest.
sequenceDiagram
participant A as Node A
participant B as Node B
participant C as Node C
participant ZK as ZooKeeper ensemble
A->>ZK: create /election/c- EPHEMERAL_SEQUENTIAL
ZK-->>A: /election/c-0000000001
B->>ZK: create /election/c- EPHEMERAL_SEQUENTIAL
ZK-->>B: /election/c-0000000002
C->>ZK: create /election/c- EPHEMERAL_SEQUENTIAL
ZK-->>C: /election/c-0000000003
A->>ZK: getChildren /election
Note over A: Lowest sequence - A is leader
B->>ZK: exists c-0000000001 with watch
C->>ZK: exists c-0000000002 with watch
Note over A: A stops heartbeating - crash, or a long pause
Note over ZK: Session timeout elapses - session expired
ZK->>ZK: delete c-0000000001 (ephemeral)
ZK-->>B: watch fired, NodeDeleted c-0000000001
B->>ZK: getChildren /election
Note over B: Lowest is now c-0000000002 - B is leader
Note over C: Nothing fired for C - no herd
The subtle part: what the leader must do when disconnected
The ZooKeeper client library reports connection state. A leader that loses its connection to the ensemble does not know whether its session has expired — expiry is decided by the ensemble, not the client. Until it reconnects, it is in limbo.
| Client state (Curator naming) | Meaning | What a leader must do |
|---|---|---|
CONNECTED / RECONNECTED | Session alive | Lead (re-verify leadership after reconnect) |
SUSPENDED | Connection lost, session may or may not be alive | Stop acting as leader immediately |
LOST | Session expired | Give up leadership, rejoin as a candidate |
The common bug is to stop leading only on LOST. In the gap between the ensemble expiring the session (and electing B) and the old leader's client finally noticing, there are two leaders. Stopping on SUSPENDED narrows the window; fencing closes it.
Used by: Kafka (controller election), HBase (HMaster election), older Hadoop (NameNode HA).
Correction
These three systems use ZooKeeper for election, but not the sequential-node recipe shown above. Kafka in ZooKeeper mode elected its controller by racing to create a single ephemeral /controller znode — first writer wins, everyone else watches it — and since KRaft (production-ready in Kafka 3.3, with ZooKeeper support removed in Kafka 4.0) the controller is elected by a Raft-based quorum instead. HBase's active HMaster similarly holds an ephemeral master znode, and HDFS NameNode HA uses the ZKFailoverController, which holds an ephemeral lock znode and fences the old active before promoting the standby. The "single ephemeral znode" variant is simpler but has the herd effect on every failover; the sequential recipe avoids it and gives a fair queue.
etcd: leases instead of sessions
etcd's model is similar, with different names:
| ZooKeeper | etcd |
|---|---|
| Session | Lease with a TTL, kept alive by LeaseKeepAlive |
| Ephemeral znode | Key attached to a lease (deleted when the lease expires) |
| Sequential suffix | Every key has a CreateRevision from the global revision counter |
| Watch | Watch (streaming, does not need re-arming) |
| zxid | Revision |
The concurrency package's election recipe has each candidate write a key under a shared prefix (the key name includes its lease ID), attached to its lease. The candidate whose key has the smallest CreateRevision is leader; everyone else watches the key with the next-lower revision — the same predecessor trick as ZooKeeper.
package main
import (
"context"
"log"
clientv3 "go.etcd.io/etcd/client/v3"
"go.etcd.io/etcd/client/v3/concurrency"
)
func main() {
cli, err := clientv3.New(clientv3.Config{Endpoints: []string{"etcd1:2379", "etcd2:2379", "etcd3:2379"}})
if err != nil {
log.Fatal(err)
}
defer cli.Close()
// The session owns a lease with a 10s TTL and keeps it alive in the background.
sess, err := concurrency.NewSession(cli, concurrency.WithTTL(10))
if err != nil {
log.Fatal(err)
}
defer sess.Close()
e := concurrency.NewElection(sess, "/myservice/leader")
ctx := context.Background()
// Blocks until we hold the lowest CreateRevision under the prefix.
if err := e.Campaign(ctx, "node-a"); err != nil {
log.Fatal(err)
}
token := e.Rev() // CreateRevision of our leader key: monotonic, usable as a fencing token
log.Printf("leader with fencing token %d", token)
// Leader-only writes to etcd itself can be made conditional on still being leader:
_, err = cli.Txn(ctx).
If(clientv3.Compare(clientv3.CreateRevision(e.Key()), "=", e.Rev())).
Then(clientv3.OpPut("/myservice/config", "v2")).
Commit()
if err != nil {
log.Print(err)
}
select {
case <-sess.Done():
// Lease lost (expired or revoked). We are no longer leader. Stop all leader work.
log.Print("lost leadership")
}
}
The conditional transaction is the important part. For writes that go to etcd itself, the "am I still leader?" check and the write are a single atomic operation — no window at all. For writes to other systems (a database, a storage bucket), you need those systems to check a fencing token, because etcd cannot make their write atomic with your leadership.
Kubernetes and lease objects in a shared store
The third family elects through a single record with an expiry in a strongly consistent store, without sequential ordering. Kubernetes controllers use a Lease object in the API server (backed by etcd): the holder writes its identity and a renew time; others try to take it over once leaseDurationSeconds has passed without renewal, using the API server's optimistic concurrency (resourceVersion) so only one takeover succeeds. kube-controller-manager and kube-scheduler default to a 15 s lease duration, 10 s renew deadline, and 2 s retry period.
Patroni (PostgreSQL HA) does the same with a leader key in etcd, Consul, ZooKeeper or Kubernetes: by default a 30 s TTL, and the primary renews it every loop_wait (10 s). A primary that cannot renew demotes itself to read-only before the TTL runs out.
These designs depend on the holder giving up before the lease expires by its own local clock. That works when clocks advance at roughly the same rate and the process is not paused — which is precisely the assumption the process-pause timeline breaks. See Leases and Fencing for the timing math.
Three ways to elect, compared
| Built-in consensus (Raft, ZAB, Paxos) | Coordination service (ZooKeeper, etcd election recipe) | Lease record in a store (K8s Lease, Patroni, DynamoDB lock client) | |
|---|---|---|---|
| Who runs the quorum | Your nodes | A separate 3–5 node ensemble | The store (if it is itself consensus-backed) |
| Your cluster size | Odd, 3–7 | Any | Any |
| Leader has latest data | Guaranteed by the vote rule | No — application must sync state itself | No |
| Fencing token | Term | zxid / CreateRevision | Record version, or a counter you add |
| Failover time | ~1–2 election timeouts | Session or lease TTL | Lease TTL |
| Operational burden | Inside the product | Run and monitor another critical service | Low, if you already run the store |
| Typical users | etcd, CockroachDB, TiKV, Consul, KRaft | Older Kafka, HBase, HDFS HA, many in-house services | Kubernetes controllers, Patroni, cron schedulers |
The "leader has latest data" row is often missed. A coordination service tells you who leads; it says nothing about whether that node has the data. If your nodes hold state (a database primary), the new leader must catch up or the election must prefer the most up-to-date candidate — which is why Patroni checks replication lag before a replica may take the leader key.
Split-Brain: The Nightmare Scenario
Split-brain occurs when two nodes both believe they are the leader simultaneously.
Timeline (five nodes A–E, A is leader):
t=0: Node A is leader, replicating to B, C, D and E
t=1: Network partition — A can reach B, C can reach D and E
t=2: C detects A is unreachable, starts election
t=3: C wins (quorum: C, D, E)
t=4: Both A and C are accepting writes as leader
t=5: Partition heals — conflicting data
Correction
The timeline previously started with "replicating to Node B and C" and then introduced D and E; it now states the five-node cluster explicitly. It also deserves a qualifier: the conflict at t=5 only happens if A's writes count without a majority. In a quorum-based system (Raft, ZAB, Paxos) A can still accept requests at t=4, but it cannot commit them — it reaches only 2 of 5 nodes — so clients never get success, and those uncommitted entries are overwritten when A rejoins and sees term N+1. The timeline as written describes a system with no quorum rule, such as naive primary/replica failover driven by a health check.
Prevention
Quorum: Only allow a leader to operate if it can communicate with a majority (N/2 + 1 nodes). A minority partition cannot elect a leader. This is the core mechanism in Raft and Paxos.
The arithmetic: with nodes and majority quorum , any two quorums share at least one node, because . That shared node voted in both elections, and it will not vote twice in the same term — so two leaders can never exist in the same term.
| Cluster size | Quorum | Failures tolerated | Note |
|---|---|---|---|
| 1 | 1 | 0 | No fault tolerance |
| 2 | 2 | 0 | Worse than 1: either failure stops progress |
| 3 | 2 | 1 | Minimum useful size |
| 4 | 3 | 1 | Same tolerance as 3, more replicas to write to |
| 5 | 3 | 2 | Common for production consensus |
| 7 | 4 | 3 | Upper end — beyond this, write latency grows for little gain |
This is why consensus clusters are odd-sized, and why "two data centres, active/passive with automatic failover" is fundamentally unable to avoid split brain on its own: with two sites, neither side of a site-to-site partition is a majority. You need a third site (even a tiny witness or tie-breaker) to decide.
Fencing tokens: Each leader receives a monotonically increasing token. Storage systems reject requests with stale tokens. A partitioned old leader with token 5 is rejected by storage when the new leader with token 6 is operating.
Leader A (token=5): WRITE key=X val=old
Storage: "Current leader token is 6, rejecting token 5" → rejected ✓
STONITH (Shoot The Other Node In The Head): When a failover occurs, explicitly kill the old leader before promoting the new one. Common in Pacemaker/Corosync (Linux HA cluster). Brutal but effective.
Self-fencing / step-down: The leader itself stops serving when it can no longer prove it is leader: Raft's CheckQuorum, Patroni demoting the primary when it cannot renew its key, a ZooKeeper client stopping on SUSPENDED. This is the cheapest layer, but it is only as reliable as the leader's ability to notice — which a paused or wedged process cannot.
Fencing in Practice
Fencing is covered in depth in Leases and Fencing; here is what matters for elections.
Where the token comes from
| Election mechanism | Natural fencing token |
|---|---|
| Raft | The leader's term |
| Multi-Paxos | The ballot number |
| ZAB / ZooKeeper election | The leader znode's creation zxid (or the epoch) |
| etcd election | The leader key's CreateRevision (Election.Rev()) |
| Kubernetes Lease | leaseTransitions counter or the object's resourceVersion |
| Hand-rolled Redis lock | None — you must add a counter (INCR) yourself, and Redis replication does not make it safe across failover |
Every one of these is monotonic across leadership changes, which is the only property a token needs.
The rule on the resource side
The protected resource remembers the highest token it has seen and rejects anything lower. Ideally this check and the write are one atomic step:
-- The resource keeps the highest epoch it has accepted, per protected object.
UPDATE jobs
SET status = 'running', owner = 'node-b', epoch = 34
WHERE id = 'nightly-billing'
AND epoch < 34; -- 0 rows updated means a newer leader already acted
Using < rather than <= here deliberately rejects a second claim with the same epoch; a leader repeating its own write must handle "0 rows" by checking that it already owns the row. The key properties: the comparison happens at the resource, atomically with the write, so no amount of delay between the leader's check and its action can let a stale leader through.
Tokens only work if the resource checks them
A fencing token passed to a resource that ignores it is decoration. Before relying on fencing, list every side effect the leader performs — database writes, object-store puts, emails, payments, calls to other services — and decide for each whether it can check a token. For those that cannot, you need idempotency keys, STONITH, or a design where only one place can perform the effect.
Worked Failure Timelines
The algorithms are easy to state. The failures are where the understanding is. Each timeline below is a scenario you should be able to reason through in an interview or an incident review.
Timeline 1: Clean leader crash in a five-node Raft cluster
Settings: heartbeat 100 ms, election timeout randomized in [1000, 2000] ms.
| Time (ms) | Event |
|---|---|
| 0 | S1 (leader, term 7) sends heartbeats |
| 50 | S1 crashes (power loss) |
| 100–1000 | Followers get no heartbeats; their timers keep running |
| ~1100 | S4's timer fires first (it last reset at ~0 and drew 1100). S4 → term 8, candidate |
| ~1102 | S2, S3, S5 receive RequestVote(term 8); S2 and S3 grant (S4's log is up to date) |
| ~1104 | S4 has 3 votes → leader of term 8, sends heartbeats and a no-op |
| ~1110 | No-op replicated to a majority; S4 can now serve linearizable reads and new writes |
| ~1150 | Clients that were talking to S1 time out, retry, get redirected to S4 |
Unavailability for writes: about 1.1 seconds, almost all of it detection. Shortening it means a shorter election timeout, which means more spurious elections on a noisy network. Writes that S1 had acknowledged were committed on a majority and are therefore in S4's log. Writes S1 had received but not yet committed may or may not survive; their clients never got success and must retry — with idempotency keys, or they may apply twice.
Timeline 2: The paused leader, and why leases alone are not enough
A scheduler uses a lease in a coordination service: 10 s TTL, renewed every 3 s. The leader runs a nightly billing job that writes to a database.
sequenceDiagram
participant A as Scheduler A
participant CS as Coordination service
participant B as Scheduler B
participant DB as Billing DB
A->>CS: renew lease, token 33
CS-->>A: ok, valid 10s
A->>A: checks lease is valid, starts billing batch
Note over A: Stop-the-world GC pause, 15 seconds
Note over CS: 10s pass with no renewal - lease expires
B->>CS: acquire lease
CS-->>B: granted, token 34
B->>DB: write invoices, token 34
DB-->>B: ok, highest token now 34
Note over A: Pause ends. A still believes its lease is valid
A->>DB: write invoices, token 33
DB-->>A: rejected, token 33 is below 34
| Time (s) | A believes | Truly | Without fencing | With fencing |
|---|---|---|---|---|
| 0 | Leader | Leader | — | — |
| 0.1 | Lease valid, starts batch | Leader | — | — |
| 0.2–15.2 | (paused, believes nothing) | Lease expires at 10 | — | — |
| 10.5 | — | B is leader, token 34 | B bills customers | B bills, DB records 34 |
| 15.2 | Leader (stale belief) | Not leader | A bills the same customers again | A's write rejected |
The bug is not in the election. The coordination service did exactly the right thing. A checked its lease before the pause and acted after it, and no check performed by A can close that gap, because the pause can land between any check and any action. Only the resource can close it. This is the argument Martin Kleppmann made in his 2016 critique of using Redis-based locks for correctness, and it applies to every lease-based election. See Distributed Locking for the lock-specific version.
Timeline 3: Old leader in the minority partition
Five-node Raft cluster, leader S1 in term 3. A network partition isolates {S1, S2} from {S3, S4, S5}.
| Time | Minority side {S1, S2} | Majority side {S3, S4, S5} |
|---|---|---|
| t0 | S1 leader term 3 | Followers of S1 |
| t0 + partition | S1 keeps sending heartbeats; only S2 receives them | No heartbeats arrive |
| t0 + ~1.5 s | S1 accepts a client write x=1, replicates to S2 only — 2 of 5, not committed, client waits | S4 times out, wins term 4 with S3, S5 |
| t0 + 2 s | Client B reads x from S1. If S1 serves reads locally, B sees the old value of x — or worse, a value written only on the minority side | S4 commits x=2 from another client |
| t0 + 2.5 s | With CheckQuorum, S1 notices no majority in an election timeout and steps down | Serving normally |
| heal | S1 receives term-4 message, becomes follower, its uncommitted x=1 entry is truncated and replaced with S4's log | — |
What could go wrong, and what prevents it:
| Hazard | Prevented by |
|---|---|
x=1 reported as successful | Commit requires a majority; S1 never has one |
| Stale read from S1 | ReadIndex (leader confirms leadership with a majority round before serving a read) or lease reads bounded by CheckQuorum and clock-drift margins |
| S1 serving forever | CheckQuorum |
Client of x=1 retrying blindly and double-applying | Client-side idempotency keys; the state machine deduplicates by request ID |
The read row is the important one. Raft without ReadIndex or leases does not give linearizable reads from the leader, despite what "reads go to the leader" suggests. etcd uses ReadIndex for linearizable reads by default and offers serializable (possibly stale, local) reads as an explicit option.
Timeline 4: Two data centres, no witness
A real incident shape. MySQL primary in data centre East, replicas in East and West, failover managed automatically.
sequenceDiagram
participant E as Primary in East
participant O as Failover manager
participant W as Replica in West
participant App as Applications
Note over E,W: Link between East and the network hub fails for under a minute
O->>E: health check
Note over O: East unreachable from the manager's quorum
O->>W: promote to primary
App->>W: writes routed to West
Note over E: East never crashed. Writes already on East were not yet replicated to West
Note over E,W: Link restored. Two divergent histories exist
O->>E: cannot simply rejoin as replica without losing its unreplicated writes
The failover was "correct" by its own rules. The trouble is what the election could not know: East had writes that West never received, because replication was asynchronous. Promoting West discarded them; reverting to East would discard West's new writes. Either way someone reconciles by hand.
War Story — GitHub, October 2018
On 21 October 2018, GitHub lost connectivity between its US East Coast network hub and its primary US East Coast data centre for 43 seconds during routine maintenance. Orchestrator, GitHub's MySQL topology manager (which itself runs Raft for its own coordination), saw the primaries as unreachable and promoted replicas in the US West Coast data centre. When connectivity returned, the East Coast databases contained a short window of writes that had not replicated to the West Coast, and the West Coast primaries now had writes of their own. GitHub chose not to discard either set, ran the site degraded while it restored from backups and replayed the divergent writes, and was degraded for a little over 24 hours. Source: GitHub's "October 21 post-incident analysis" (October 2018).
The lesson for election design: Orchestrator's own Raft quorum made its decision safe, but the database layer had no quorum for writes. A leader-election mechanism protects the data only if the data path is subject to the same quorum or fenced by the same epoch.
Production Considerations
Graceful handover
For planned maintenance, never "just kill the leader and let the timeout fire." Use a leadership transfer (Raft TimeoutNow, etcdctl move-leader, Curator's close, deleting your own Kubernetes Lease) so the outage is one round trip, not one election timeout. The consensus-section page walks through graceful transfer in more detail.
Leader responsibilities should be idempotent
Even with all the layers above, design leader actions so that a duplicate is harmless: idempotency keys on payments and emails, INSERT ... ON CONFLICT DO NOTHING for scheduled job runs keyed by (job, scheduled_time), and state transitions guarded by version checks. Election correctness and idempotent side effects are complements, not alternatives. See Exactly-Once Semantics and Timeouts, Retries and Backoff.
Practical Recommendations
| Scenario | Recommendation |
|---|---|
| New distributed system | Use Raft (via etcd or CockroachDB) |
| Need lightweight coordination | Use etcd's built-in leader election |
| Existing ZooKeeper infrastructure | Use ZooKeeper ephemeral nodes |
| Database primary election | Use Patroni (PostgreSQL) or Orchestrator (MySQL) |
| Simple single-region | Use Redis SETNX with TTL as a simple lock |
The Redis row is for efficiency, not correctness
SET key value NX PX ttl on a single Redis instance is fine when a duplicate leader merely wastes work (two cache warmers). It is not safe when a duplicate leader corrupts data or double-charges customers: Redis asynchronous replication can lose the key on failover, it produces no fencing token, and it is exposed to the paused-holder problem in timeline 2. For correctness-critical leadership use a consensus-backed store and fence the resource. See Distributed Locking.
More concrete guidance:
| If you need… | Do this |
|---|---|
| A replicated, strongly consistent state machine | Use a Raft library (etcd/raft, hashicorp/raft) or a system built on one; election comes with it. See replicated state machines. |
| One active instance of a stateless worker | etcd election or a Kubernetes Lease, plus fencing or idempotency on its side effects |
| Database primary failover | Patroni with a consensus-backed DCS; synchronous replication to at least one replica if losing acknowledged writes is unacceptable |
| Cross-data-centre failover | Three sites (or a witness), never two; or make failover a human decision |
| To protect a resource that cannot check tokens | STONITH or resource-level isolation (revoke credentials, detach the volume) before promoting |
Never implement split-brain prevention yourself. Use a battle-tested consensus library. The failure modes are subtle and the consequences (data corruption) are severe.
Interview Questions
1. Why can't the bully algorithm prevent split brain?
It has no quorum. Its correctness relies on timeouts being accurate — "no reply means crashed." During a partition, each side sees the other as crashed and elects its own highest live ID. Nothing forces the two sides to overlap, so both leaders act.
2. What exactly does Raft guarantee about leaders, and why is "at most one leader at a time" the wrong way to say it?
At most one leader per term. Two nodes can believe they are leader simultaneously — an old one in term 7 and a new one in term 8 — because the old one has not yet heard about term 8. Safety comes from the fact that the term-7 leader cannot commit anything: committing needs a majority, and a majority has already moved to term 8 and rejects term-7 messages.
3. A Raft candidate has the longest log. Is it guaranteed to win?
No. Voters compare the last term first, then the index. A candidate with a longer log whose last entry is from an older term loses to a shorter log ending in a newer term. And "guaranteed" never applies to liveness anyway: it may lose to a split vote or never reach a majority.
4. Why do ZooKeeper election recipes have each node watch its predecessor rather than the leader?
To avoid the herd effect. If every candidate watches the leader, the leader's deletion triggers N simultaneous getChildren calls and N re-evaluations. Watching the predecessor means one notification per failure, and candidates form an orderly queue.
5. A leader holds a 10-second lease and checks it before every write. Is that safe?
No. A process pause (GC, VM migration, page faults on swap) can occur between the check and the write, and the lease may expire and be granted elsewhere during the pause. Checking more often only narrows the window. Safety requires the resource to reject writes carrying a stale fencing token.
6. Why are consensus clusters odd-sized? Is four nodes ever better than three?
Majority of 3 is 2 (tolerates 1 failure); majority of 4 is 3 (still tolerates 1). Four nodes add replication cost and a larger quorum without tolerating more failures. Four can make sense only for read capacity or when one node is a non-voting learner.
7. How would you design automatic failover between exactly two data centres?
You cannot do it safely with only two voting sites: during a partition between them, neither side is a majority, so either both stop or one side guesses. Add a third site or a lightweight witness/tie-breaker that both can reach, so a majority exists. Otherwise, make cross-site failover a manual decision.
8. What is PreVote and what problem does it solve?
A node rejoining after a partition has incremented its term many times. In basic Raft its first RequestVote forces the healthy leader to step down, even though it can't win. PreVote has the candidate ask whether peers would vote for it before incrementing the term. Peers that recently heard from a leader say no, so the disruption never happens.
9. Give three different fencing tokens and where they come from.
Raft term (from the consensus protocol); etcd election key CreateRevision (from etcd's global revision counter); ZooKeeper znode creation zxid. All are monotonic across leadership changes, which is the only property needed. A Kubernetes Lease's transition count also works.
10. Does Multi-Paxos require a unique leader for safety?
No. Ballot numbers ensure that a proposer with a lower ballot cannot get any value chosen once acceptors have promised a higher one. Two concurrent "leaders" only cause dueling proposers — a liveness problem. A stable leader is a performance optimization (skip phase 1).
11. After a failover, clients that had sent writes to the old leader got timeouts. Should they retry?
Yes, but with idempotency keys. The write may have been committed (on a majority before the crash) or lost (only on the old leader). The client cannot tell. A retry with the same request ID lets the state machine deduplicate if it was in fact committed.
Further Reading
- Related on Archon: Leader Election (consensus section), Leases and Fencing, Failure Detectors, FLP Impossibility, Paxos, Replication