Distributed Systems · 4 of 4

Consensus

Getting several machines to agree on one leader, one log, one answer, while any of them may crash and the network may lie about which. Raft and Paxos solve it with one idea, the overlapping majority, and pay for it in round trips.

≈ 25 min

The whole idea

Press ← → to step, or Space to play and pause, whenever a diagram has focus.

What consensus is

Leader-based replication has a hole in the middle. When the leader dies, someone must pick a successor, and everyone must agree on who. Get it wrong and you have split brain: two leaders, two histories, data that can’t be merged. A failover script, a human with a pager, a heartbeat timeout: each of these can be fooled by a slow network into promoting a second leader.

Consensus is the problem of getting several nodes to agree on a single value, in a way that survives some of them crashing. Formally, an algorithm solves it if:

  • Agreement: no two nodes decide differently.
  • Integrity: no node decides twice.
  • Validity: the decided value was proposed by some node.
  • Termination: every node that doesn’t crash eventually decides.

The first three are safety properties: nothing bad ever happens. Termination is liveness: something good eventually happens. Without termination the problem is trivial (never decide), so it’s what makes the problem hard.

A single decision is rarely the goal. What systems need is a sequence of them: entry 1 of the log is this, entry 2 is that. Agreeing on a log in order is total order broadcast, and it’s equivalent to consensus: each can be built from the other. Feed the same log to deterministic replicas and they stay identical. That’s state machine replication, and it’s what etcd, ZooKeeper, Kafka’s KRaft controllers and every Raft-based database are.

The same machinery gives you the other things that need “exactly one”: a linearizable compare-and-set register, a lock with a single holder, a uniqueness constraint, a leader. They all reduce to consensus.Atomic commit is a close cousin. Two-phase commit gets every participant to agree on commit or abort, but it blocks if the coordinator dies at the wrong moment. Running the coordinator’s decision through consensus (Gray and Lamport’s Paxos Commit) removes that single point of failure.

FLP impossibility

In 1985 Fischer, Lynch and Paterson proved that in an asynchronous system, where messages can be delayed arbitrarily and there are no clocks, no deterministic algorithm can guarantee consensus if even one process may crash. The trouble is that a crashed node and a slow one look identical. Any algorithm that waits for a node may wait forever; any algorithm that stops waiting may decide without information it needed.

That sounds fatal, and practical systems run consensus all day. The way out is to weaken the model, never the safety:

  • Partial synchrony. Assume the network is usually timely. Use timeouts to make progress, and design so that a wrong timeout costs only time. Paxos and Raft both work this way: safety holds even when every timing assumption is broken; liveness returns once the network behaves.
  • Randomness. Randomized algorithms terminate with probability 1. Raft borrows the idea for its election timeouts.

Lamport put it directly in “Paxos Made Simple”: electing a leader reliably must use “either randomness or real time”, but “safety is ensured regardless of the success or failure of the election”.

Majorities and terms

Both Raft and Paxos rest on two ideas. The first is the majority quorum: a decision counts once more than half the nodes have it, and any two majorities of the same cluster overlap in at least one node.

Why majorities

S1S2S3S4S5entry stored on 3 of 5: committed
The overlap is what carries a decision from one leader to the next. The arithmetic is why clusters have odd sizes.

The second is the term (Paxos calls it a ballot or proposal number; ZooKeeper an epoch): a counter that increases with every election. Every message carries one. A node that sees a higher term than its own steps down and adopts it; a message from an older term is rejected. Terms make “the current leader” a well-defined thing, and they’re the same idea as a fencing token, applied inside the protocol.

Leader election

Raft, published by Diego Ongaro and John Ousterhout in 2014, was designed for understandability first. Their user study had 43 students at two universities learn both Raft and Paxos; 33 of them then answered questions about Raft better than questions about Paxos. Raft splits consensus into leader election, log replication and safety, and every node is in one of three states: follower, candidate or leader.

  1. A follower that hears nothing from a leader for its election timeout becomes a candidate, increments the term, votes for itself and asks the others for votes.
  2. Each node grants one vote per term, first come, first served, and only to a candidate whose log is at least as up to date as its own.
  3. A candidate with votes from a majority becomes leader and immediately sends heartbeats, which stop other elections. A candidate that hears from a leader with an equal or higher term steps down.

The hero diagram showed the happy path. The interesting case is when two candidates stand at once.

Split vote

Liveness, not safety, is at stake: a split vote wastes a term but can never elect two leaders.

Raft’s answer is randomness: election timeouts are drawn from a range, “e.g., 150–300ms” in the paper, so one node usually times out well before the rest and wins before anyone else starts. Its timing rule is broadcastTime ≪ electionTimeout ≪ MTBF: a heartbeat round trip (0.5–20 ms, depending on storage) must be much shorter than the timeout, and the timeout much shorter than the months between server failures. etcd ships with a 100 ms heartbeat and a 1,000 ms election timeout, and its tuning guide says the timeout should be at least ten times the round-trip time between members.

