Part 7 · Failure

Consensus, Coordination, and Verification

Lesson 16 showed that linearizability — making a distributed register behave as if there were a single copy — is exactly what you need for a uniqueness constraint, a lock, or a leader-election flag, and that it is expensive because it demands coordination. But it left the central question open: how do several unreliable machines actually agree, and agree irrevocably, when any of them can crash mid-decision and the network can lose or delay any message? That mechanism is consensus. This lesson is its home. We will show that consensus, total order broadcast, and a linearizable log are three faces of the same object; why a simple two-phase commit is not fault-tolerant consensus; why a majority is the magic number; what the FLP result says you can never have; and why the practical advice is to need consensus as rarely, and at as small a scope, as you can. Then, because these protocols are too subtle to trust by reading the code, we close with how you actually verify a distributed system — formal specification (TLA+), deterministic simulation testing, and fault injection. This lesson closes Part 7 · Failure and hands to Part 8 · Derived history.

DDIA source

Arc drawn from Martin Kleppmann, Designing Data-Intensive Applications, Chapter 9 (Consistency and Consensus) — the atomic-commit / two-phase-commit section, the consensus and total-order-broadcast equivalence, the FLP result, and the membership/coordination-service material (ZooKeeper). Original synthesis; ML-infra framings are ours.

Linear position

Prerequisite: Lesson 16 (linearizability — the single-copy illusion and why some invariants demand it); lesson 15 (fencing tokens and leases — the protection an agreed-upon order gives you against a deposed leader); lesson 09 (the quorum / majority overlap argument, w + r > n); lesson 08 (the replicated log and failover).
New capability: Recognize when a problem reduces to consensus, size a consensus cluster (how many nodes to tolerate how many failures), explain why 2PC blocks while Raft-style consensus does not, and decide what tiny slice of your system should sit behind ZooKeeper / etcd while everything else stays coordination-free.

The plan

Seven moves. (1) State the consensus problem precisely — agree on one value, irrevocably, despite crashes — and list the jobs that secretly are consensus. (2) Atomic commit and two-phase commit (2PC): how it works, and the exact reason it blocks when the coordinator dies, which is why it is not fault-tolerant consensus. (3) Total order broadcast: deliver the same messages to every node in the same order, and the punchline that it is equivalent to consensus and the same object as a linearizable log. (4) Fault-tolerant consensus algorithms (Paxos / Raft / Zab / VR): the shape they share, with the worked majority arithmetic — 2f + 1 nodes tolerate f failures. (5) The FLP impossibility, intuitively: why you cannot have both safety and liveness in a fully asynchronous network, and how real systems escape with timeouts. (6) Coordination services (ZooKeeper / etcd) and the discipline: coordinate once, at the smallest scope, then let a single leader do linearizable work without per-operation consensus. (7) Verifying distributed systems — why you test them differently, through formal methods (TLA+), deterministic simulation testing, and fault injection (chaos).

1 · The problem: agree on one value, and never take it back

One sentence: consensus is getting several unreliable nodes to irrevocably agree on one value — when any of them may crash and any message may be lost or arbitrarily delayed. "Agree" is a strong word here. A correct consensus protocol must satisfy four properties:

→Uniform agreement. No two nodes decide differently. There is one decision, full stop.

→Integrity. A node decides at most once — the decision is irrevocable. You cannot un-elect a leader by changing your mind later.

→Validity. The value decided was actually proposed by some node — the protocol can't invent an answer out of thin air.

→Termination. Every node that does not crash eventually decides. This is the liveness property — and §5 shows it is the one you cannot guarantee for free.

The first three are safety properties ("nothing bad happens"); the fourth is liveness ("something good eventually happens"). Keep that split in mind — the whole drama of consensus is that safety is achievable always, liveness only with extra assumptions.

Why care? Because a surprising number of distributed jobs are consensus wearing a costume. Each of these reduces to "agree on one value, irrevocably":

Leader election. Among n nodes, agree on exactly one leader — so two nodes don't both think they're in charge (split brain). The decided value is "who is leader for this term."
Distributed locks / leases. Agree on who holds the lock right now. Lesson 15's fencing token is just the monotonically increasing number consensus stamps on each grant.
Uniqueness / atomic commit. Agree that a username is claimed, or that a multi-node transaction commits everywhere or aborts everywhere — never half.
Membership & configuration. Agree on the current set of live nodes, or which shard a key belongs to, so everyone routes the same way.

