On this page

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:

  1. Safety — At most one leader at any time (no split-brain)
  2. Liveness — A leader is eventually elected if enough nodes are up
  3. 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.

PropertyNaive versionWhat production algorithms actually provide
SafetyNever two leaders at onceAt most one leader per epoch, and stale epochs are rejected
LivenessA leader is always elected quicklyA leader is eventually elected once the network behaves (partial synchrony)
ValidityThe leader is aliveThe 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 timeoutFailover speedFalse positivesTypical use
100–300 msVery fastFrequent on busy or cross-AZ networks, GC pauses trigger electionsLAN, tuned JVMs, Raft paper examples
1–2 sFastOccasionaletcd default (1000 ms election, 100 ms heartbeat)
10–30 sSlowRareZooKeeper sessions, Kubernetes leases (15 s), Patroni (30 s TTL)
MinutesVery slowAlmost noneManual 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
The bully algorithm: node 5 crashes, node 3 challenges every higher id, node 4 answers and wins — the highest id alive becomes leader and broadcasts COORDINATOR.

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:

StepNodeReceivesAction
12—Suspects leader 5, sends Election(2) to 3
23Election(2)2 < 3, not yet a participant, sends Election(3)
34Election(3)3 < 4, sends Election(4) to 5 — 5 does not acknowledge, so 4 skips to 1
41Election(4)4 > 1, forwards
52Election(4)4 > 2, forwards
63Election(4)4 > 3, forwards
74Election(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:

  1. Every node persists currentTerm and votedFor to disk before answering a vote request. A node that crashes and restarts must not vote twice in the same term.
  2. Any message carrying a higher term than the receiver's causes the receiver to adopt that term and become a follower — including a leader.
  3. 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 conceptWhat it gives election
SessionA client's liveness, maintained by heartbeats. Expires if the ensemble hears nothing for the session timeout (negotiated within 2× to 20× tickTime).
Ephemeral znodeDeleted automatically when the creating session expires — the "I am alive" marker.
Sequential znodeZooKeeper appends a monotonically increasing 10-digit counter to the name — a total order of candidates.
WatchA one-shot notification when a znode changes or is deleted.
zxidThe 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)MeaningWhat a leader must do
CONNECTED / RECONNECTEDSession aliveLead (re-verify leadership after reconnect)
SUSPENDEDConnection lost, session may or may not be aliveStop acting as leader immediately
LOSTSession expiredGive 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:

ZooKeeperetcd
SessionLease with a TTL, kept alive by LeaseKeepAlive
Ephemeral znodeKey attached to a lease (deleted when the lease expires)
Sequential suffixEvery key has a CreateRevision from the global revision counter
WatchWatch (streaming, does not need re-arming)
zxidRevision

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 quorumYour nodesA separate 3–5 node ensembleThe store (if it is itself consensus-backed)
Your cluster sizeOdd, 3–7AnyAny
Leader has latest dataGuaranteed by the vote ruleNo — application must sync state itselfNo
Fencing tokenTermzxid / CreateRevisionRecord version, or a counter you add
Failover time~1–2 election timeoutsSession or lease TTLLease TTL
Operational burdenInside the productRun and monitor another critical serviceLow, if you already run the store
Typical usersetcd, CockroachDB, TiKV, Consul, KRaftOlder Kafka, HBase, HDFS HA, many in-house servicesKubernetes 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 sizeQuorumFailures toleratedNote
110No fault tolerance
220Worse than 1: either failure stops progress
321Minimum useful size
431Same tolerance as 3, more replicas to write to
532Common for production consensus
743Upper 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 mechanismNatural fencing token
RaftThe leader's term
Multi-PaxosThe ballot number
ZAB / ZooKeeper electionThe leader znode's creation zxid (or the epoch)
etcd electionThe leader key's CreateRevision (Election.Rev())
Kubernetes LeaseleaseTransitions counter or the object's resourceVersion
Hand-rolled Redis lockNone — 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
0S1 (leader, term 7) sends heartbeats
50S1 crashes (power loss)
100–1000Followers get no heartbeats; their timers keep running
~1100S4's timer fires first (it last reset at ~0 and drew 1100). S4 → term 8, candidate
~1102S2, S3, S5 receive RequestVote(term 8); S2 and S3 grant (S4's log is up to date)
~1104S4 has 3 votes → leader of term 8, sends heartbeats and a no-op
~1110No-op replicated to a majority; S4 can now serve linearizable reads and new writes
~1150Clients 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 believesTrulyWithout fencingWith fencing
0LeaderLeader——
0.1Lease valid, starts batchLeader——
0.2–15.2(paused, believes nothing)Lease expires at 10——
10.5—B is leader, token 34B bills customersB bills, DB records 34
15.2Leader (stale belief)Not leaderA bills the same customers againA'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}.

TimeMinority side {S1, S2}Majority side {S3, S4, S5}
t0S1 leader term 3Followers of S1
t0 + partitionS1 keeps sending heartbeats; only S2 receives themNo heartbeats arrive
t0 + ~1.5 sS1 accepts a client write x=1, replicates to S2 only — 2 of 5, not committed, client waitsS4 times out, wins term 4 with S3, S5
t0 + 2 sClient 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 sideS4 commits x=2 from another client
t0 + 2.5 sWith CheckQuorum, S1 notices no majority in an election timeout and steps downServing normally
healS1 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:

HazardPrevented by
x=1 reported as successfulCommit requires a majority; S1 never has one
Stale read from S1ReadIndex (leader confirms leadership with a majority round before serving a read) or lease reads bounded by CheckQuorum and clock-drift margins
S1 serving foreverCheckQuorum
Client of x=1 retrying blindly and double-applyingClient-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

ScenarioRecommendation
New distributed systemUse Raft (via etcd or CockroachDB)
Need lightweight coordinationUse etcd's built-in leader election
Existing ZooKeeper infrastructureUse ZooKeeper ephemeral nodes
Database primary electionUse Patroni (PostgreSQL) or Orchestrator (MySQL)
Simple single-regionUse 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 machineUse 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 workeretcd election or a Kubernetes Lease, plus fencing or idempotency on its side effects
Database primary failoverPatroni with a consensus-backed DCS; synchronous replication to at least one replica if losing acknowledged writes is unacceptable
Cross-data-centre failoverThree sites (or a witness), never two; or make failover a human decision
To protect a resource that cannot check tokensSTONITH 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