Consensus and Leader Election

Why machines struggle to agree, what majority consensus gives you, how leases and fencing tokens stop split brain, and how much to say in an interview.

17 minLesson 5 of 8
On this page
  1. Why agreeing is hard
  2. The idea: majorities
  3. Leases and fencing tokens
  4. Where it shows up
  5. In the interview
  6. Common mistakes
  7. What to practise next

A billing scheduler runs on two machines so one can take over if the other dies. Each checks the other with a heartbeat every second and takes over after 5 missed beats. One night the network between them drops for 10 seconds. Each decides the other is dead, both become leader, and both run the nightly billing job. 40,000 customers are charged twice.

Neither machine was wrong given what it could see. Consensus solves this: several machines agree on one answer (who leads, what was written) even when some are slow, dead or cut off.

Why agreeing is hard

A machine that stops answering might be dead, overloaded, paused by garbage collection, or behind a broken link. From outside these look the same; no timeout tells them apart. Clocks drift, and messages arrive late, twice, or never.

With two machines, any rule fails: if each waits for the other's vote, a single failure stops everything; if each acts alone, a partition gives you two leaders (split brain).

The idea: majorities

Use an odd number of nodes, usually 3 or 5, and require a majority for every decision. Any two majorities of the same group share at least one node, so two conflicting decisions can never both get a majority. A cut-off minority simply cannot act.

Raft-style consensus (a simplified picture) builds on that:

  • One leader per term. Terms are numbered 1, 2, 3… A node becomes leader for a term only with votes from a majority, and each node votes once per term.
  • A replicated log. Every change is appended to the leader's log and copied to followers. An entry is committed once a majority has stored it; only then is it applied and acknowledged.
  • Elections on silence. If followers hear nothing from the leader for a randomised timeout (a few hundred ms), one becomes a candidate for the next term and asks for votes. Nodes vote only for a candidate whose log is at least as complete as theirs, so a new leader always has every committed entry.

The cost: every write waits for a majority, and with 2f + 1 nodes you survive f failures. 3 nodes survive 1, 5 survive 2. 4 nodes still survive only 1 (a majority of 4 is 3), so even sizes buy nothing.

A committed write, a leader crash, an electionUse the arrows or ← → keys
  1. A committed write, a leader crash, an election, step 1Client to Node 1; Client to Node 2; Node 1 and Node 2; Node 1 and Node 3; Node 2 and Node 3.ClientNode 1leader, term 3Node 2Node 3
    term
    3
    entry 7 copies
    1

    1Node 1 is leader for term 3. A client writes owner = A. The leader appends it to its log as entry 7, not yet committed.

  2. A committed write, a leader crash, an election, step 2Client to Node 1; Client to Node 2; Node 1 and Node 2; Node 1 and Node 3; Node 2 and Node 3.ClientNode 1leader, term 3Node 2Node 3
    term
    3
    entry 7 copies
    1

    2It sends entry 7 to both followers.

  3. A committed write, a leader crash, an election, step 3Client to Node 1; Client to Node 2; Node 1 and Node 2; Node 1 and Node 3; Node 2 and Node 3.ClientNode 1Node 2Node 3slow
    term
    3
    entry 7 copies
    2

    3Node 2 stores it and replies. That is 2 of 3 copies, a majority: entry 7 is committed. Node 3 is slow, which does not matter.

  4. A committed write, a leader crash, an election, step 4Client to Node 1; Client to Node 2; Node 1 and Node 2; Node 1 and Node 3; Node 2 and Node 3.ClientNode 1Node 2Node 3
    term
    3
    entry 7 copies
    2

    4The leader applies it and tells the client: success.

  5. A committed write, a leader crash, an election, step 5Client to Node 1; Client to Node 2; Node 1 and Node 2; Node 1 and Node 3; Node 2 and Node 3.ClientNode 1downNode 2Node 3
    term
    3
    leader
    none

    5Node 1 crashes. Heartbeats stop.

  6. A committed write, a leader crash, an election, step 6Client to Node 1; Client to Node 2; Node 1 and Node 2; Node 1 and Node 3; Node 2 and Node 3.ClientNode 1downNode 2candidate, t4Node 3
    term
    4
    votes for 2
    1

    6Node 2's random timeout fires first. It starts term 4, votes for itself and asks Node 3.

  7. A committed write, a leader crash, an election, step 7Client to Node 1; Client to Node 2; Node 1 and Node 2; Node 1 and Node 3; Node 2 and Node 3.ClientNode 1downNode 2leader, term 4Node 3
    term
    4
    votes for 2
    2

    7Node 2's log is at least as complete as Node 3's, so Node 3 votes yes. 2 of 3: Node 2 leads term 4. It has entry 7, because the majority that committed it overlaps the majority that elects.

  8. A committed write, a leader crash, an election, step 8Client to Node 1; Client to Node 2; Node 1 and Node 2; Node 1 and Node 3; Node 2 and Node 3.ClientNode 1downNode 2leader, term 4Node 3
    term
    4
    leader
    Node 2

    8The client retries against Node 2. Failover took well under a second.

  9. A committed write, a leader crash, an election, step 9Client to Node 1; Client to Node 2; Node 1 and Node 2; Node 1 and Node 3; Node 2 and Node 3.ClientNode 1follower, t4Node 2Node 3
    term
    4
    leader
    Node 2

    9Node 1 comes back still thinking it leads term 3. The first message it sees carries term 4, so it steps down. Alone it could never commit: 1 of 3 is not a majority.

