← Back to System Internals

Consensus: Raft & Paxos

A system design interview guide to distributed consensus — how a set of unreliable nodes agree on a single ordered log of commands, why the problem is provably hard, and exactly how Raft and Paxos solve it.

Consensus is the beating heart of every strongly consistent distributed system. A lock service, a configuration store, a database that promises linearizable writes — underneath each one is a group of nodes that must agree, and keep agreeing, on one authoritative sequence of decisions even as machines crash and networks drop packets. This is the same quorum core that the companion guide Zero Data Loss During a Network Partition leans on to survive a split; here we go one level deeper and open up the algorithms themselves. We will build the replicated-state-machine model, confront the FLP impossibility result that says perfect consensus is unattainable in a fully asynchronous world, and then walk through Raft — election and log replication, line by line — and Paxos — the original single-decree protocol and the Multi-Paxos form that real systems ship. The goal is precision: this is a topic where a hand-wave is instantly visible, and where getting the commit rule, the election restriction, and the two Paxos phases exactly right is the seniority tell.

1. What Consensus Is & Why It’s Hard

The clean way to frame consensus is the replicated state machine (RSM). Imagine a deterministic state machine — a key-value store, say — and run an identical copy on each of several nodes. If every copy starts in the same state and applies the same commands in the same order, every copy ends in the same state. That reduces “keep these replicas identical” to one problem: agree on an ordered log of commands. Consensus is the machinery that makes all correct nodes agree on that log, entry by entry, so that a client talking to any replica sees one consistent history.

Formally, a consensus protocol must satisfy three properties:

• Agreement. No two correct nodes decide on different values for the same log slot. This is the safety property that must never break.
• Validity (integrity). A decided value must be one that was actually proposed by some node — the protocol cannot invent values out of thin air, and a node decides at most once per slot.
• Termination. Every correct node eventually decides. This is the liveness property — the system must make progress, not stall forever.

Why is this hard? Because of a deep result: the FLP impossibility (Fischer, Lynch & Paterson, 1985). It proves that in a fully asynchronous system — one with no bound on message delay or relative processor speed — there is no deterministic protocol that guarantees both safety and termination if even a single node may crash. The intuition: you can never distinguish a crashed node from one that is merely slow, so any protocol that waits for it can hang forever, and any protocol that gives up on it can be tricked into disagreeing. FLP does not say consensus is usually impossible — it says you cannot guarantee it will always terminate in a purely async model.

Real systems escape FLP not by breaking it but by weakening its assumptions. They assume partial synchrony: the network is asynchronous during bad periods but eventually behaves well enough (bounded delays) for long enough to make progress. On top of that they add timeouts (to suspect crashed nodes) and, in Paxos-style protocols, a touch of randomization (Raft randomizes election timeouts). The crucial design discipline is this: these mechanisms are used only to preserve liveness. Safety — agreement — never depends on any timing assumption. A slow network or a bad timeout can delay a decision; it can never cause two nodes to decide differently.

2. Safety, Liveness & Majority Quorums

Two ideas do the heavy lifting throughout every consensus protocol: the split between safety and liveness, and the algebra of majority quorums.

Safety vs liveness

• Safety — “nothing bad ever happens.” The committed log never forks; two nodes never disagree on a decided slot; a committed entry is never lost or overwritten. Safety must hold under every failure and every timing, including adversarial network delays.
• Liveness — “something good eventually happens.” The system eventually elects a leader and commits new entries. Liveness is what FLP forbids us from guaranteeing absolutely; we settle for “makes progress whenever the network is well-behaved.”

The failure model

Raft and Paxos assume the crash-stop (a.k.a. crash-recovery / fail-stop) model: nodes may crash, pause, restart, and lose in-flight messages, but they never lie — a node always follows the protocol correctly or does nothing. Messages may be lost, delayed, reordered, or duplicated, but not corrupted or forged. This is the right model for a datacenter fleet.