Lesson 16 ended exactly here: a uniqueness constraint needs a single decider because the two registrations are concurrent and causality alone can't break the tie. Consensus is the machine that breaks the tie and writes the answer down so hard that no later confusion can erase it.

2 · Atomic commit and two-phase commit — and why 2PC blocks

Start with the most familiar consensus-flavoured problem: atomic commit. A transaction touches several nodes (say a payment row on node A and an inventory row on node B). Atomicity (lesson 13) demands all-or-nothing across machines: either every participant commits, or every participant aborts. No participant may commit while another aborts, or you've sold an item you never charged for.

The classic protocol is two-phase commit (2PC). One node acts as the coordinator; the others are participants. It runs in two rounds:

phase 1 — PREPARE (voting) coordinator --"can you commit?"--> participant A -> "yes" (and durably promise) coordinator --"can you commit?"--> participant B -> "yes" (and durably promise) once a participant votes "yes" it has given up the right to abort on its own. phase 2 — COMMIT (decision) coordinator decides COMMIT (all voted yes) ----> A: commit B: commit or ABORT (any vote was no) -----> A: abort B: abort the coordinator's decision is the single point of agreement.

The subtle part is the promise, and it rests on two pieces of durable bookkeeping. When a participant votes "yes" it first writes its vote and all the transaction's changes to stable storage (so a crash-and-restart, lesson 15's crash-recovery model, can still honor the promise) and only then replies. It is now in the in-doubt state — also called prepared: it has surrendered the right to decide for itself, cannot abort, cannot commit, and must do whatever the coordinator says in phase 2. Symmetrically, the coordinator owns a commit log on its own stable storage: the instant it has collected every "yes," it writes a single commit record, and that durable write is the moment of decision — the transaction is now committed even before any participant has heard. (If the coordinator crashes after writing it, recovery reads the log and resends the COMMIT; if it crashes before, recovery aborts.) That one durable record is the single point of agreement that makes the commit atomic. And it is also the flaw.

Why 2PC is not fault-tolerant consensus — it blocks

Suppose the coordinator sends PREPARE, every participant votes "yes" and is now in-doubt, and then the coordinator crashes before sending the phase-2 decision (and, worst case, before its commit log is reachable — e.g. its disk is lost). Every participant is now stuck in the in-doubt state: it promised to commit-or-abort on command, holds the transaction's locks, but the only node that knows the decision is gone. It cannot unilaterally commit (maybe someone voted no) and cannot unilaterally abort (maybe everyone voted yes and other participants already committed) — either guess risks violating atomicity. So it blocks — holding locks, frozen — until the coordinator recovers and replays its commit log. The coordinator is a single point of failure with no quorum behind it. That is precisely why 2PC fails consensus's termination property: a single crash can stall the system indefinitely.

phase 1: all vote YES, all now IN-DOUBT, holding locks coordinator --X crashes before writing/sending the decision participants ? "commit or abort?? we promised — we cannot decide alone" -> BLOCKED, locks held, until the coordinator comes back

A word on 3PC (three-phase commit): it inserts a "pre-commit" round so participants can, in theory, time out and decide among themselves without the coordinator — making it non-blocking. But it assumes a synchronous network with bounded delays (lesson 15), and under a real network partition those timeouts fire wrongly and 3PC can still produce an inconsistent commit. So 3PC is not used in practice; real fault-tolerant consensus (next sections) instead replaces the lone coordinator with a majority that carries the decision forward even when the leader dies.

When 2PC spans different systems — say a relational database and a message broker, each from a different vendor — the standard that lets them play the participant role is XA (the X/Open XA interface), with an external transaction manager as coordinator. XA is exactly the heterogeneous, distributed-transaction form of the protocol above, and it inherits the same blocking flaw plus operational pain (orphaned in-doubt transactions holding locks when the transaction manager is down), which is why most modern designs avoid distributed transactions across services and reach for the outbox / idempotency pattern of lesson 14 instead.

So 2PC (and its cross-system form, XA) is genuinely useful for atomic commit across well-behaved nodes, but it is not the fault-tolerant agreement we're after. The fix is to make the "decision" survive the loss of any single node — which is what total order broadcast and majority-based consensus deliver.