1 / 9

One subtlety interviewers like: until it hears of term 4, the old leader may still answer reads from a stale copy. Systems promising fresh reads confirm leadership with a majority first, or use a time-based lease.

Leases and fencing tokens

Most systems do not run consensus themselves. They ask a small consensus-backed coordination service (such as ZooKeeper or etcd) for a lease: "you are leader for the next 10 seconds; renew before then." If the holder dies, the lease expires and someone else gets it.

A lease alone is not enough. A process paused for 15 seconds wakes believing its lease is valid and writes anyway. The fix is a fencing token: a number that grows with every grant, and storage rejects any write carrying a smaller number than one it has seen.

A paused leader is fenced offUse the arrows or ← → keys
  1. A paused leader is fenced off, step 1Scheduler A to Coordination service (lease); Scheduler B to Coordination service (lease); Scheduler A to Billing store (write + token); Scheduler B to Billing store (write + token).Scheduler Atoken 33Scheduler BCoordinationserviceBilling storeleaseleasewrite + tokenwrite + token
    store's highest token
    0

    1A gets a 10-second lease with token 33.

  2. A paused leader is fenced off, step 2Scheduler A to Coordination service (lease); Scheduler B to Coordination service (lease); Scheduler A to Billing store (write + token); Scheduler B to Billing store (write + token).Scheduler Atoken 33Scheduler BCoordinationserviceBilling storeleaseleasewrite + tokenwrite + token
    store's highest token
    33

    2A starts the billing run and writes with token 33. The store records 33 as the highest token seen.

  3. A paused leader is fenced off, step 3Scheduler A to Coordination service (lease); Scheduler B to Coordination service (lease); Scheduler A to Billing store (write + token); Scheduler B to Billing store (write + token).Scheduler ApausedScheduler BCoordinationserviceBilling storeleaseleasewrite + tokenwrite + token
    store's highest token
    33

    3A pauses for 15 seconds (garbage collection). It cannot renew and does not know time passed.

  4. A paused leader is fenced off, step 4Scheduler A to Coordination service (lease); Scheduler B to Coordination service (lease); Scheduler A to Billing store (write + token); Scheduler B to Billing store (write + token).Scheduler ApausedScheduler Btoken 34CoordinationserviceBilling storeleaseleasewrite + tokenwrite + token
    store's highest token
    33

    4The lease expires. B asks for it and gets token 34.

  5. A paused leader is fenced off, step 5Scheduler A to Coordination service (lease); Scheduler B to Coordination service (lease); Scheduler A to Billing store (write + token); Scheduler B to Billing store (write + token).Scheduler ApausedScheduler Btoken 34CoordinationserviceBilling storeleaseleasewrite + tokenwrite + token
    store's highest token
    34

    5B continues the run and writes with token 34. The store accepts it and now remembers 34.

  6. A paused leader is fenced off, step 6Scheduler A to Coordination service (lease); Scheduler B to Coordination service (lease); Scheduler A to Billing store (write + token); Scheduler B to Billing store (write + token).Scheduler AScheduler BCoordinationserviceBilling storereject 33leaseleasewrite + tokenwrite + token
    store's highest token
    34

    6A wakes and writes with token 33, sure it is still leader. 33 is below 34, so the store rejects it. Split brain did no damage.

