Paxos vs Raft, and why consensus is hard

Every strongly consistent distributed database (etcd, Spanner, CockroachDB, TiKV, ZooKeeper, Consul) is built on one primitive: getting a group of machines to agree on a sequence of values, even when some of them crash and the network loses, delays and reorders messages. That primitive is consensus, and it is famously hard: provably impossible to guarantee in full, and notoriously easy to get subtly wrong.

This article covers what consensus must guarantee and the impossibility result that bounds it, then Paxos and why it is safe, then Raft, which reorganised the same ideas to be understandable, including elections, log repair and membership changes. It finishes with what “linearizable” actually promises clients. The figures follow the protocols message by message.

What consensus must guarantee

A set of processes each propose a value and must decide on one. A correct algorithm guarantees:

• Agreement: no two processes decide differently.
• Validity: the decided value was proposed by someone, so the trivial “always decide 0” is ruled out.
• Termination: every non-faulty process eventually decides.

Agreement and validity are safety properties: nothing bad ever happens. Termination is a liveness property: something good eventually happens. Repeat consensus for slot 1, slot 2, slot 3 and so on, and you get a replicated log. Feed the log to identical deterministic state machines and you get state machine replication: a service that behaves like a single machine but survives the loss of some of its replicas.

FLP: why it can’t be guaranteed

Fischer, Lynch and Paterson (1985) proved that in an asynchronous system, where messages can be delayed arbitrarily long and there are no clocks to bound delays, no deterministic algorithm can guarantee consensus if even one process may crash. The reason is that a very slow process is indistinguishable from a dead one. An adversarial schedule can always delay exactly the message that would let the algorithm decide, keeping it undecided forever.

FLP doesn’t say consensus is useless. It says you must give something up, and practical systems give up guaranteed termination, never safety. Paxos and Raft are always safe, and they make progress whenever the network behaves reasonably for long enough, the partial synchrony model of Dwork, Lynch and Stockmeyer (1988). Randomisation, like Raft’s random election timeouts, makes the adversarial schedules vanishingly unlikely.

Quorums

Both Paxos and Raft rest on one combinatorial fact: any two majorities of the same set intersect. If every decision needs acknowledgements from a majority, then any later decision’s majority contains at least one node that saw the earlier one. That node carries the memory of the past forward. To tolerate f crashed nodes, you need 2f + 1: 3 nodes survive one failure, 5 survive two.

Paxos

Lamport’s Paxos (described in 1989, published in 1998, and re-explained plainly in “Paxos Made Simple”, 2001) decides a single value in two phases. Proposals carry unique, increasing ballot numbers.

1. Prepare / promise. A proposer picks ballot n and asks acceptors to promise to ignore any proposal numbered below n. Each acceptor that promises also reports the highest-numbered value it has already accepted, if any.
2. Accept / accepted. With promises from a majority, the proposer sends accept(n, v). Here v must be the value from the highest-numbered acceptance reported in phase 1. Only if none was reported may it propose its own value. When a majority accepts, v is chosen.

That “must re-propose” rule is the whole safety argument. Once a majority has accepted v at ballot n, any proposer with a higher ballot will hear about v from the node where the two majorities intersect, and will propose v itself. A chosen value can never be replaced.

Multi-Paxos

Running two phases for every log slot is wasteful. Multi-Paxos elects a stable leader that runs phase 1 once, for all future slots at once, and then needs only phase 2 for each new entry, one round trip to a majority. This is how Paxos is actually deployed (Chubby, Spanner). But “Paxos Made Simple” describes only single-decree Paxos, and the leader election, log compaction, membership changes and gap handling needed for a real log are left to the implementer. Google’s “Paxos Made Live” (Chandra et al., 2007) describes how much engineering that took.

Raft: terms and elections

Raft (Ongaro & Ousterhout, 2014) was designed explicitly for understandability. It specifies the whole replicated log, not just one decision, and it structures the problem around a strong leader. Time is divided into numbered terms, each with at most one leader. Every message carries the sender’s term, and any node that sees a higher term immediately adopts it and becomes a follower. That single rule removes stale leaders.

Followers expect regular heartbeats from the leader. If none arrives within an election timeout, randomised (the paper suggests 150–300 ms), a follower becomes a candidate: it increments the term, votes for itself and asks everyone else for a vote. Each node grants at most one vote per term, and only to a candidate whose log is at least as up to date as its own. A candidate with a majority becomes leader.