Two extensions matter in production. PreVote has a would-be candidate first ask whether it could win before incrementing the term, so a node rejoining after a partition doesn’t force a pointless election; etcd enables it by default. CheckQuorum makes a leader step down if it stops hearing from a majority, so a cut-off leader doesn’t keep believing in itself.

Log replication

Once elected, the leader takes every client request, appends it to its log, and replicates it with AppendEntries messages (which double as heartbeats). An entry is committed when the leader has stored it on a majority; the leader then applies it to its state machine and replies to the client.

The log, server by server

#1#2#3#4#5#6S1t1t1t2leader · term 3S2t1t1t2followerS3t1t1t2followerS4t1t1t2t2t22 uncommittedS5t1t1behindcommit indexcommittedpendingconflicting, deleted
Each entry carries the term it was written in. Committed entries are solid; pending ones are dashed.

Each AppendEntries carries the index and term of the entry just before the new ones. A follower accepts only if its log has a matching entry there; otherwise the leader steps back and retries. That one check gives the Log Matching property: if two logs have an entry with the same index and term, they’re identical up to that point. Followers with extra, conflicting entries have them overwritten. That’s safe precisely because those entries were never committed.

Safety

Two rules keep committed entries permanent across leader changes.

  • The election restriction. A voter refuses a candidate whose log is less up to date than its own (compare last terms; if equal, compare lengths). A committed entry is on a majority, and the winner needs a majority’s votes, so at least one voter has the entry, and that voter only votes for a candidate that has it too. Every leader holds every committed entry.
  • Only commit your own term’s entries by counting. A new leader may find an older-term entry sitting on a majority, and it still can’t call it committed: the paper’s Figure 8 shows such an entry being overwritten by a later leader. Raft only counts replicas for entries from the leader’s current term; earlier entries become committed indirectly when a current-term entry after them commits. That’s why a new leader commits a blank no-op entry at the start of its term.

Reads need care too. A leader that answers from its own state might have been deposed without knowing (the stale leader). Raft has it exchange heartbeats with a majority before answering a read, or, faster but timing-dependent, rely on a lease.

Paxos

Leslie Lamport’s Paxos came first: written up as “The Part-Time Parliament” (submitted 1990, published 1998), then restated in 2001 as “Paxos Made Simple”, whose entire abstract is “The Paxos algorithm, when presented in plain English, is very simple.” Basic Paxos agrees on one value in two phases, with nodes acting as proposers and acceptors.

Two phases, one value

The rival proposer can’t miss the chosen value: its majority overlaps the one that accepted it.
  1. Prepare. A proposer picks a number n and asks acceptors to promise to ignore anything numbered below n. Each reply includes the highest-numbered proposal that acceptor has already accepted.
  2. Accept. With promises from a majority, the proposer sends accept(n, v), where v is the value of the highest-numbered proposal reported, or its own value if none was. A value accepted by a majority is chosen.

Running one instance per log slot is wasteful, so Multi-Paxos elects a stable leader that runs phase 1 once and then streams phase 2 for each new entry, which is structurally what Raft does. Heidi Howard and Richard Mortier’s 2020 comparison concluded the two are very similar, “differing only in their approach to leader election”: Raft only lets nodes with up-to-date logs become leader, while Paxos lets any node lead and has it catch up during phase 1. Howard’s Flexible Paxos (2016) showed that every phase-1 quorum must intersect every phase-2 quorum, but two phase-2 quorums needn’t intersect each other, which opens up smaller, cheaper write quorums.

Leases

Confirming leadership with a majority on every read costs a round trip. A lease trades that for an assumption about clocks: a majority promises not to elect anyone else for, say, ten seconds, and during that window the leader can serve reads locally. The idea dates to Gray and Cheriton’s 1989 paper on file-cache consistency.

Time as a lock

A lease is safe only if clocks drift within the margin you allowed, and the holder doesn’t freeze past expiry.

The cost lands on failover: a new leader has to wait for the old lease to run out. DynamoDB’s 2022 paper describes exactly this. Each partition’s replicas form a Multi-Paxos group whose leader holds a lease; a newly elected leader won’t serve writes or consistent reads until the previous leader’s lease expires, which “only takes a couple of seconds” but is unavailability all the same. That’s why DynamoDB invested in avoiding false failure detection during gray network failures.

Leases depend on bounded clock drift (rate), not synchronized time, and on the holder not pausing past expiry. A GC pause or a VM migration breaks the second assumption, which is why anything that must not be corrupted also checks a fencing token.

Coordination services

Most teams shouldn’t implement consensus. They run a small consensus cluster and use it for the handful of decisions that need it: who’s leader, which config is current, which nodes are alive. That’s a coordination service.

  • Chubby (Google, 2006) is a lock service built on Paxos, usually five replicas per cell, three of which must be up. Its paper reports one master serving 90,000 clients, and that although it was designed for locks, its most popular use turned out to be naming. Locks are coarse-grained, held “perhaps hours or days”, and holders can pass a sequencer (a fencing token) to the servers they write to.
  • ZooKeeper (Yahoo, 2010) exposes a tree of small files (znodes) with linearizable writes and FIFO order per client, replicated by its Zab protocol. Reads are served by the local replica, so they can be stale unless preceded by sync. Ephemeral znodes vanish when their session ends; sequential znodes get a monotonically increasing suffix; watches notify clients of changes. Locks, leader election and group membership are recipes on top.
  • etcd is a Raft-replicated key-value store with MVCC revisions, leases and watches. Kubernetes keeps all of its cluster state there.