1 / 6
Ways to pick one leader
OptionGood atBad atPick it when
Lease from a coordination service Usual defaultProven consensus underneath; you write little code. Gives tokens for fencing.Another cluster to run; the leader must stop when it cannot renew.Schedulers, single-writer workers, shard owners.
Database with built-in consensusReplication, election and failover come with the store.Writes pay a majority round trip; across regions that is tens of ms.The data itself needs automatic failover without losing commits.
Lock row in an existing databaseNo new system: a row with owner and expiry time.Only as available as that database; you must add fencing yourself.Small systems that already depend on one database.

Where it shows up

  • Choosing the single leader of a replicated database, and promoting a new one.
  • Metadata stores: which node owns which shard, cluster membership, configuration.
  • Locks and "exactly one worker does this job" schedulers.

Keep consensus for small, critical metadata, not every user request: a majority round trip on every request costs too much.

Estimate: Commit latency with five nodes

A five-node cluster has its leader in region A. How long does the leader wait before a write is committed?

You know
  • Round trips from the leader to the other four nodes: 30 ms, 80 ms, 90 ms, 120 ms
  • A write commits once a majority of the five nodes have stored it

Show the working
  1. Majority of 5 = 3 nodes: the leader plus 2 followers
  2. The leader waits for the 2 fastest followers: 30 ms and 80 ms
  3. Commit after the slower of those two: 80 ms

Estimate 80 ms (anything from 40 ms to 240 ms is a good answer)

Commit latency is set by the majority's slowest member, not the slowest node. Placing two nodes close to the leader cuts it.

In the interview

Mention consensus when something needs exactly one owner (a leader, a lock, a shard map) or when you promise no lost writes on failover. Keep it to a sentence or two unless pushed: "The shard map lives in a consensus-backed store such as etcd, three nodes, so it survives one failure. Workers hold leases and every write carries a fencing token." Interviewers almost never want Raft on the whiteboard.

Making the scheduler safe
Interviewer

How do you make sure only one scheduler runs the billing job?

You

Schedulers take a lease from a coordination service with three nodes, so it survives losing one. The lease is 10 seconds and renewed every 3. The holder runs the job.

Interviewer

What if the holder freezes and wakes up after the lease has moved?

You

It would still try to write. So each lease carries a fencing token, and the billing store rejects any write with a token lower than the highest it has seen. I also make each charge idempotent per customer and month, so even a duplicate run cannot bill twice.

Follow-ups you should expect:

  • "Why three nodes and not two?" Two cannot form a majority after one fails. Three can.
  • "What happens on the minority side of a partition?" It cannot elect a leader or commit, so it refuses writes: consistency over availability.
  • "Isn't lease expiry enough on its own?" No. Clocks drift and processes pause, so a holder can act after its lease ended. Anything that must not happen twice needs fencing.

Common mistakes

Quick check

How many node failures can a 5-node majority-based cluster survive and still commit writes?

A storage service has seen fencing token 52. A write arrives with token 51. What should happen?

Why is a 4-node cluster rarely chosen over 3?

What to practise next

Consensus often hands out the machine numbers used to build unique IDs. To see a lease-based leader in a full design, work through Design a Job Scheduler.