Consensus (Paxos / Raft)
Consensus is the problem of getting multiple distributed nodes to agree on a single value despite crashes, message loss, and reordering. Paxos (Lamport, 1998) and Raft (Ongaro & Ousterhout, 2014) are the two algorithms that solve this safely: they guarantee that the agreed value is never wrong (safety) and that the system eventually agrees as long as a majority of nodes can communicate (liveness, modulo FLP). Every strongly consistent distributed database, lock service, and configuration store is built on one of these or a variant.
How it works
The consensus problem is deceptively simple to state: given N nodes, can they agree on a single value? The constraints make it hard:
- Safety: only one value may be chosen, and once chosen, it never changes. No two nodes should ever disagree on the outcome.
- Liveness: as long as a majority of nodes are reachable, the system eventually makes progress.
- Fault tolerance: the system tolerates
ffailures with2f+1nodes (a majority must survive).
The FLP impossibility result (Fischer, Lynch, Paterson, 1985) proves that no asynchronous deterministic protocol can guarantee both safety and liveness if even one node may crash. In practice, real systems (Paxos, Raft) sidestep FLP by adding randomness (leader election with randomized timeouts) and accepting that liveness may stall for bounded periods under bad network conditions — but safety is never violated.
Paxos (Lamport, 1998) is the canonical consensus algorithm. It is famously hard to understand — Lamport himself wrote 'Paxos Made Simple' and 'Paxos Made Live' to explain it. The core idea:
- A proposer suggests a value with a unique proposal number.
- Acceptors promise to reject proposals with lower numbers, and accept the highest-numbered proposal they have seen.
- Once a majority of acceptors accept, the value is chosen — it cannot be unchosen.
- A learner discovers the chosen value and announces it.
Multi-Paxos extends this to a sequence of values (a log) by reusing a stable leader to skip the prepare phase for subsequent entries. Modern systems rarely implement raw Paxos; they implement Multi-Paxos with optimizations (e.g., Fast Paxos, EPaxos) or use Raft.
Raft was designed specifically for understandability. It decomposes consensus into three sub-problems: leader election (randomized timeouts), log replication (AppendEntries RPCs), and safety (terms and majority commits). The result is algorithmically equivalent to Multi-Paxos but dramatically easier to teach, implement, and debug — which is why every modern consensus system (etcd, Consul, CockroachDB, TiKV) uses Raft.
Two majorities cannot exist simultaneously. If 5 nodes vote for value A and a different 5 vote for value B, the two groups must share at least one node — which would have to vote for both, contradicting safety. This is why every consensus protocol requires a majority quorum and tolerates f failures with 2f+1 nodes: the smallest set that cannot simultaneously agree on two conflicting values. It is also why cluster sizes are odd (3, 5, 7) — adding one node to an even-sized cluster does not increase fault tolerance.
Raft's central trick is the term — a monotonically increasing integer that serves as a logical clock for leadership. Every election starts a new term; every RPC carries the sender's current term. If a node sees a higher term than its own, it immediately reverts to follower — this is how a stale leader learns it has been deposed.
The flow for a single write:
- Client sends write to the leader.
- Leader appends the entry to its log (uncommitted).
- Leader sends
AppendEntriesRPC to all followers in parallel. - Followers append the entry and reply with success.
- Once a majority replies, the leader commits the entry (marks it durable) and applies it to its state machine.
- Leader replies to the client with success.
- Leader includes the commit index in the next
AppendEntries, so followers learn the entry is committed.
A read on the leader is 'free' but may be stale (the leader might have been deposed and not yet know). For strongly consistent reads, Raft systems add a read index round-trip: the leader confirms it is still leader (by getting heartbeats from a majority) before serving the read. This is why strongly consistent reads on etcd have higher latency than writes — they require a quorum check too.
What can go wrong in practice:
- Network partition with quorum: 3-node cluster partitions 2/1. The 2-node side has quorum, elects a new leader, accepts writes. The 1-node side has no quorum, accepts no writes. On heal, the 1-node side catches up. This is correct behavior.
- Network partition without quorum: 5-node cluster partitions 2/3. Both sides have a majority? No — only 3 has quorum. The 2-node side blocks. This is why 5-node clusters tolerate 2 failures, not 3 (3-failure would partition 0/5 or 1/4 — neither side of a 2/3 split has majority in the failed sense).
- Split-brain: two leaders in different terms. Raft's term numbering prevents this — the older leader is forced to step down when it sees a higher term. The newer leader's commits win.
- Livelock: candidate elections keep timing out and conflicting. Mitigated by randomized election timeouts (150-300ms) so collisions are unlikely to repeat.
- Slow disk: a leader that cannot fsync its log cannot commit — disk latency is a hard floor on Raft throughput.
Why do Raft and Paxos require a majority quorum (N/2 + 1) rather than, say, two-thirds or three-quarters?
Pick one answer.
A 5-node Raft cluster partitions 3 nodes on one side and 2 on the other. What happens on each side?
Pick one answer.
What does the FLP impossibility result actually prove, and how do real consensus protocols (Paxos, Raft) get around it?
Pick one answer.
Engineering mental model
Mental model. Think of Consensus (Paxos / Raft) as a deliberate boundary in a system. The boundary exists because something becomes harder to manage when everything is done in one place: latency, scale, failure isolation, consistency, cost, or team ownership. The useful question is not “what does Consensus (Paxos / Raft) mean?” but “what pressure makes this boundary worth introducing, and what new failure mode does it create?”
Before choosing Consensus (Paxos / Raft), name the workload, the critical user path, the dominant bottleneck, the failure you are trying to absorb, and the trade-off you are willing to accept. If you cannot name those five things, the design is probably premature.
// Pseudocode
request = receive()
result = consensus(request)
return result
// Production questions:
// 1. What happens on timeout?
// 2. Can this operation be retried safely?
// 3. What is the bottleneck?Back-of-the-envelope reasoning
Example: with 5 replicas, a majority quorum is 3. Losing 2 replicas still leaves a majority available for a quorum-based protocol.
Interactive thought experiment: Consensus (Paxos / Raft)
Change the variables below and predict what breaks first in Consensus (Paxos / Raft). The production lab can later reuse these same inputs.
Change one variable at a time. Predict the failure mode first, then move the slider and see whether your mental model matches the simplified system response.
If you are stuck on Consensus (Paxos / Raft), start by drawing the request path and marking every network hop, stateful component, queue, cache and failure boundary. Then estimate where the system will saturate.
You increase traffic by 10× in a system using Consensus (Paxos / Raft). What should you inspect first?
Pick one answer.
Which statement is the safest engineering habit when using Consensus (Paxos / Raft)?
Pick one answer.
You have dashboards for traffic, latency, errors and saturation. You can change the architecture, but every change has operational cost.
Production scenario: your system uses Consensus (Paxos / Raft), traffic suddenly spikes, and p99 latency doubles. What is your first move?
Interview drill
Answer this without notes: When would you choose Consensus (Paxos / Raft), and when would you intentionally avoid it? Mention at least one bottleneck it addresses, one failure mode it introduces, and one alternative. Then quantify the workload you are designing for.
A useful engineering lens for Consensus (Paxos / Raft): define the problem it solves, the simpler design that fails first, the constraint that forces you to introduce this concept, and the new failure modes the concept creates.
Numerical sanity check
Back-of-the-envelope reasoning beats fake precision. State your traffic, payload, concurrency and growth assumptions explicitly, then calculate enough to know whether the current architecture is orders of magnitude away from the target.
Do not optimize for a memorized definition. Reason from the workload and failure mode.
Imagine the simplest version of a system using Consensus (Paxos / Raft). What breaks first as traffic grows by 10×, and what would you change before reaching 100×?
Pick one answer.
What you gain, what you pay
- +Safety is absolute — once a value is chosen, it never changes; no two nodes disagree on committed values.
- +Tolerates minority failures (N/2 - 1 nodes can crash) without downtime.
- +Foundation for every linearizable distributed system — locks, leader election, replicated state machines.
- +Raft is well-understood and has multiple battle-tested open-source implementations (etcd, TiKV, CockroachDB).
- −Every write requires a majority round-trip — latency is at least one network RTT plus fsync time.
- −Throughput is bounded by the leader (single-writer bottleneck); multi-leader variants (EPaxos) are complex.
- −Cluster size is odd and small (3, 5, 7) — large clusters slow down without improving fault tolerance.
- −Liveness can stall under network partition or livelock — FLP is a real bound, even if rare in practice.
- −Operations complexity: monitoring, reconfiguration, membership changes are non-trivial.
How this breaks in production
- Leader crash mid-term — election timeout fires; cluster pauses writes for 150-300ms until new leader elected.
- Network partition without quorum — both sides block until healed (correct, but visible as downtime).
- Livelock from election timeout collisions — randomized timeouts mitigate but do not eliminate.
- Slow disk on leader — fsync latency caps throughput; leader becomes the bottleneck.
- Membership change mishandled — adding/removing nodes naively can create two majorities (joint consensus is the safe path).
- Byzantine faults — Raft and Paxos assume crash-stop; Byzantine faults require PBFT-style protocols (3f+1 nodes).
Don't fall into these traps
- •Running consensus on even-sized clusters (4, 6) — partitions like 2/2 leave no quorum; odd is better.
- •Treating reads on the leader as strongly consistent without a read-index round — they can be stale.
- •Configuring election timeouts too short — false elections under load; too long — slow failover.
- •Using consensus for high-throughput writes when eventual consistency would do — pays the latency cost for nothing.
- •Forgetting that fsync latency is a floor on commit throughput — slow disk = slow consensus.
- •Adding nodes to a cluster without joint consensus — can split-brain.
Real systems using this
How real systems implement this
- etcd — Raft-based strongly consistent KV store that backs Kubernetes. Every API server write goes through Raft consensus. Cluster sizes are typically 3 or 5; odd to maximize fault tolerance.
- CockroachDB — Each 'range' of data is replicated across 3+ nodes via Raft. Writes commit when a majority of the range's replicas agree. Strong consistency across geo-distributed datacenters, with latency as the trade-off.
- Apache ZooKeeper — Uses ZAB (ZooKeeper Atomic Broadcast), a Paxos variant optimized for primary-backup replication. A single leader accepts writes, replicates to followers, commits on quorum ack. Used by Kafka (pre-KRaft), HBase, and many Hadoop-era systems.
- Kafka KRaft — Replaced ZooKeeper in Kafka 3.x. Uses Raft to elect a controller that manages broker metadata. Removes the external ZooKeeper dependency and reduces failure domains.
Practice saying it out loud
- Q1Explain the difference between Paxos and Raft. Why did Raft displace Paxos in most modern systems?
- Q2Walk through what happens when a Raft leader crashes. How does the cluster recover, and what is the visible downtime?
- Q3Why do consensus clusters use odd numbers of nodes (3, 5, 7)? What goes wrong with even numbers?
- Q4What is the FLP impossibility result, and how do Paxos/Raft work around it?
- Q5Why are strongly consistent reads on a Raft leader more expensive than reads on a follower? How do you make reads strongly consistent?
Further reading & references
Core explanations are original NO CAP material. External references are provided for deeper study and standards.
What next?
Mark as understood once the mental model clicks.
Next recommended
Leader Election