How Do Paxos and Raft Achieve Consensus Despite Crashes?

Paxos and Raft are distributed consensus algorithms that enable a cluster of classical computers to agree on a shared sequence of operations even when some nodes crash or messages are delayed. Both algorithms implement a replicated state machine, where every non-faulty node starts in the same initial state and executes the same commands in the exact same order. By relying on majority quorums, monotonically increasing term or proposal numbers, and strict commit rules, Paxos and Raft guarantee safety at all times and make progress whenever a majority of nodes are reachable.

Replicated State Machines and Crash Faults

In a replicated state machine, a service is modeled as a deterministic state machine replicated across \(N\) nodes. If all replicas begin in the same state and apply the same log of commands in the same order, they will produce identical outputs and reach identical states.

Both Paxos and Raft operate under the crash-stop or crash-recovery fault model, where nodes may halt unexpectedly or restart with their persistent storage intact, and network messages may be delayed, reordered, or lost. Neither algorithm defends against Byzantine (malicious or arbitrary) faults. To tolerate up to \(f\) crashed nodes, a cluster requires at least \(N = 2f + 1\) nodes, ensuring that any majority quorum of size \(Q = \lfloor N/2 \rfloor + 1\) contains at least one node from every other majority quorum.

Quorum Intersection and Safety

The mathematical foundation of both algorithms is quorum intersection. Because any two majorities \(Q_1\) and \(Q_2\) in a cluster of \(N\) nodes satisfy:

\[|Q_1 \cap Q_2| \ge 1\]

there is always at least one node in common between the quorum that decided a value and any subsequent quorum that attempts to read or propose a new value. This overlap prevents split-brain scenarios where two different subsets of the cluster independently commit conflicting commands.

How Paxos Achieves Agreement

Single-decree Paxos (Synod) reaches agreement on a single value through a two-phase protocol involving proposers, acceptors, and learners, using unique, monotonically increasing proposal numbers \(n\):

  1. Phase 1a (Prepare): A proposer selects a proposal number \(n\) and sends a Prepare(n) request to a majority of acceptors.
  2. Phase 1b (Promise): If \(n\) is greater than any proposal number an acceptor has previously seen, the acceptor promises not to accept any future proposals with numbers less than \(n\). It replies with a Promise(n) containing the highest-numbered proposal \((n_a, v_a)\) it has already accepted, if any.
  3. Phase 2a (Accept): Once the proposer receives promises from a majority, it must choose a value. If any acceptor returned an already-accepted value, the proposer must select the value \(v_a\) associated with the highest \(n_a\); otherwise, it may propose its own value. It then sends Accept(n, v) to the acceptors.
  4. Phase 2b (Accepted): An acceptor accepts \((n, v)\) unless it has already promised a higher proposal number \(n' > n\). When a majority of acceptors accept \((n, v)\), the value is chosen.

To build a replicated log of commands, systems use Multi-Paxos, which runs a sequence of Paxos instances—one for each log index. By electing a stable leader that skips Phase 1 for subsequent log entries, Multi-Paxos reduces normal-case message overhead to a single round trip.

How Raft Achieves Agreement

Raft was designed to be more understandable than Paxos by decomposing consensus into three explicit subproblems: leader election, log replication, and safety.

  • Leader Election: Time is divided into numbered terms \(t\). If a follower does not receive a heartbeat from the leader within an election timeout, it increments its current term, transitions to a candidate, votes for itself, and sends RequestVote RPCs to other nodes. A node grants its vote at most once per term and only if the candidate's log is at least as up-to-date as its own. A candidate that receives votes from a majority becomes the leader for term \(t\).
  • Log Replication: The leader accepts client commands, appends them to its local log with the current term, and sends AppendEntries RPCs to followers. Followers append the entries if their preceding log entry matches the leader's term and index. Once a majority of nodes have written an entry to their logs, the leader commits the entry and applies it to its state machine.
  • Safety: Raft restricts leadership to nodes that already possess all committed entries. Furthermore, a leader only commits entries from its own current term by counting replicas; entries from earlier terms are committed indirectly when a newer entry from the current term is committed.

Comparing Paxos and Raft

While both algorithms provide the same safety and liveness guarantees under asynchronous networks with crash faults, they differ in structure. Paxos allows any node to propose values at any time and permits out-of-order log slots to be filled independently, which can require extra coordination to resolve gaps. Raft enforces a strong leader model where log entries flow strictly from the leader to followers in sequential order, trading a small amount of flexibility for a simpler, more prescriptive implementation.