The primitive underneath every strongly-consistent distributed system. Intermediate M.44 said "use quorum"; Expert M.47 shows you the two-phase message flow that makes quorum work, the proposal-number invariant that prevents split decisions, and the FLP impossibility result that means you can never fully escape the fundamental tradeoff. Paxos (Lamport 1989/1998), Multi-Paxos (Lamport 2001), and Raft (Ongaro & Ousterhout 2014) — three algorithms, one theoretical foundation, and the specific reason Kafka, etcd, Consul, CockroachDB, and every strongly-consistent K-V store agree on writes across replicas.
Every senior distributed-systems engineer has learned to reach for consensus without knowing exactly what happens inside it. "Use etcd for that" — etcd runs Raft. "We'll use ZooKeeper" — ZooKeeper runs Zab, a Paxos variant. "Postgres synchronous replication" — implicit two-phase commit with the primary as coordinator. "Spanner distributed transactions" — Paxos per replica group with TrueTime for ordering. "Kafka controller elections" — KRaft, a Raft implementation. The specific pattern is that mature distributed systems always defer to a small set of well-understood consensus algorithms rather than inventing their own. The Expert-tier question is: what do those algorithms actually do, why do they work, and where do they break? This is where "I use etcd" becomes "I understand what happens when the leader loses network connectivity to the majority for 30 seconds." Intermediate taught the reach; Expert teaches the mechanism.
The specific difficulty of consensus is that the problem seems trivial and is provably hard. "Get five nodes to agree on a value" — easy, right? Broadcast the proposed value, wait for acknowledgments, done. But what if two nodes propose different values simultaneously? What if a node's acknowledgment gets lost in the network? What if a node crashes after acknowledging but before writing to disk? What if the network partitions and the two halves each elect their own leader? Every one of these scenarios is a real failure mode that a naive protocol handles incorrectly — producing split-brain, data loss, or hung systems. The FLP impossibility result (Fischer, Lynch, Paterson 1985) formally proved that no deterministic consensus algorithm can guarantee both safety and liveness in an asynchronous network with even one failure. This isn't a limitation of specific algorithms — it's a limitation of consensus itself. Real algorithms navigate this by giving up liveness during network partitions (safety always, liveness usually) or by using probabilistic guarantees. Understanding what your algorithm gives up when is the Expert-tier skill this module builds.
Each earlier attempt has a specific failure mode that consensus was designed to prevent — 2PC blocks on coordinator crash, lock-based election allows split-brain, quorum reads/writes aren't linearizable. Real consensus algorithms (Paxos, Raft) solve all three by combining quorum-based decisions (majority makes progress) with proposal ordering (proposal numbers or terms prevent conflicting values from being chosen) and persistent state (acceptors remember their promises across crashes). The two-phase structure is what makes this work: proposers must discover what values might have been accepted before proposing new ones. This is why every mature distributed system converges on Paxos-family algorithms for its critical decisions, and this is what §02 and §03 walk through in mechanical detail.
The historical arc of consensus is a specific case where academic theory preceded industrial need by decades, then took another decade to make the theory teachable. 1985: FLP impossibility (Fischer, Lynch, Paterson) — proved that no deterministic algorithm can achieve both safety and liveness under fully asynchronous conditions with even one crash. This result shaped every subsequent consensus algorithm. 1989: Lamport writes the Paxos paper — "The Part-Time Parliament," written in a whimsical style with a fictional Greek island parliament. The style obscured the technical content; the paper was rejected initially and languished until 1998 when it was finally published. 2001: Lamport writes "Paxos Made Simple" — a plain-English version stripped of the parliamentary metaphor. This became the standard reference. 2006: Google publishes the Chubby paper — Paxos in production at scale, providing distributed lock service across all of Google. Same year, ZooKeeper begins at Yahoo with the Zab protocol (a Paxos variant). 2013: etcd, Consul launch using Raft. 2014: Ongaro and Ousterhout publish the Raft paper ("In Search of an Understandable Consensus Algorithm") — reformulating consensus as leader election + log replication with explicit design-for-teachability. Raft eclipses Paxos for new implementations because engineers can understand it. 2015+: Consensus becomes commodity — every distributed database, service mesh, and streaming platform embeds a consensus implementation. Modern production consensus is Multi-Paxos (Google, Spanner) or Raft (everyone else); Basic Paxos is a teaching tool. Understanding the arc explains why Raft won industrial mindshare despite being younger — teachability matters when the algorithm gets embedded in tools that thousands of engineers debug and extend.
Basic Paxos solves one specific problem: get N processes to agree on a single value, even if some processes crash or messages get lost. The algorithm has three roles (Proposers, Acceptors, Learners) and two phases (Prepare/Promise, Accept/Accepted). In practice, one process typically plays all three roles, but the roles are logically distinct because they enforce different invariants. Understanding Basic Paxos in mechanical detail — what messages get sent, what state each acceptor maintains, what invariants make it safe — is the specific competence that separates "I use etcd" from "I can reason about consensus failure modes." This section walks through the algorithm step by step.
Every proposal has a unique, monotonically increasing number. In practice: pair (round_number, proposer_id) — proposer_id breaks ties. The proposal number is what enforces ordering: higher-numbered proposals win over lower-numbered ones. Reset the proposal number scheme wrong and you break safety.
Every acceptor persists three things to disk before responding: the highest proposal number promised, the highest proposal number accepted, and the value accepted for that proposal number. Persistence must survive crashes — if an acceptor forgets what it accepted, safety breaks. Real implementations use fsync before responding.
Every phase requires responses from a strict majority of acceptors (⌈N/2⌉ + 1). Majority-of-majority guarantees overlap between any two decisions, which is what preserves safety across time. N=5 → quorum = 3. N=3 → quorum = 2. Even N (like N=4) is a waste — you tolerate the same failures as N=3 but need more messages.
If a value v is chosen at proposal n, any subsequent proposal (n', v') with n'>n must have v'=v. This is proven by contradiction: if v'≠v were chosen, both chose-majorities must overlap on at least one acceptor, and that acceptor would have told the second proposer about v — the proposer would have adopted v as its value. Lamport's original proof.
Two proposers alternately preparing with higher numbers can prevent each other from ever completing Phase 2 — the classic livelock. Fixed by electing a stable leader (Multi-Paxos) or introducing randomized backoff. Note that this is a liveness failure, not a safety failure — no wrong decision is made, just no decision at all. FLP predicts this.
In production, agreement is repeated (for a log of decisions, not one value). Multi-Paxos elects a stable leader that skips Phase 1 for subsequent proposals — one-round-trip decisions during stable-leader periods. If the leader fails, a new one is elected via full Paxos. This gives the throughput of a single-leader system with the safety of Paxos.
The proposal-number invariant (i) is the specific mechanism that makes Paxos safe across time. Every proposal is tagged with a globally unique number (in practice, a pair (round, proposer_id)); acceptors track the highest number they've promised and the highest number they've accepted. When a new proposer arrives with number n, acceptors reject if they've already promised n' > n. This ordering prevents an old proposer from resurrecting stale proposals after network partitions heal. It's the same idea as a version number in optimistic concurrency control, but applied to a distributed protocol. Getting proposal number generation wrong (non-unique numbers, non-monotonic numbers, resetting after crash) is one of the specific ways real implementations break Paxos.
The persistent state (ii) is where Paxos meets reality — every acceptor must fsync three values to disk before responding to a Prepare or Accept, and these values must survive crashes. Skip the fsync (for performance) and you can violate safety: a crashed acceptor that "forgets" its promise can accept a lower-numbered proposal after restart, potentially causing a stale value to be chosen. This is the source of most real-world consensus bugs — not the algorithm itself, but the implementation's handling of durability. Chubby, ZooKeeper, and etcd all have detailed engineering around durable state; failure to preserve it is what makes many "homegrown" consensus implementations subtly wrong. Anti-pattern §05.i is rolling your own consensus and getting persistence subtly wrong.
The Multi-Paxos optimization (vi) is what makes Paxos usable in production. Basic Paxos does two round-trips per decision (Prepare/Promise + Accept/Accepted) — that's 4 network hops for every consensus decision. Unusable for high throughput. Multi-Paxos observes that if the same proposer keeps winning (stable leader), the Prepare phase's result is the same each round, so it can be skipped. Subsequent decisions require only one round-trip (Accept/Accepted) — 2 network hops. This is the pattern Chubby, Spanner, and every production Paxos implementation uses. Basic Paxos is a teaching tool; Multi-Paxos is what actually runs. Same safety properties, dramatically better throughput. Understanding this distinction is table stakes for reasoning about production consensus performance.
Raft (Ongaro & Ousterhout, 2014) is Paxos reformulated for understandability. Same underlying problem (get N processes to agree on a sequence of values), same fundamental technique (majority quorum with ordering invariants), but organized as three separately-reasoned concerns — leader election, log replication, and safety — instead of Paxos's single-blob protocol. The pedagogical redesign was so effective that Raft became the industrial default within 3 years of publication: etcd, Consul, TiKV, CockroachDB, InfluxDB Enterprise, MongoDB (from 3.2), and Kafka (via KRaft) all use Raft. Understanding both Paxos and Raft is Expert-tier competence; understanding why Raft won industrial mindshare despite being younger is meta-competence about how systems engineering evolves.
Time in Raft is divided into arbitrary-length terms — a monotonically increasing integer. Each term has at most one leader (or none, if election fails). Every message carries the sender's current term; receivers reject messages with older terms and update their own term when they see a higher one. Terms serve the same role as Paxos's proposal numbers — ordering across time.
Followers become candidates after an election timeout (150-300ms random, to avoid split votes). Candidates request votes from all others; each node votes at most once per term. First candidate with majority votes wins. If split votes prevent majority, timeout again with a new random interval. Randomized timeouts are what break the livelock — real Paxos needs external mechanisms; Raft has it built in.
Leader receives client request, appends to its log, sends AppendEntries to followers. Followers append and respond. Once a majority acknowledges, the entry is committed and can be applied to the state machine. Log entries are indexed and identified by (term, index) — this pair uniquely identifies any entry across the cluster's history.
If two logs have an entry with the same index and term, all preceding entries are also identical. This is enforced by AppendEntries's consistency check: the leader sends the previous entry's (term, index) with each request; followers reject if their log doesn't match. On mismatch, the leader backs up and retries with earlier entries. This is Raft's specific safety mechanism.
A candidate cannot win an election unless its log contains all committed entries from previous terms. This is enforced during voting: a follower rejects a vote request from a candidate whose log is less "up to date" than its own. Prevents an out-of-date candidate from becoming leader and overwriting committed history. Critical for safety across term transitions.
Logs grow forever unless truncated. Raft supports snapshots — the state machine state at some log index — plus log truncation up to the snapshot. New followers receive snapshots via InstallSnapshot RPC rather than replaying the entire log. Production Raft implementations spend significant engineering on snapshot semantics; incorrect snapshotting is a common source of subtle bugs.
The separation of concerns (leader election, log replication, safety) is Raft's specific pedagogical innovation. In Paxos, these concerns are entangled — the same algorithm runs for both electing a leader (Multi-Paxos's Phase 1) and committing values (Phase 2), with the same messages and state. Understanding the algorithm requires understanding both simultaneously. Raft separates them into three orthogonal sub-protocols: elect a leader when necessary, replicate the log while the leader is stable, maintain safety across leader transitions via voting restrictions. Each sub-protocol can be reasoned about independently, and the algorithm as a whole becomes tractable in a single reading. This is why the Raft paper opens with "In Search of an Understandable Consensus Algorithm" — the primary contribution is pedagogical, not theoretical. Same problem, same fundamental technique, but organized for human comprehension.
The randomized election timeouts (ii) are the specific mechanism that gives Raft its liveness guarantee under stable-network conditions. Paxos has a well-known livelock: two proposers with alternating higher numbers can prevent each other from completing Phase 2 forever. Fixing this in Paxos requires external mechanisms (leader election as a separate protocol, or randomized backoff). Raft bakes randomization into the election protocol itself: election timeouts are random within a range (150-300ms typical), so split votes are unlikely to repeat and elections eventually converge. This is a specific example of how Raft's design decisions reduce operational surface — you don't need external libraries or configurations to prevent livelock; the algorithm handles it internally. Production systems value this kind of "batteries included" property.
The industrial dominance of Raft is worth understanding as a specific case study in how systems engineering evolves. Paxos is older (1989 vs 2014), more foundational (Multi-Paxos and Raft are both descendants), and has decades of production track record (Chubby, Spanner, ZooKeeper). Raft is younger, has less battle-tested code, and had to win against a well-established incumbent. It won because the barrier to correctly implementing consensus is not the algorithm's theoretical properties but the engineering effort to build correct implementations, and that engineering effort scales with algorithm complexity. Raft's separated concerns mean a new engineer can understand and debug the code in weeks rather than months. When your service mesh reaches an anomaly, having a Raft implementation you can reason about is worth more than having a Multi-Paxos implementation you have to trust. This is what industrial-software-engineering means in practice — the algorithm that people can actually build and maintain wins over the algorithm that's theoretically ideal but operationally opaque.
Below: each of the three canonical consensus algorithms (Basic Paxos · Multi-Paxos · Raft) evaluated against three failure scenarios (Normal operation · Leader failure · Network partition). Watch how each algorithm handles the specific engineering tests that distinguish theoretical elegance from production usability. The 9 cells illustrate why algorithm choice is a decision about your operational model, not about theoretical purity.
The failure modes of consensus implementations are the reason "we implemented Raft in-house" is one of the most dangerous sentences in distributed systems engineering. Consensus algorithms are simple to state and vicious to get right — the subtle bugs don't show up in normal operation and become catastrophic under specific failure sequences that engineers didn't anticipate. Even seasoned distributed-systems teams get consensus implementations subtly wrong; the difference between production-ready and buggy is measured in months of formal verification, testing, and fuzzing.
Rolling your own consensus is the specific engineering mistake that has produced more real-world data-loss incidents than any other category. The intuition that "leader election with heartbeats is simple" is precisely wrong — the simplicity of the happy path hides the complexity of the failure modes. Split-brain during partitions, stale leaders after network hiccups, torn writes when the leader crashes mid-transaction, clock-skew-induced inconsistencies — every one of these is a real bug from real deployments. The fix: use etcd, Consul, or ZooKeeper. Even if the operational surface seems heavy for your use case, it's cheaper than reproducing 15 years of consensus implementation engineering. Companies that write their own only survive if they employ multiple full-time consensus specialists (Google, Amazon, Meta) — and even they use production-hardened implementations for most cases. The general principle: consensus is a solved problem; the solution is "use a battle-tested implementation," not "implement your own".
Consensus is expensive — every decision requires a majority quorum, which means every write is at least one round-trip to multiple nodes plus disk fsync. Raft-based systems typically handle 10K-50K writes/sec per Raft group, which is far below what a single-node database achieves. Putting consensus in the hot data path — using etcd or Consul as your primary database — is a specific antipattern that hits scale walls fast. The fix: consensus is for control-plane decisions (leader elections, configuration changes, small-scale coordination), not for data-plane traffic. Actual data goes through databases that use consensus internally for replication but expose faster interfaces to clients. CockroachDB uses per-range Raft but processes millions of QPS by having many independent Raft groups. The general principle: consensus is for coordination, not for throughput. Putting it in the data path is the fastest way to hit its throughput ceiling.
The number of nodes in a consensus cluster should almost always be odd (3, 5, 7). Even numbers give you the same fault tolerance as N-1 with more overhead: 4 nodes tolerates 1 failure (same as 3) but requires 3 acknowledgments per decision (vs 2 for a 3-node cluster). Worse, even-numbered clusters can split evenly during partitions, leaving both sides without majority and both sides unavailable for writes. The fix: always deploy 3 or 5 (or 7 for large-scale critical systems). If you need to add a 4th node temporarily during operations, do it as a transitional state with an explicit migration plan. Never leave a consensus cluster at an even count. The general principle: odd counts are strictly better than even counts for consensus; there is no reason to deploy 4 or 6 in production. Anti-pattern §05.iii is the most easily-avoided consensus bug.
The FLP impossibility result (Fischer, Lynch, Paterson 1985) proves that no deterministic consensus algorithm can guarantee both safety and liveness under fully asynchronous conditions with even one failure. Production Paxos and Raft always give up liveness — they refuse to make progress during network partitions rather than risk safety violations. This is a feature, not a bug. But it means a consensus-based system CANNOT be both strongly consistent and always available; the CAP theorem is a direct corollary. The fix: (a) understand that "we use Raft" means "we accept unavailability during partitions"; (b) design your SLA around this — 99.99% availability is compatible with brief consensus unavailability if you have short partition durations; (c) for workloads that demand higher availability, consider whether you actually need consensus or whether eventual consistency would suffice (M.44's leaderless Dynamo-style is the alternative). The general principle: consensus buys you consistency at the cost of availability during partitions; you cannot design around FLP.
Consensus algorithms assume that persisted state survives crashes. If an acceptor promises not to accept lower-numbered proposals or acknowledges a log entry, and then that state is lost on crash (because fsync was skipped for performance), the algorithm's safety guarantees break. A restarted node can violate its previous promises. Not visible in single-node crash tests (single crashes recover from other replicas); catastrophic in correlated-failure scenarios (rack loss, power event, kernel panic across the fleet). The fix: (a) fsync every state change before responding — never lie to peers about durability; (b) validate durability under correlated failures, not just random single-node crashes; (c) if performance requires async commits, understand the specific safety weakening and document it explicitly. The general principle: consensus is a durability-first algorithm; every performance optimization that weakens durability weakens safety proportionally. This is where academic-vs-industrial implementations differ most.
The composite pattern across all five is that consensus algorithms are engineering artifacts, not just theoretical constructs — the algorithm proofs assume certain behaviors (unique proposal numbers, persistent state, correctly-implemented majority quorums) that the implementation must guarantee. Production consensus deployments spend significant engineering on formal verification (TLA+ specifications for etcd's Raft implementation), correlated-failure testing (Jepsen tests for CockroachDB, MongoDB, etcd), and chaos engineering (Netflix's Chaos Monkey extended for stateful services). Skipping any of these produces subtly broken systems that pass unit tests and fail catastrophically under production load. This is the specific engineering rigor that separates production-grade consensus implementations from prototypes.
The terms that show up in every "we need coordination" architecture review, every "why did the cluster stop making progress?" postmortem, every "which consensus algorithm?" design doc.
Test the algorithm. Click an answer; explanation drops in instantly.
Perfect. Paxos, Multi-Paxos, Raft, majority quorums, FLP impossibility, safety invariants — the primitive that every strongly-consistent distributed system runs underneath. Next up: M.48, Byzantine fault tolerance and adversarial consensus.
The composite understanding that turns "we use etcd" into "we understand what happens when etcd's leader loses network connectivity."
Basic Paxos is Prepare/Promise + Accept/Accepted with majority quorum on both phases and a proposal-number invariant that orders proposals across time. Multi-Paxos elects a stable leader that skips Phase 1 for throughput. Raft reformulates the same fundamental technique as leader election + log replication + safety, organized for teachability. Same problem, three organizations; all provide safety always, liveness under partial synchrony.
Fischer, Lynch, Paterson 1985 proved that no deterministic consensus algorithm can guarantee both safety and liveness under async networks with one failure. Production consensus algorithms always give up liveness — refusing to make progress during partitions rather than risking safety violations. This is why "we use Raft" means "we accept brief unavailability during network partitions." CAP is a direct corollary.
Consensus is a solved problem; implementing consensus correctly is not. Homegrown consensus is the leading source of split-brain and data-loss incidents in distributed systems. Use etcd, Consul, or ZooKeeper. Reserve consensus for control-plane decisions (leader election, config changes) not data-path traffic. Deploy odd-numbered clusters. Fsync everything. The theoretical algorithm is the easy part; the implementation is decades of engineering.