3 · Total order broadcast: the same messages, in the same order, everywhere

Total order broadcast (also called atomic broadcast) is a messaging guarantee with two parts:

Reliable delivery. No messages are lost: if a message is delivered to one non-crashed node, it is delivered to all of them.
Totally ordered delivery. Messages are delivered to every node in the same order. If node 1 sees [m1, m2, m3], node 2 also sees exactly [m1, m2, m3] — never [m2, m1, m3].

Picture it as an append-only log that everyone agrees on, position by position:

total order broadcast == an agreed log everyone replays identically pos: 0 1 2 3 4 node A: [ m1 ] [ m2 ] [ m3 ] [ m4 ] [ ?? ] node B: [ m1 ] [ m2 ] [ m3 ] [ m4 ] [ ?? ] node C: [ m1 ] [ m2 ] [ m3 ] [ ?? ] [ ?? ] <- C is just behind; it will never see a DIFFERENT m3. deciding "what goes in slot 3" is one run of consensus. the order is fixed; nodes may lag, but never disagree on a filled slot.

Here is the equivalence that ties the whole lesson together: total order broadcast is equivalent to consensus — each is implementable from the other. The bridge is the sequence numbers of lesson 16: total-order broadcast is precisely the act of attaching an agreed, gap-free sequence number to every message so all nodes deliver in that order.

TOB from consensus: run one consensus instance PER log slot. slot 0: consensus( proposals ) -> decides m1 ; slot 1 -> decides m2 ; ... the decided value at slot i is "the i-th message"; everyone delivers in slot order. consensus from TOB: to decide ONE value, every proposer BROADCASTS its proposal. TOB delivers all proposals to everyone in the SAME order. rule: each node decides the value of the FIRST delivered proposal. same order at every node => same "first" => same single decision (uniform agreement).

The cheap single-leader sequence numbers from lesson 16 are the easiest way to build the broadcast: the leader's append position is the agreed sequence number — but only while one leader holds the pen. Consensus is exactly what lets a new leader pick up the numbering, gap-free, after the old one fails. So deciding the content of each log slot is one consensus instance (slot 3 is "m4" and can never become anything else), and running consensus once per slot rebuilds the broadcast. They are the same problem.

The same object as a linearizable log (lesson 16)

And total order broadcast is the same thing as the linearizable log from lesson 16. A linearizable register can be built on top of total order broadcast: to do a compare-and-set (the operation a uniqueness constraint or lock needs), append your intended operation to the totally-ordered log, then wait to read back the log and act on the first such operation to appear. Because every node replays the log in the identical order, every node agrees who got there first — that's linearizability. So: linearizability (16) → total order broadcast → consensus (17) are three names for one underlying capability. Lesson 16 told you what you get (single-copy semantics); this lesson shows the engine — an agreed, totally-ordered, durable log — that produces it. The ordered durable log itself is the very same structure introduced back in lesson 03 (the write-ahead log) and used for replication in lesson 08; consensus is how several nodes agree on its contents.

4 · Fault-tolerant consensus: leader, log, majority