Raft: log replication

The leader appends client commands to its log and sends them to followers with AppendEntries. Each request includes the index and term of the entry just before the new ones. A follower accepts only if its own log has a matching entry there. If not, the leader steps back and retries with earlier entries until the logs agree, then overwrites the follower’s conflicting suffix. This consistency check gives the Log Matching Property: if two logs contain an entry with the same index and term, they are identical up to that index.

An entry is committed once the leader has stored it on a majority, and committed entries are applied to the state machine. There is one subtle exception, Figure 8 in the paper. A leader may only count replicas to commit entries from its own term. Older entries become committed indirectly, when a current-term entry after them is. The voting rule (“only up-to-date candidates win”) then guarantees that every future leader holds every committed entry: Leader Completeness.

Fig. 3 also shows why a leader must not answer reads from its own state without checking. During the partition, S1 still believes it leads term 3. If a client asked it for y, it would answer 9, a value that was never committed and is about to disappear.

Changing membership

Adding or removing servers is itself dangerous. Switch directly from configuration C_old to C_new, and during the transition a majority of the old set and a separate majority of the new set could both exist, and elect two leaders in the same term. Raft’s original answer is joint consensus: an intermediate configuration C_old,new in which every decision needs a majority of both sets, committed as a log entry before switching to C_new. Ongaro’s thesis later presented a simpler alternative: change one server at a time, because any majority of the old set and any majority of a set differing by one server must intersect.

What linearizable actually means

Linearizability (Herlihy & Wing, 1990) is the guarantee consensus-backed stores usually promise. Every operation appears to take effect atomically at some instant between its invocation and its response, and those instants are consistent with real time. If a write completes before a read begins, the read sees the write or something newer. It is the strongest single-object consistency model, and it is what makes a replicated system behave like one machine.

Writes get it for free through the log. Reads are the trap, because skipping the log is tempting for speed:

• Read through the log. Append the read as an entry and answer when it commits. Correct, and slow.
• ReadIndex. The leader records its commit index, confirms it is still leader with one round of heartbeats to a majority, waits until that index is applied, then answers locally. One round trip, no disk write.
• Leases. Followers promise not to elect a new leader for a lease period, so the leader can answer reads with no round trip at all, but only if clock drift is bounded. Safety now depends on timing, the very assumption consensus was designed to avoid.
• Follower reads. Serving from followers scales reads but returns possibly stale data unless the follower first confirms it has caught up to the leader’s commit index.

Paxos vs Raft in practice

Howard and Mortier (2020) compared the two carefully and concluded they are far more alike than their reputations suggest. Both use a leader, quorums, and a numbered epoch (ballot or term). The main difference is leader election. Raft only lets a node with an up-to-date log become leader, so a new leader never needs to fetch missing entries. Multi-Paxos allows any node to lead and catches it up during phase 1. Raft’s advantage is a complete, precise specification, and that is why it became the default in new systems: etcd, Consul, CockroachDB, TiKV, and Kafka’s KRaft. Spanner and Chubby run Paxos. ZooKeeper uses its own closely related protocol, Zab.

• Pre-vote and CheckQuorum. A node that was partitioned away keeps incrementing its term, and when it rejoins it disrupts a healthy leader. Pre-vote has a candidate first check that it could win before bumping the term. CheckQuorum has a leader step down if it can’t reach a majority.
• Throughput. Batch many commands per AppendEntries, pipeline without waiting for each acknowledgement, and fsync in groups. Disk sync latency, not network latency, often sets the ceiling.
• Test like an adversary. Consensus bugs live in rare interleavings. Deterministic simulation, fault injection (Jepsen) and model checking (TLA+) find them before production does.

Raft’s core in code

The voting rule, the AppendEntries consistency check with conflict truncation, and the commit rule with its current-term restriction. Most of Raft’s safety lives in these three functions.

// The two RPC handlers at the heart of Raft, plus the leader's commit rule.
type Entry = { term: number; command: string };
type Node = {
  id: string; currentTerm: number; votedFor: string | null;
  log: Entry[]; commitIndex: number; role: "follower" | "candidate" | "leader";
};
const lastTerm = (n: Node) => n.log.at(-1)?.term ?? 0;