A different, harder class assumes Byzantine faults, where a node may behave arbitrarily — buggy, compromised, or actively malicious, sending different answers to different peers. Tolerating that requires Byzantine fault-tolerant (BFT) protocols such as PBFT or the ones underpinning blockchains, which need 3f + 1 nodes to tolerate f liars (not 2f + 1) and cost more rounds. Unless the interviewer raises trust between nodes, stay in the crash-stop world — but naming that Byzantine is a distinct, more expensive class shows range.

Why majorities

Both algorithms commit a decision only when a majority (a quorum of more than half the nodes) agrees. The reason is a single, beautiful fact: any two majorities of the same set must intersect in at least one node. With N = 2f + 1 nodes, a majority is f + 1, and two subsets of size f + 1 from a set of 2f + 1 cannot be disjoint — together they would need 2f + 2 > 2f + 1 distinct nodes. That overlap is what carries information forward: whatever a previous majority decided, the next majority is guaranteed to contain a node that witnessed it, so it cannot decide something contradictory.

• Fault tolerance. With 2f + 1 nodes you tolerate f failures and still form a majority from the survivors. N = 3 tolerates 1; N = 5 tolerates 2.
• No split brain. A partition cannot produce two majorities, so at most one side can make progress. This is the structural root of single-leader safety.
• Odd is best. An even N buys no extra tolerance over the odd number below it (N = 4 still tolerates only 1, same as N = 3) while making every quorum larger and slower — so clusters are almost always sized 3, 5, or 7.

3. Raft: Leader Election

Raft was designed for understandability, and it earns that by decomposing consensus into two mostly-independent pieces: leader election and log replication. Everything flows through a single elected leader, which turns the abstract “agree on an order” into the concrete “the leader picks the order and everyone copies it.” This section covers how that leader is chosen safely.

Every node is always in one of three roles:

• Follower — passive. It responds to the leader’s and candidates’ RPCs but issues none of its own. It expects to hear from the leader periodically (heartbeats).
• Candidate — a follower that suspected the leader died and is now campaigning for votes.
• Leader — the single node that handles all client writes and drives replication. There is at most one leader per term.

Terms as a logical clock

Time in Raft is divided into terms, numbered with consecutive integers. Each term begins with an election. If a candidate wins, it serves as leader for the rest of that term; if the vote splits, the term ends with no leader and a new term (a new election) begins. Every RPC carries the sender’s term. Terms act as a logical clock that lets nodes detect stale information: if a node receives a message with a term higher than its own, it updates to that term and reverts to follower; if it receives one with a lower term, it rejects it. This single rule — higher term wins, lower term is refused — is how an old, partitioned leader is harmlessly retired the moment it rejoins.

The election

A follower keeps a randomized election timeout (typically 150–300 ms). Each heartbeat (an empty AppendEntries) from the current leader resets it. If the timeout elapses with no heartbeat, the follower assumes the leader is gone and starts an election:

1. It increments currentTerm, transitions to candidate, and votes for itself.
2. It sends RequestVote RPCs to all other nodes in parallel.
3. Each node grants at most 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 (the election restriction, detailed in §4).
4. If the candidate collects votes from a majority, it becomes leader and immediately sends heartbeats to assert authority and stop other elections.

Three outcomes are possible: the candidate wins; another node wins first (the candidate discovers a legitimate leader via an AppendEntries with a term ≥ its own, and reverts to follower); or nobody wins because the vote split. Randomized timeouts are the elegant fix for split votes — because each node waits a different, random amount before campaigning again, one node almost always times out first, wins uncontested, and the cluster converges quickly rather than dueling forever.

4. Raft: Log Replication & Commit

Once a leader is in charge, client commands become log entries and the leader replicates them. This is where the exact rules matter, and where interviews probe hardest.

Each entry stores a command, the term in which the leader created it, and its index (position in the log). The leader appends a new entry locally, then sends AppendEntries RPCs to followers to replicate it. An AppendEntries carries not just the new entry but also the index and term of the entry immediately preceding it (prevLogIndex, prevLogTerm), which enables a consistency check.

The Log Matching Property