The production algorithms — Paxos (and its practical Multi-Paxos), Raft (designed to be understandable), Zab (ZooKeeper's protocol), and Viewstamped Replication — differ in detail but share one shape. Learn the shape once:

1Elect a leader for a term. Nodes vote; a candidate that collects a majority of votes becomes leader for a numbered term (also called an epoch or ballot). The term number is monotonically increasing — it is the fencing token (lesson 15) that lets nodes ignore a stale, deposed leader.

2Replicate the log to a quorum. Clients send commands to the leader. The leader appends each command to its log and ships it to followers. This is just the replication log of lesson 08, now under an agreement protocol.

3Commit once a majority acks. An entry is committed — irrevocable — as soon as a majority of nodes (including the leader) have stored it durably. The leader then tells everyone the entry is committed and they apply it.

4New leaders inherit committed history. Election rules guarantee a new leader's log already contains every committed entry, so failover never loses an agreed decision. This is where consensus beats 2PC: the decision lives in a majority, not in one coordinator.

Everything rests on one word: majority. A majority quorum is more than half the nodes. Its magic is the same overlap argument you proved for leaderless reads in lesson 09: any two majorities of the same set must share at least one member. That shared node carries knowledge from the old leader's term into the new one — so a freshly elected leader is guaranteed to have seen any entry the previous majority committed. Two disjoint groups can never each commit a conflicting decision, because they can't both be a majority.

Worked numbers — why 2f + 1 tolerates f failures

To tolerate f node failures and still form a majority, you need n = 2f + 1 nodes. A majority is f + 1 of them (strictly more than half). Walk it:

n = 3 (f = 1). Majority = 2. If 1 node dies, 2 remain — still a majority, the cluster keeps committing. If 2 die, only 1 remains, which is not a majority of 3, so it correctly refuses to act (better to stall than to split-brain). So 3 nodes tolerate 1 failure.

n = 5 (f = 2). Majority = 3. Lose 2 nodes, 3 remain = a majority, still live. Lose 3 and the remaining 2 are a minority and stop. So 5 nodes tolerate 2 failures.

Why odd numbers? Going from 3 to 4 nodes does not buy more fault tolerance: a majority of 4 is 3, so 4 nodes still tolerate only 1 failure (lose 2 of 4 and you have 2, not a majority) — you added a node, a vote to wait for, and zero extra resilience. 5 is the next useful size. Hence consensus clusters are almost always 3 or 5. The cost of a larger cluster is real: every commit waits for a majority to ack, so 5 nodes means waiting for the 3rd-fastest on every write — more durable, slightly slower, never worth an even count.

Note the availability price you already met in lesson 09: if the cluster cannot reach a majority — say a network partition isolates the leader with a minority — it stops accepting writes rather than risk two decisions. Consensus chooses consistency (safety) over availability under partition. That is the deliberate trade.

5 · The FLP impossibility: you can't always have both safety and liveness

If majority consensus is so clean, why isn't the problem just "solved"? Because of a foundational result, named after Fischer, Lynch, and Paterson — the FLP impossibility:

FLP, in one sentence

In a fully asynchronous network — one with no bound on how long a message can take and no reliable clock — no deterministic consensus algorithm can guarantee both safety (never decide wrong) and liveness (always eventually decide) if even a single node may crash.

The intuition: in a fully asynchronous network you cannot distinguish a crashed node from a merely slow one — there is no timeout you're allowed to trust, because messages can legitimately take arbitrarily long. So the algorithm can always be forced into a state where it must either wait forever for a possibly-dead node (losing liveness) or proceed and risk that the node was alive and about to disagree (losing safety). You can't escape the dilemma with cleverness; it's a property of the model.

The escape in practice is to weaken the model. Real networks are not adversarially asynchronous — messages usually arrive within some rough bound. So real consensus systems:

keep safety unconditionally — they will never decide two different values, no matter how badly the network behaves (the majority-overlap argument needs no timing assumption);
use timeouts to recover liveness — if the leader is silent for a timeout, followers suspect it has died and elect a new one. The timeout might be wrong (the old leader was just slow), but the term-number fencing makes that harmless: the stale leader's later messages are ignored. Raft adds randomized election timeouts so two followers rarely call an election at the same instant and split the vote.

So FLP doesn't say consensus is impossible — it says you cannot have a timeout-free algorithm that is both always-safe and always-live. The engineering answer is: never sacrifice safety, and buy liveness with timeouts and randomization that work because real networks are usually well-behaved.

6 · Coordination services: ZooKeeper, etcd, and the discipline of needing them rarely

You almost never implement Paxos or Raft yourself. You rent it. ZooKeeper (running Zab) and etcd (running Raft) are off-the-shelf, battle-tested consensus systems — think of them as a small, highly-available, linearizable key-value store with a few extra primitives. Out of the box they give you the consensus-shaped jobs from §1:

Leader election

A set of nodes race to create one ephemeral key; whoever wins is leader. If the leader's session dies, the key vanishes and a new election runs. One safe leader, guaranteed.

Locks & leases

A linearizable compare-and-set grants a lock; the store hands out a monotonically increasing version number — your fencing token (lesson 15) to reject a stale holder's writes.

Configuration & metadata

Which schema version is live, which shard a key maps to, what the cluster's current settings are — small, critical state every node must agree on and read consistently.

Membership / failure detection

Ephemeral nodes + heartbeats track the live set; the service tells everyone the same agreed view of who is up, so routing doesn't split-brain.

The expensive-tool discipline — coordinate at the smallest scope

Every consensus operation costs a majority round trip and refuses to make progress during a partition. So treating it as a general database is a performance and availability disaster. The standard pattern: use consensus to elect ONE leader, then let that single leader do all the linearizable work without per-operation consensus. The leader holds a lease (renewed through the consensus store), and while it holds the lease it can serve and order operations locally and linearizably — fast, no quorum per write. Consensus runs only on the rare events: who is leader, and membership/config changes. The high-volume data plane never touches it. This is the same control-plane / data-plane split from the trade-off table below: a tiny amount of coordination protecting a large amount of coordination-free work.

ML-infra tie

A distributed training job needs exactly one coordinator — the rank-0 / chief worker, or the parameter-server master — to assign shards, drive checkpointing, and decide when an epoch is done. If two workers both believed they were chief (split brain after a network hiccup), they could write conflicting checkpoints or double-issue work. So the job does one consensus operation: elect the chief via an ephemeral key in etcd, with a fencing token so a paused-then-resumed old chief is ignored. After that, the chief coordinates thousands of steps per second with no per-step consensus. Likewise the cluster scheduler (Kubernetes) stores all its agreed state — what's scheduled where, the membership of the control plane — in etcd; the consensus box is the scheduler's source of truth, and everything fast happens off the consensus path.

7 · Verifying a distributed system: why you test it differently

Everything above is too subtle to trust by reading the code. The bugs that matter — a split brain, a lost commit, a deposed leader's write slipping through — appear only in rare interleavings of crashes, message reorderings, and pauses (§1, lesson 15) that a normal test suite never happens to hit. Ordinary unit and integration tests exercise the happy path and a few hand-picked failures; the dangerous schedules hide in the combinatorial space between them. So distributed systems are verified with three techniques aimed squarely at that space.

Formal methods (TLA+)

Write the protocol as a specification — the allowed states and transitions — plus the invariants it must never violate (uniform agreement, "at most one leader per term"). A model checker then exhaustively explores every reachable interleaving up to some bound and reports the shortest schedule that breaks an invariant. TLA+ is the standard; AWS used it to find subtle bugs in S3 and DynamoDB protocols before shipping. It verifies the design, not the code — but a wrong design is the most expensive bug to find late.

Deterministic simulation testing

Run the real code on a simulated network and clock where message delays, reorderings, partitions, and crashes are driven by a seeded random number generator. Because everything is deterministic, a failing run is captured by its seed and replays identically — no flaky "happens once a week" bug. FoundationDB built its whole engine this way, running years of simulated failure per night; TigerBeetle does the same. It tests the actual implementation, not just the model.

Fault injection (chaos)

Inject real faults into a real (often production-like) cluster — kill nodes, sever the network, freeze a process, skew clocks — and assert the system's invariants still hold. Jepsen is the famous tool for checking consistency claims under partition (it has falsified many vendors' linearizability claims); Chaos Monkey-style tools randomly kill instances in production. It catches what the model and simulator abstracted away: real OS, real disks, real timeouts.