// RequestVote: grant at most one vote per term, and only to a candidate whose log is at least as up to date.
export function handleRequestVote(n: Node, req: { term: number; candidateId: string; lastLogIndex: number; lastLogTerm: number }) {
  if (req.term < n.currentTerm) return { term: n.currentTerm, voteGranted: false };
  if (req.term > n.currentTerm) { n.currentTerm = req.term; n.votedFor = null; n.role = "follower"; }
  const upToDate =
    req.lastLogTerm > lastTerm(n) || (req.lastLogTerm === lastTerm(n) && req.lastLogIndex >= n.log.length);
  const grant = (n.votedFor === null || n.votedFor === req.candidateId) && upToDate;
  if (grant) n.votedFor = req.candidateId; // persisted to disk before replying, in a real system
  return { term: n.currentTerm, voteGranted: grant };
}

// AppendEntries: the consistency check on (prevLogIndex, prevLogTerm) is what gives Log Matching.
export function handleAppendEntries(n: Node, req: {
  term: number; prevLogIndex: number; prevLogTerm: number; entries: Entry[]; leaderCommit: number;
}) {
  if (req.term < n.currentTerm) return { term: n.currentTerm, success: false }; // a stale leader
  n.currentTerm = req.term;
  n.role = "follower"; // any valid leader for this term makes us a follower

  const prev = req.prevLogIndex === 0 ? null : n.log[req.prevLogIndex - 1];
  if (req.prevLogIndex > 0 && (!prev || prev.term !== req.prevLogTerm)) return { term: n.currentTerm, success: false };

  // Delete a conflicting suffix, then append. Entries before the conflict are already identical.
  req.entries.forEach((e, k) => {
    const i = req.prevLogIndex + k;
    if (n.log[i] && n.log[i].term !== e.term) n.log.length = i;
    if (!n.log[i]) n.log.push(e);
  });
  n.commitIndex = Math.max(n.commitIndex, Math.min(req.leaderCommit, req.prevLogIndex + req.entries.length));
  return { term: n.currentTerm, success: true };
}

// Leader: an index is committed once a majority stores it AND it is from the current term.
// (Counting replicas of an older-term entry is unsafe; see Figure 8 of the Raft paper.)
export function advanceCommit(leader: Node, matchIndex: number[], clusterSize: number) {
  for (let i = leader.log.length; i > leader.commitIndex; i--) {
    const replicas = 1 + matchIndex.filter((m) => m >= i).length;
    if (replicas * 2 > clusterSize && leader.log[i - 1].term === leader.currentTerm) {
      leader.commitIndex = i;
      break;
    }
  }
}

References

1. Fischer, M. J., Lynch, N. A. & Paterson, M. S. (1985). Impossibility of Distributed Consensus with One Faulty Process. JACM. doi:10.1145/3149.214121
2. Dwork, C., Lynch, N. & Stockmeyer, L. (1988). Consensus in the Presence of Partial Synchrony. JACM. doi:10.1145/42282.42283
3. Lamport, L. (1998). The Part-Time Parliament. ACM TOCS. doi:10.1145/279227.279229
4. Lamport, L. (2001). Paxos Made Simple. ACM SIGACT News. lamport.azurewebsites.net
5. Chandra, T. D., Griesemer, R. & Redstone, J. (2007). Paxos Made Live: An Engineering Perspective. PODC. doi:10.1145/1281100.1281103
6. Ongaro, D. & Ousterhout, J. (2014). In Search of an Understandable Consensus Algorithm. USENIX ATC. usenix.org
7. Ongaro, D. (2014). Consensus: Bridging Theory and Practice. PhD thesis, Stanford University. web.stanford.edu
8. Herlihy, M. P. & Wing, J. M. (1990). Linearizability: A Correctness Condition for Concurrent Objects. ACM TOPLAS. doi:10.1145/78969.78972
9. Howard, H. & Mortier, R. (2020). Paxos vs Raft: Have we reached consensus on distributed consensus? PaPoC. arXiv:2004.05074
10. Burrows, M. (2006). The Chubby lock service for loosely-coupled distributed systems. OSDI. usenix.org
11. Corbett, J. C. et al. (2012). Spanner: Google’s Globally-Distributed Database. OSDI. usenix.org