Raft maintains a strong invariant that keeps logs consistent without expensive comparison: if two logs contain an entry with the same index and term, then (a) they store the same command at that index, and (b) all preceding entries are identical. Part (a) holds because a leader creates at most one entry per index per term and never changes it. Part (b) is enforced by the AppendEntries consistency check: a follower rejects the RPC unless its log already contains an entry matching the leader’s prevLogIndex/prevLogTerm. By induction, a successful append implies the logs agree on everything up to that point.

The commit rule (get this exactly right)

An entry is committed — safe to apply to the state machine and acknowledge to the client — when both conditions hold:

1. The entry is stored on a majority of servers (durably); and
2. The entry was created in the leader’s current term.

The second clause is subtle and famous. A leader may not conclude that an entry from a previous term is committed merely because it now sits on a majority — doing so can lead to a committed entry being overwritten (the scenario in Figure 8 of the Raft paper). Instead, a new leader commits entries from earlier terms only indirectly: once it commits an entry from its own current term (which is on a majority), the Log Matching Property means all preceding entries are committed too. In practice a new leader appends a no-op entry in its term at the start of its reign precisely to carry older entries across this bar. Once commitIndex advances, each node applies newly committed entries to its state machine in log order.

The election restriction (leader completeness)

How do we guarantee a new leader has every committed entry, so nothing already promised to a client is lost? Through a restriction on voting: a node grants its vote only to a candidate whose log is at least as up-to-date as its own. “Up-to-date” is defined by the last entry: a higher last-term wins; if the last terms tie, the longer log wins. Because a committed entry sits on a majority, and any election-winning candidate also needs a majority, those two majorities intersect — so at least one voter holds every committed entry and would refuse to vote for a candidate missing it. Therefore any candidate that can win an election already contains all committed entries. This is the Leader Completeness property, and it is why Raft never needs to ship committed entries “backward” from followers to a new leader.

Repairing follower logs

Followers can fall behind or hold uncommitted entries from a deposed leader. The leader reconciles each follower with a per-follower nextIndex (the next entry it expects to send). If an AppendEntries is rejected because the consistency check failed, the leader decrements nextIndex and retries, walking backward until it finds the last point where the logs agree; from there it overwrites any conflicting follower entries with its own. Uncommitted entries can be overwritten safely — only committed ones are sacred, and Leader Completeness guarantees the leader has all of those. The pseudocode below is the follower’s side of that handshake.

function handle_append_entries(req):
  # 1. Reject anything from a stale leader.
  if req.term < currentTerm:
    return {term: currentTerm, success: false}

  if req.term > currentTerm:
    currentTerm = req.term                    # adopt newer term...
  role = FOLLOWER                             # ...and accept this leader
  reset_election_timer()                      # valid RPC = leader is alive

  # 2. Consistency check: our log must match at prevLogIndex.
  if req.prevLogIndex > last_index() or
     log[req.prevLogIndex].term != req.prevLogTerm:
    return {term: currentTerm, success: false} # leader will back off nextIndex

  # 3. Append: overwrite conflicts, then add new entries.
  for entry in req.entries:
    if log[entry.index] exists and log[entry.index].term != entry.term:
      truncate_log_from(entry.index)          # drop conflicting suffix
    if entry.index > last_index():
      log.append(entry)

  # 4. Advance commit index up to the leader's, then apply.
  if req.leaderCommit > commitIndex:
    commitIndex = min(req.leaderCommit, last_index())
    apply_committed_entries_to_state_machine()

  return {term: currentTerm, success: true}

5. Raft: Safety, Membership & Snapshots

The election restriction plus the commit rule together give Raft its central safety guarantee, the State Machine Safety Property: if any node has applied a log entry at a given index to its state machine, no other node will ever apply a different entry for that index. In other words, all state machines execute exactly the same commands in exactly the same order. Everything in §3–§4 exists to uphold this one line.

Membership changes

Adding or removing servers is dangerous because you cannot switch every node’s notion of “the cluster” atomically — during the switch, two different majorities could form (one under the old config, one under the new) and elect two leaders. Raft offers two safe approaches:

• Joint consensus (the original). The cluster transitions through an intermediate configuration C<old,new> in which decisions require majorities from both the old and new configurations simultaneously. Because no decision can be made without overlap in both, no two disjoint majorities can form during the change. Once C<old,new> is committed, the cluster moves to C<new>.
• Single-server changes (the common simplification). Add or remove exactly one node at a time. Changing membership by a single server can never create two disjoint majorities (the old and new majorities always overlap), so this avoids the joint-consensus machinery and is what most implementations use.

Log compaction with snapshots

A log that only ever grows will exhaust disk and make restarts slow. Snapshotting solves this: each node periodically writes its current state-machine state to a snapshot and discards all log entries up to that point. The snapshot records the lastIncludedIndex and lastIncludedTerm so the log-matching check still works at the boundary. If a follower is so far behind that the leader has already discarded the entries it needs, the leader ships the whole snapshot via an InstallSnapshot RPC instead of individual entries. Snapshotting is orthogonal to consensus — it is a space optimization — but it is essential for any long-running system.

6. Basic Paxos: Single-Decree

Paxos, from Leslie Lamport, is the original consensus protocol and the theoretical bedrock the whole field rests on. It is famously slippery to grasp, but the core — Basic (single-decree) Paxos — solves exactly one question: how does a set of nodes agree on a single value, despite crashes and message loss? Multi-Paxos (§7) then chains this to build a log.

There are three roles (a single process usually plays several):

• Proposers propose values (e.g. client commands).
• Acceptors form the quorum; they vote on proposals and are the protocol’s memory. A value is chosen only when a majority of acceptors accept it.
• Learners observe which value was chosen and act on it (e.g. apply it to the state machine).

The subtlety Paxos must handle: multiple proposers may propose concurrently, and messages may be lost or delayed arbitrarily, yet once a value is chosen, no different value may ever be chosen. It achieves this with totally ordered proposal numbers (globally unique, e.g. a counter paired with the proposer’s id) and two phases.

Phase 1 — Prepare / Promise

A proposer picks a proposal number n higher than any it has used and sends Prepare(n) to a majority of acceptors. An acceptor that receives Prepare(n):

• ignores it if it has already promised a number ≥ n (a newer proposer got there first); otherwise
• promises never to accept any proposal numbered less than n, and
• returns the highest-numbered proposal it has already accepted, if any (the value plus its number), so the new proposer can learn about in-flight decisions.

Phase 2 — Accept / Accepted

If the proposer gets promises from a majority, it sends Accept(n, v). The value v is not freely chosen — this is the crux of correctness:

• If any acceptor in the promise responses reported a previously accepted value, the proposer must use the value with the highest proposal number among them — it re-proposes the potentially-chosen value rather than its own.
• Only if no acceptor had accepted anything may the proposer use its own value.

An acceptor receiving Accept(n, v) accepts it (records (n, v)) unless it has meanwhile promised a higher number. Once a majority accepts (n, v), v is chosen; learners are informed.

Why it is safe

Suppose value v was chosen at number n — that means a majority accepted it. Any later proposal at a higher number n' > n must first complete Phase 1 with its own majority. That majority intersects the majority that accepted v, so at least one acceptor in it will report v (with number n) in its promise. By the Phase 2 rule, the new proposer is forced to re-propose v. By induction, every proposal numbered ≥ n proposes v, so no different value can ever be chosen. That is the whole game — majority intersection plus “re-propose what might already be chosen” makes a decision irreversible.

function propose(value):
  n = next_unique_proposal_number()           # globally ordered, e.g. (counter, node_id)

  # --- Phase 1: Prepare / Promise ---
  send Prepare(n) to all acceptors
  wait for Promise replies from a majority     # else back off, bump n, retry

  # Adopt the highest-numbered value any acceptor already accepted.
  prior = highest_numbered_accepted(replies)   # may be none
  v = prior.value if prior exists else value   # cannot pick own value if one exists

  # --- Phase 2: Accept / Accepted ---
  send Accept(n, v) to all acceptors
  wait for Accepted replies from a majority     # any acceptor that promised > n rejects
  return v is CHOSEN                            # a majority accepted (n, v)