The progression is design → implementation → deployment: TLA+ proves the protocol is sound, deterministic simulation proves the code implements it under adversarial schedules, and fault injection proves the deployed system survives real-world faults. None subsumes the others — a verified design can be miscoded, and correct code can be misconfigured. The point that unifies them is the §1 insight: because partial failure is nondeterministic and rare interleavings are where correctness dies, you cannot verify a distributed system by example. You must search the failure space deliberately, with a model checker, a seeded simulator, or an adversary breaking your cluster on purpose.

Trade-offs

Choice	Buys	Costs
2PC (atomic commit)	All participants commit or abort together across nodes	Blocks indefinitely if the lone coordinator dies — not fault-tolerant
Majority consensus (Raft/Paxos)	Irrevocable agreement that survives any minority failure; no split brain	Quorum round trip per decision; halts writes when no majority is reachable
Total order broadcast	An agreed, replayable log = linearizable state machine	Same as consensus — it is consensus per slot
Coordination service (ZooKeeper/etcd)	Rent leader election, locks, config, membership; don't build Paxos	Operational dependency; latency floor; a partition can stall the control plane
Elect-one-leader, then no per-op consensus	Linearizable work at local speed under a lease	Must handle lease expiry / fencing correctly or risk a deposed-leader write

Failure modes