Leader election, outsourced

etcd / ZooKeeper
The lease frees the lock; the revision number stops the old holder from doing damage.

The last step is the one people skip. Jepsen’s 2020 analysis of etcd 3.4.3 found its key-value operations strict serializable, and its locks unsafe: “Multiple processes can hold an etcd lock concurrently, even in healthy clusters with perfectly synchronized clocks.” In one test with 2-second lease TTLs and periodic process pauses, about 18% of acknowledged updates made under the lock were lost. The fix Jepsen recommended is the one in the diagram: use the lock key’s revision as a fencing token and have the protected resource reject lower ones.

Trade-offs

Choice Gains Costs
3 nodes cheapest; 2 acks per commit tolerates 1 failure; a rolling restart leaves no slack
5 nodes tolerates 2 failures, or 1 during maintenance 3 acks per commit; more replication traffic
7+ nodes tolerates 3+ slower commits; leader bandwidth; etcd advises no more than 7
Across regions survives a region loss every commit pays an inter-region round trip
Reads through the log or ReadIndex linearizable, no clock assumptions a majority round trip per read
Lease-based reads local, fast correctness depends on bounded clock drift; slower failover
Short election timeout fast failover spurious elections under load or GC pauses

In the real world

3 of 5servers must be up for a typical Chubby, etcd or ZooKeeper cluster to make progress
150–300 msexample randomized election timeout in the Raft paper
Millionsof Paxos groups DynamoDB runs in a single AWS Region
  • Kafka KRaft. KIP-500 replaced ZooKeeper with a Raft-based quorum of controllers inside Kafka itself, so metadata lives in a replicated log Kafka already knows how to handle. KRaft became production-ready for new clusters in Kafka 3.3 (October 2022), and Kafka 4.0 (March 2025) removed ZooKeeper mode entirely.
  • Elasticsearch 7.0 (2019) replaced its Zen discovery with a new coordination layer, validated with a TLA+ model. Under Zen, operators had to set minimum_master_nodes correctly on every node and remember to change it as the cluster grew, and a wrong value risked inconsistent state and data loss. The new layer manages its own voting configuration, and elections typically finish in well under a second.
  • Cloudflare, November 2, 2020. A switch failed partially. One etcd member’s traffic to the leader went through it, while its traffic to another member didn’t. Members held conflicting views, elections kept tying, and “RAFT leader elections are disruptive, blocking all writes until they’re resolved”. The API and dashboard were impaired for six and a half hours, with API success dropping as low as 75%. Partial connectivity is still an active research topic.
  • GitHub, October 2018. Orchestrator’s Raft quorum correctly promoted the West Coast during a 43-second partition. Consensus did its job; asynchronous database replication was what left two divergent histories.
  • Spanner, CockroachDB, TiKV run one consensus group (Paxos or Raft) per shard, so the write throughput limit of a single leader applies per shard, not per database.

Pitfalls

  • Even cluster sizes. Four nodes tolerate one failure, the same as three, and a 2 | 2 split stops everything. Use 3 or 5.
  • Acknowledging before fsync. Raft’s guarantees assume a node’s vote and log are on stable storage before it replies. Jepsen’s 2025 analysis of NATS found it flushes to disk every two minutes by default while acknowledging writes immediately, so a power loss or quick successive crashes could erase committed writes.
  • Locks without fencing. See etcd above. Leader election through a coordination service tells a process it may lead; storage must still reject the old leader.
  • Check-then-act on stale information. AWS’s October 2025 us-east-1 outage began when a delayed DynamoDB DNS “Enactor” applied an old plan over a newer one. Its check that the plan was newer had run at the start and “was stale by this time”, and a cleanup job then deleted the plan that was live, leaving an empty DNS record. A version check at the moment of the write is a fencing token by another name.
  • Too-short timeouts. An election timeout close to the network’s worst round trip, or to a GC pause, turns load spikes into leader churn, and every election blocks writes.
  • Consensus on the hot path. Every decision funnels through one leader and waits on a majority’s disks. Use it for metadata and coordination, or run one group per shard.
  • Being too available. Google’s SRE book describes deliberately taking the global Chubby down in any quarter where real failures hadn’t brought it down to its SLO, so services couldn’t quietly come to depend on it never failing.

Recall

Go deeper

Keep going

The atomic notes for this lesson live in the knowledge graph:

Next on the map: Message Brokers & Logs (Kafka, a replicated log you can build systems on) and Distributed Transactions (agreeing on commit across shards).

Done with this lesson?

Mark it learned and the concepts it teaches will light up in your galaxy.

Distributed Systems: roadmapBack to the roadmap