Consensus & Leader Election

In a Nutshell

Once you scale out to many machines, they have to agree on things: who's the leader, which write happened first, what the current configuration is. Consensus is the problem of getting a group of unreliable, independently-failing nodes to agree on a single value even when some crash or messages get delayed. Leader election is the most common application — picking one node to coordinate so the others can follow it. Algorithms like Raft and Paxos solve this safely, and they're the invisible backbone behind almost every distributed database, coordination service (ZooKeeper, etcd), and failover system you'll ever design.

How It Actually Works

Why Agreement Is Hard

In a distributed system you can't tell the difference between a node that's dead and one that's just slow or partitioned away. This is the core difficulty: if the leader goes silent, is it gone (elect a new one) or just lagging (electing a new one risks two leaders)? Consensus algorithms exist to make this decision safely despite that ambiguity.

The FLP impossibility result proves you can't guarantee consensus in a fully asynchronous network with even one faulty node — so real algorithms use timeouts and randomization to make progress in practice while never sacrificing safety (they may pause, but they never decide wrong).

The Role of Quorum (Majority)

Consensus algorithms require a majority (quorum) of nodes to agree before any decision is final. With N nodes, you need ⌊N/2⌋ + 1:

Cluster Size	Quorum	Failures Tolerated
3	2	1
5	3	2
7	4	3

Two takeaways: use odd numbers (4 nodes tolerate the same 1 failure as 3, but cost more and are easier to split evenly), and majority quorum is what prevents split-brain — two partitions can't both have a majority, so at most one side can elect a leader and accept writes.

Raft: Consensus You Can Actually Understand

Raft is the modern standard because it's designed for understandability. It breaks consensus into three pieces:

1. Leader election. Each node is a follower, candidate, or leader. Time is divided into terms. If a follower hears no heartbeat within a randomized election timeout, it becomes a candidate and requests votes. Win a majority → become leader.

Follower ──(no heartbeat within timeout)──▶ Candidate
Candidate ──(gets majority of votes)──────▶ Leader
Candidate ──(sees a higher term)──────────▶ Follower
Leader ────(discovers higher term)────────▶ Follower

2. Log replication. The leader appends client commands to its log and replicates them to followers. Once a majority has an entry, it's committed and applied to the state machine.

3. Safety. Randomized timeouts make split votes rare; the majority rule and term numbers guarantee at most one leader per term and that committed entries are never lost.

Preventing Split-Brain with Fencing

Even with elections, an old leader that was partitioned might come back thinking it's still in charge. Fencing tokens (monotonically increasing epoch numbers) solve this: every write carries the leader's term/epoch, and downstream systems reject any write with a stale token.

Old leader (term 4) was partitioned, still thinks it's leader.
New leader elected (term 5).
Old leader tries to write with token=4 → storage rejects (current epoch=5).
✅ No split-brain: stale leader is fenced out.

Where You'll Actually Meet Consensus

You rarely implement Raft yourself — you use systems built on it:

System	Uses Consensus For
etcd / ZooKeeper / Consul	Cluster coordination, config, leader election as a service
Kafka (KRaft)	Controller/metadata election
CockroachDB / TiDB / Spanner	Committing writes across replicas (Raft/Paxos per range)
Kubernetes	etcd stores all cluster state via Raft
Databases' failover	Electing a new primary without split-brain

Common pattern: instead of building election into your own service, outsource it to etcd/ZooKeeper via a lease or lock — whoever holds the lease is leader, and the lease auto-expires if that node dies.

Seeing It in Action

Scenario: Ensuring only one instance runs a scheduled job across a fleet, using etcd leader election.

import etcd3

# All 5 app instances run this. Only one becomes leader and runs the job.
client = etcd3.client(host="etcd", port=2379)

def run_as_leader(instance_id):
    # Acquire a lease that auto-expires in 10s unless we keep renewing it.
    lease = client.lease(ttl=10)

    # Try to become leader by claiming a well-known key (atomic put-if-absent).
    acquired, _ = client.transaction(
        compare=[client.transactions.version("/service/leader") == 0],
        success=[client.transactions.put("/service/leader",
                                         instance_id, lease=lease)],
        failure=[],
    )

    if acquired:
        print(f"{instance_id} is LEADER — running the scheduled job")
        lease.refresh()          # heartbeat: keep the lease alive
        do_scheduled_work()
    else:
        print(f"{instance_id} is FOLLOWER — standing by")
    # If the leader crashes, its lease expires in <=10s and a follower takes over.

What this guarantees: exactly one instance runs the job at a time. etcd's underlying Raft consensus ensures the lock is globally consistent — even during a network partition, only the majority side can hold the lease, so you never get two nodes running the job simultaneously.

Interview Questions

1. Q: What problem does consensus solve, and why is it fundamentally hard? Hint: Getting multiple independently-failing nodes to agree on a single value despite crashes, message delays, and partitions. It's hard because you can't distinguish a dead node from a slow/partitioned one, and FLP proves consensus can't be guaranteed in a fully asynchronous network with even one faulty node — so real systems use timeouts/randomization for liveness while preserving safety.

2. Q: Why do consensus systems need an odd number of nodes and a majority quorum? Hint: A decision requires a majority (⌊N/2⌋+1) so that two partitions can't both reach quorum — this prevents split-brain. Odd numbers are optimal: 5 nodes tolerate 2 failures, but 6 also only tolerate 2 while costing more and risking even splits. Majority is the mechanism guaranteeing at most one leader.

3. Q: Walk through Raft leader election at a high level. Hint: Nodes are followers, candidates, or leaders, and time is split into terms. If a follower gets no leader heartbeat within a randomized election timeout, it becomes a candidate, increments the term, and requests votes. A candidate winning a majority becomes leader and sends heartbeats. Higher terms always win, guaranteeing one leader per term. Randomized timeouts avoid perpetual split votes.

4. Q: What is split-brain, and how do fencing tokens prevent it? Hint: Split-brain is two nodes both acting as leader (e.g., a recovered/partitioned old leader). Fencing tokens are monotonically increasing epoch/term numbers attached to every write; downstream storage rejects any write carrying a stale token, so a demoted leader can't corrupt state even if it still believes it's in charge.

5. Q: In practice, would you implement Raft yourself for leader election in your service? What's the alternative? Hint: Almost never — it's subtle and error-prone. Instead outsource coordination to a battle-tested system: acquire a lease/lock in etcd, ZooKeeper, or Consul; whoever holds it is leader, and it auto-expires on failure. Those systems run the consensus for you and expose simple primitives.

References

• In Search of an Understandable Consensus Algorithm (Raft) by Ongaro & Ousterhout — the original Raft paper
• The Raft visualization — interactive, watch elections and log replication happen
• Designing Data-Intensive Applications by Martin Kleppmann — Chapter 9: Consistency and Consensus

Dive Deeper

• Paxos Made Simple by Leslie Lamport — the foundational (if famously tricky) consensus algorithm
• etcd documentation — Raft-backed coordination you can actually run
• Google's Chubby lock service paper — the design that inspired ZooKeeper and modern coordination services