Split brain. Two nodes both believe they're leader after a partition and both accept writes. Root cause: leadership not backed by a majority, or no fencing token to reject the stale one. Symptom: conflicting committed state, lost updates.
2PC coordinator crash. Participants stuck in the uncertain state hold locks forever. Symptom: a transaction hangs, unrelated work blocks on its locks, only a coordinator restart unsticks it.
Even-sized cluster. 4 or 6 nodes give the same fault tolerance as 3 or 5 while costing an extra vote per commit — and a 2/2 partition deadlocks with no majority either side.
Consensus on the data plane. Running a quorum write per user operation: every request pays a majority round trip and the whole service goes unavailable during any partition. Symptom: latency cliff and partition-correlated outages.
Liveness lost to bad timeouts. Election timeout too short → constant leader churn (no progress); too long → slow failover. FLP says you can't make this perfect; tune and randomize it.

Decision checklist

Does this problem actually reduce to consensus (one irrevocable decision: leader, lock, uniqueness, membership)? If not, keep it coordination-free.
If you need atomicity across nodes and fault tolerance, use a consensus-backed log, not bare 2PC.
Size the cluster odd: 3 to tolerate 1 failure, 5 to tolerate 2. Don't pick even counts.
Are you renting consensus (ZooKeeper/etcd) instead of hand-rolling Paxos? Almost always you should be.
Is leadership backed by a majority and protected by a fencing token (lesson 15) so a deposed leader's late writes are rejected?
Is consensus confined to the control plane — elect one leader, then serve linearizable work under a lease with no per-op quorum?
What happens during a partition? Confirm the minority side correctly stops rather than serving conflicting writes.

Checkpoint exercise

Try it

You're building the control plane for a distributed training fleet. (a) The fleet must have exactly one job coordinator at a time; describe, using a coordination service, how you elect it and how a fencing token stops a frozen-then-resumed old coordinator from corrupting a checkpoint — name the consensus property (§1) this enforces. (b) You're choosing the etcd cluster size and want to survive 2 simultaneous node failures while always able to commit; how many nodes, what is the majority, and why not one more? Show the arithmetic (§4). (c) A teammate proposes routing every gradient-sync message through the consensus log for "strong ordering." Explain why that is the wrong scope and what to do instead (§3, §6). (d) During a network partition the minority side of your etcd cluster goes read-only and rejects writes; explain which consensus property (§1) and which impossibility result (§5) justify that behaviour.

Where this points next

Part 7 · Failure — and with it the whole arc of keeping a single, mutable, consistent picture of state across machines — closes here. We covered replication (08–09), partitioning (11), transactions and isolation (13), the transaction and message boundary (14), the troubles of partial failure and clocks (15), and the consistency / consensus apparatus that buys you single-copy semantics when an invariant truly demands it (16–17) — and how to verify all of it. The recurring lesson is that strong coordination is expensive and should be applied surgically. Part 8 · Derived history turns that insight into an architecture: instead of coordinating every write, treat one dataset as the source of truth and derive everything else — indexes, aggregates, features, embeddings — by reprocessing it. Lesson 18, batch processing, starts there: bounded input in, deterministically recomputed output out, the all-to-all shuffle as the dominant cost, and the property that makes derived data safe — a broken view can simply be deleted and rebuilt from history, no consensus required. We trade coordination on the write path for recomputation on the read path.

Where is truth?

For a consensus-backed system, "truth" is the agreed log itself. System of record: the replicated, totally-ordered log held by the consensus group (ZooKeeper/etcd) — an entry is true only once a majority has stored it durably; the current leader's term number records who may write. Copies / derived views: follower replicas of the log, and the local state machines every node builds by replaying it — each a copy that may briefly lag but can never diverge on a committed slot. Freshness budget: a follower may trail by the replication delay, but a linearizable read must reach a majority (zero staleness); the leader's lease bounds how long a stale leader can believe it still leads. Owner: the elected leader for the current term owns appends; the majority owns commitment. Deletion path: the log is append-only, so "deletion" is a new committed entry (a tombstone or config change) plus periodic snapshot/compaction of superseded prefix — never an in-place erase. Reconciliation / repair: a rejoining or lagging node catches up by replaying the leader's committed log (or installing a snapshot); a deposed leader is fenced by its stale term number. Evidence it is correct: the majority-overlap argument proves no two conflicting values commit, and the verification techniques of §7 (TLA+, deterministic simulation, fault injection) are how you check the implementation actually upholds that.