Note Basic Paxos guarantees safety but not liveness: two proposers can leapfrog each other’s numbers forever (dueling proposers), each invalidating the other’s promises. FLP in action — and the fix is exactly what Multi-Paxos does next: pick one distinguished proposer.

7. Multi-Paxos: The Practical Form

Basic Paxos decides one value. A real system needs to decide an endless sequence of values — a replicated log, one Paxos instance per log slot. Running full two-phase Paxos for every entry would cost two round trips per command and invite dueling proposers. Multi-Paxos is the optimization that makes Paxos practical, and it converges on the same shape as Raft.

The key insight: elect a stable leader (a “distinguished proposer”) and let it skip Phase 1 in steady state. Here is why that is sound:

• Phase 1 (Prepare/Promise) is fundamentally about acquiring the right to propose and learning about in-flight values. A proposer can run Phase 1 once, for a proposal number n, covering all future log slots at once — effectively “I am the leader for number n; promise me for every slot.”
• Having done that, the leader replicates each new command with only Phase 2 (Accept(n, v) → Accepted) — a single round trip to a majority per entry, just like Raft’s AppendEntries.
• Phase 1 is re-run only when leadership changes — a new would-be leader picks a higher number and prepares, which fences out the old leader (any acceptor that promised the new number will reject the old leader’s accepts). This is the same “higher number/term wins” fencing that Raft gets from terms.

In this steady state Multi-Paxos and Raft are near-isomorphic: a single leader, a monotonic epoch (proposal number / term), one round trip to a majority per commit, and re-election on leader failure. The historical difference is that Paxos left leader election, log management, and membership changes as exercises for the implementer — which is precisely the gap Raft filled by prescribing them. Production Paxos systems (Chubby, Spanner) build substantial machinery around Basic Paxos to get there; Raft bakes it in.

8. Raft vs Paxos

They solve the identical problem — agreement on a replicated log — with the identical quorum core (majority intersection). The differences are about structure and pedagogy, not power.

A close cousin worth naming is ZAB (ZooKeeper Atomic Broadcast), which powers ZooKeeper. ZAB is not Paxos but solves the same problem with a leader-based, log-replication design very much in Raft’s spirit (a leader broadcasts totally-ordered transactions, epochs fence stale leaders). If asked “which should I use,” the honest answer is: reach for a battle-tested implementation (etcd/ZooKeeper) rather than writing your own — and if you must reason about one in an interview, explain Raft, because its structure maps directly to the guarantees.

9. Practical Concerns & Summary

Consensus has a few operational realities that separate a textbook answer from a deployable one.

• Reads without stale data. Writes go through the log, but naively serving a read from the leader can return stale data if that “leader” was silently deposed during a partition. Two standard fixes: a leader lease (the leader holds a time-bounded lease renewed by heartbeats, and only serves local reads while the lease is valid — correct only under bounded clock drift), or ReadIndex (the leader records its current commitIndex, confirms it is still leader by exchanging a heartbeat round with a majority, then serves the read once it has applied up to that index — safe without clock assumptions, at the cost of one round trip). Reads are otherwise the cheap operation; the write path is where consensus is paid for.
• Latency is one round trip to a majority per commit. Every committed entry costs at least one RTT from the leader to the nearest majority (plus a durable write). Within a datacenter that is sub-millisecond; across regions it is tens of milliseconds — the cost detailed in the zero-data-loss guide. You reach the closest majority, so replica placement matters.
• Size clusters odd. As §2 showed, an even number of nodes is wasteful — it enlarges the quorum without improving fault tolerance. Use 3, 5, or 7.
• Scale by sharding. A single Raft/Paxos group has a single leader and therefore a write ceiling. Horizontal scale comes from partitioning the keyspace into many independent consensus groups (one leader each) — the model used by CockroachDB, TiKV, and Spanner.
• Consensus is a coordination primitive, not a database. It is expensive; use it for the few things that truly need agreement (leader election, configuration, the commit order of critical data) and keep it off the bulk data path. This is exactly the distributed lock / leader election use case — a lock service is a thin veneer over a consensus group.