Consensus Protocols (Raft and Paxos)

Consensus lets a cluster of machines agree on a single, ordered sequence of values even when some of them crash or messages are lost. It is the foundation under replicated state machines, leader election, and strongly-consistent stores. Raft and Paxos solve the same problem; Raft optimizes for understandability.

The canonical use is the replicated log + state machine: every node applies the same commands in the same order, so all replicas reach the same state. If the log is consistent across nodes, the derived state is consistent. Consensus is the mechanism that keeps that log identical despite failures, and it holds as long as a majority (quorum) of nodes is alive. A 5-node cluster tolerates 2 failures; a 3-node cluster tolerates 1. Source: Ongaro & Ousterhout, Raft, USENIX ATC 2014

Raft

Raft decomposes consensus into three subproblems and keeps a strong leader to make it teachable. Source: Ongaro & Ousterhout, Raft, 2014

• Leader election — time is divided into terms. A follower that hears no heartbeat becomes a candidate, increments the term, and requests votes; a candidate with a majority becomes leader. Randomized election timeouts prevent split votes.
• Log replication — clients talk only to the leader. The leader appends the command, replicates it via AppendEntries RPCs, and commits once a majority has stored it; only then does it apply and reply. Followers that diverge are forced to match the leader's log.
• Safety — the Log Matching and Leader Completeness properties guarantee a committed entry is never lost and never overwritten: a node only votes for a candidate whose log is at least as up to date as its own.

Paxos

Paxos (single-decree) reaches agreement on one value through proposers, acceptors, and learners over two phases: Prepare/Promise (a proposer claims a proposal number and learns any already-accepted value) and Accept/Accepted (it asks acceptors to accept its value). A value is chosen once a majority accepts it. Multi-Paxos amortizes the cost by electing a stable leader so steady-state writes skip phase 1, converging on the same shape Raft makes explicit. Paxos is provably correct but notoriously hard to implement, which is precisely the gap Raft set out to close. Source: Lamport, Paxos Made Simple, 2001

Raft vs Paxos

Design implications

• Latency = one round trip to a quorum per commit; co-locate or use a leader lease to avoid extra hops.
• Reads are not free: a linearizable read needs a leader lease or a quorum read, or you risk reading stale data from a deposed leader.
• Membership changes require care (Raft's joint consensus) so you never have two disjoint majorities.
• It is not Byzantine — Raft/Paxos assume crash-stop, not malicious nodes. Adversarial settings need BFT protocols.

This is the agreement layer beneath Replication and Consistency Models; the committed log it produces is the same append-only abstraction exploited by Event Sourcing and CQRS and Log-Based Streaming Architecture, and quorum commit is what makes Idempotency and Exactly-Once Processing tractable in a cluster.

Architecture Position

---

Timeline

• 2026-07-01 | Architecture category refresh added this page to the Distributed systems primitives family, linked it to Architecture System Map, and kept it standalone because it owns this boundary: Cluster agreement over ordered values despite failures. Source: User request, 2026-07-01

• 2026-06-02 | Page created. Captured replicated-log/state-machine framing, quorum fault tolerance, Raft's three subproblems, single-decree and Multi-Paxos, the comparison table, and read/latency/membership implications. Source: Ongaro & Ousterhout, Raft, USENIX ATC 2014; Lamport, Paxos Made Simple, 2001