Takeaway

Consensus is the machinery for making several unreliable nodes agree on one value irrevocably — satisfying uniform agreement, integrity, validity (safety) and termination (liveness) — and a startling range of jobs (leader election, locks, uniqueness, atomic commit, membership) reduce to it. Two-phase commit gives cross-node atomicity but is not fault-tolerant: a single coordinator crash leaves participants blocked in the uncertain state, because the decision lives in one node, not a majority. The deep identity to remember is that linearizability, total order broadcast, and consensus are three faces of one object — an agreed, totally-ordered, durable log, decided one slot at a time. Fault-tolerant algorithms (Paxos, Raft, Zab, VR) share one shape: elect a leader for a term, replicate the log, commit when a majority acks, and have new leaders inherit committed history — and because any two majorities overlap, 2f + 1 nodes tolerate f failures (3 tolerate 1, 5 tolerate 2; never use even counts). The FLP result says you cannot guarantee both safety and liveness in a fully asynchronous network with even one crash, so real systems keep safety always and buy liveness with timeouts and randomization. In practice you rent consensus from ZooKeeper or etcd and apply the discipline of needing it rarely: coordinate once to elect a single leader, then let that leader do linearizable work at local speed — a tiny control plane protecting a large coordination-free data plane. And because these protocols fail only in rare interleavings, you verify them deliberately rather than by example: formal specification (TLA+), deterministic simulation testing, and fault injection (chaos) search the failure space that ordinary tests miss.

Interview prompts

What exactly does consensus guarantee, and which property is the hard one? (§1 — uniform agreement, integrity/irrevocability, validity are safety; termination is liveness, and §5 shows liveness is the one you can't get for free in an asynchronous network.)
Why is two-phase commit not fault-tolerant consensus, and what does 3PC change? (§2 — after voting "yes," participants are in-doubt/prepared (durably) and must obey the coordinator, whose single commit-log write is the moment of decision; if the coordinator crashes before that decision reaches them they block indefinitely holding locks, because the decision lives in one node with no majority. 3PC adds a pre-commit round to be non-blocking in theory but assumes a synchronous network and still fails under a partition, so it isn't used.)
How do you build total-order broadcast from consensus and consensus from total-order broadcast? (§3 — TOB from consensus: run one consensus instance per log slot, deciding the i-th message. Consensus from TOB: every proposer broadcasts its value, TOB delivers all proposals in the same order everywhere, and each node decides the first one delivered — same order means same decision. The agreed sequence number (lesson 16) is the bridge.)
Explain the equivalence of total order broadcast and consensus, and how linearizability fits. (§3 — deciding each log slot's content is one consensus instance; running consensus per slot builds total order broadcast; a linearizable register/CAS is built by appending to and replaying that agreed log, so all three are one object — the linearizable log of lesson 16.)
Why do consensus clusters use 3 or 5 nodes and never 4? (§4 — to tolerate f failures you need 2f + 1 nodes with a majority of f + 1; 3 tolerates 1, 5 tolerates 2, but 4 still tolerates only 1 (majority of 4 is 3) while adding a vote to wait for — and a 2/2 partition deadlocks.)
Why does a majority quorum make leader failover safe? (§4 — any two majorities of the same set share a member (the overlap argument from lesson 09), so a newly elected leader's log necessarily contains every entry a previous majority committed, and two disjoint groups can never both commit conflicting decisions.)
What does FLP say, and how do real systems get around it? (§5 — no deterministic algorithm guarantees both safety and liveness in a fully asynchronous network with one possible crash; systems keep safety unconditionally and recover liveness with timeouts to suspect dead leaders plus randomized election timeouts, relying on real networks being roughly synchronous.)
How should you use ZooKeeper/etcd in a system that needs high throughput? (§6 — use consensus to elect a single leader and hold a lease, then let that leader serve linearizable work locally with no per-operation quorum; reserve consensus for the rare control-plane events (leadership, membership, config) and keep the data plane coordination-free.)