Consensus — Paxos & Raft Intuition

Why this session exists

Replication copies state; consensus constrains which value or ordered command history may be decided despite crashes and uncertain messages. Distinguish agreement, validity and termination. This lesson restores the full Paxos/Raft progression, operational tradeoffs, production examples and worked answers around the byte-preserved reviewed voter exercise.

Prerequisites

Know replicas, durable logs, message retries and the difference between invocation and response. The model permits crash/recovery with intact stable state and delayed/dropped/reordered messages, not malicious Byzantine voters. No cluster or network is created.

Preparation and pacing

Suggested route: intuition and quorum arithmetic → election/log diagram → deterministic programs → operational failures → individual recall answers. The original 90-minute session, 35-minute preparation and 5/15/25/15/10-minute phase labels are planning cues, not measured durations or a guaranteed finish. This remains part of the 130-session learning route; product references are dated, not automatically evergreen.

Optional original discovery pointers

The original URLs are retained, but videos were not watched: historical titles/creator labels are finding aids, not verified attribution, content, duration or availability. “Clearest”, “definitive” and animation praise are not evidence.

• “Raft Consensus Algorithm Explained” — formerly labelled Martin Kleppmann: optional introductory orientation.
• “Raft (MIT 6.824)” — historical MIT label: optional longer academic walkthrough; lecturer and runtime unverified.
• “Distributed Consensus Explained” — formerly labelled ByteByteGo: optional election/log-replication visualization; animation quality/content unverified.
• Raft extended paper: governing protocol reference. Read Figure 2 with Sections 5, 6 and 8; an eight-page skim alone does not cover membership and client interaction.
• Raft project hub: a discovery hub for implementations, explanations and visualizations, not the exact URL of “The Secret Lives of Data.” No interactive partition/election exercise was run here.
• Microsoft Research landing page for “Paxos Made Simple”: historical publication discovery; the author-hosted paper cited below governs the ballot trace. Read its phases to understand Paxos itself, not to assume Paxos is inferior.

From one decision to a replicated state machine

The five-friends analogy is useful only if friends remember their commitments and obey the same protocol. A majority vote taken afresh for every dispute can choose contradictory answers. Consensus chooses one value per instance; state-machine replication orders many such decisions so deterministic replicas can apply the same commands. A log is a common construction, not the definition of every consensus algorithm. Crash-fault consensus does not tolerate arbitrary lying/Byzantine voters.

Separate the client SDK/redirect path, protocol state, durable log, application state machine, snapshots and network transport. A node may possess an uncommitted suffix that is not yet safe to apply. The protocol need not use gRPC or fit a universal thousand-line budget. Snapshots are not just log deletion: they preserve a committed application state together with its included index/term and any client-deduplication state required for recovery.

Derive quorum arithmetic and its limits

Two arbitrary subsets of N nodes with sizes a and b are guaranteed to intersect when a+b>N. For equal cardinality quorums q, choose q = floor(N/2)+1. This is a worst-case guarantee over possible subsets, not a statement that two particular smaller sets never intersect.

Four is not mathematically the “worst possible” cluster size; it simply does not improve independent-failure tolerance over three while increasing quorum size/cost. Similarly, six needs four healthy voters, not three. Count configured voters under the protocol's active membership rules, not a majority of whatever nodes happen to answer a health check. Removing unreachable nodes from a monitoring list is not a legal consensus reconfiguration.

Intersection is necessary for these majority-based arguments but not sufficient. The witness must persist and obey promises/votes/log rules. A witness without the required data cannot automatically substitute for a data-bearing Raft voter. Flexible quorum protocols use more specific cross-phase intersection requirements; do not transfer the equal-majority proof unmodified. Dynamo-style R+W>N is not alone a proof of linearizable consensus.

Safety and liveness under FLP

FLP's 1985 result shows a fully asynchronous deterministic consensus protocol with even one possible crash has admissible nonterminating executions. It is stronger than “no bounded-time guarantee”: guaranteed eventual termination also fails in that model. It does not say a normal run never decides or that random timeouts alone make every failure schedule terminate.

Raft aims to preserve agreement through arbitrary delay and uses randomized election timeouts to reduce split votes when a majority can communicate with suitable timing. A minority partition cannot force useful progress. Typical timing values in an illustration are not standards-required settings; choose from broadcast/network and stable-storage latency, scheduling pauses and the desired recovery behavior.

Paxos, Multi-Paxos, Raft and Zab in context

Lamport's Paxos Made Simple (2001) states the acceptor/proposer/learner roles and two phases. Roles can coexist on one machine. A proposer obtains promises at ballot n and must carry forward the highest accepted value reported by a quorum; a majority accepting the phase-2 proposal chooses the value even if no learner has heard yet. Competing proposers can prevent progress, motivating a stable distinguished proposer. Multi-Paxos amortizes phase-1 work over slots under its leadership/recovery rules; a per-slot decision and a database transaction are not the same abstraction.

Ongaro and Ousterhout's 2014 Raft paper explicitly targets understandability through decomposition and a stronger leader role. Its user study is evidence within that study, not proof that every engineer understands Raft or most Paxos implementations are buggy. Paxos remains a useful family with variants; no universal code-size ratio or “Raft won everything” claim is needed. Zab is ZooKeeper's distinct atomic-broadcast protocol, not interchangeable with Raft and not merely a reason to dismiss ZooKeeper as legacy.

Documented production examples

Use narrowly supported examples instead of an unchecked product list:

• etcd: its v3.5 API guarantees describe consensus/linearizability boundaries; the performance guide connects request latency with disk and network constraints.
• Consul: its architecture documentation describes a Raft-based consensus protocol for server state.
• CockroachDB: the replication layer uses per-range Raft groups. This is a counterexample to the old advice that consensus must never be on a database data path.
• TiKV: its architecture documents Raft-based replication for Regions.
• Chubby: Google's 2007 Paxos Made Live paper documents the Paxos replicated log beneath Chubby; the 2006 lock-service paper supplies architectural context. A lock-service guarantee is not automatic fencing of every external side effect.

These are source-backed roles, not a claim that every operation in each product is a linearizable Raft transaction. ZooKeeper uses Zab. Kafka's controller/data-replication distinctions require their own release-specific review; MongoDB config servers should not be casually listed as generic Raft clusters here.

Paxos worked ballot trace

Acceptors A, B and C start empty. Proposer P sends prepare(7) to A and B, learns no accepted value, and sends accept(7, red). Both accept: red is chosen. P crashes before telling a learner. A new proposer Q sends prepare(8) to B and C. B reports (7, red), C reports none. Q must propose red, even if its client originally requested blue. The overlap carries the chosen value forward.

Now vary the trace: only A accepted (7, red), so red was not yet chosen. Q's replies from A and B can still force red at ballot 8; safety permits retaining a value before anyone knows it was chosen. If Q hears only from B and C and neither has accepted, it can choose blue. The old proposer can no longer collect a ballot-7 quorum because B/C promised ballot 8. Distinguish accepted by one node, chosen by a quorum, and learned by a client.

Election and log-repair worked trace

Take five voters A–E. All start in term 4, with committed entries through index 7. A times out, increments to term 5, persists its term/self-vote, and requests votes with its last log term/index. B and C grant after their freshness checks and stable state updates. Three distinct votes including A elect it. Duplicate replies from B do not count twice.

A same-term heartbeat must not clear B's vote. Otherwise B might vote for another candidate in term 5, destroying the one-vote intersection argument. A higher-term request/reply updates the receiver's term and role before subsequent role-specific handling. A rejected RequestVote need not mean the candidate's numeric index is too small: the last log term is compared first.

Suppose A appends a term-5 command at index 8 and persists it. B stores the matching entry after checking the previous index/term and acknowledges. With five configured voters, A+B is only two: no majority commit. C then stores it, giving three durable copies of a current-term entry; A can advance commitIndex and apply through index 8. D/E can learn the entry or commit index later. The client reply should follow the service's agreed apply/result contract.

If A becomes isolated with B, the remaining C/D/E can potentially elect a higher-term leader whose log meets the election restriction. A can still believe it leads, but cannot commit new conflicting work with only two. On healing, higher terms force role changes and AppendEntries reconciles uncommitted conflicting suffixes. It is wrong to promise that a high-term minority must always adopt the old majority leader without a new election: isolated candidates may have increased their terms. Pre-vote can reduce disruption in implementations that support it, but it is not part of every minimal Raft sketch.

Why a copied old entry is not enough

Imagine a leader in term 5 sees a term-2 entry on three of five disks. Raft does not allow it to newly commit that entry solely by counting copies. Figure 8's counterexample motivates the current-term restriction: commit a current-term entry on a majority, and preceding entries become committed indirectly. The full proof uses log matching, election restriction, leader completeness and persistent state together. Saying “only the leader appends its own log” or “quorums overlap” alone omits necessary rules.

Hands-on: exact retained vote-rule checks

This exact previously reviewed program remains unchanged. It checks same-term vote preservation, term-first log freshness and majority intersections for one through seven voters. It models no persistence, transport, full log replication or membership and is not a Raft implementation. Its heartbeat result is a term/vote abstraction, not the complete AppendEntries log-prefix validation.

from dataclasses import dataclass
from itertools import combinations
 
@dataclass
class Voter:
    term: int = 0
    voted_for: str | None = None
    last_term: int = 0
    last_index: int = 0
 
    def observe(self, term):
        if term > self.term:
            self.term, self.voted_for = term, None
 
    def vote(self, term, candidate, last_term, last_index):
        self.observe(term)
        if term < self.term:
            return False
        fresh = (last_term, last_index) >= (self.last_term, self.last_index)
        if fresh and self.voted_for in (None, candidate):
            self.voted_for = candidate
            return True
        return False
 
    def heartbeat(self, term):
        self.observe(term)  # same-term heartbeat MUST NOT clear voted_for
        return term >= self.term
 
v = Voter(last_term=2, last_index=8)
assert v.vote(3, "A", 2, 8)
assert v.heartbeat(3)
assert not v.vote(3, "B", 2, 9)
assert not v.vote(4, "B", 1, 100)  # index alone does not imply freshness
assert v.vote(4, "C", 3, 1)
assert not v.heartbeat(3)
for n in range(1, 8):
    q = n // 2 + 1
    quorums = list(map(set, combinations(range(n), q)))
    assert all(a & b for a in quorums for b in quorums)
assert 5 // 2 + 1 == 3 and 6 // 2 + 1 == 4
print("vote-rule checks and majority intersection: PASS")

observe clears a vote only for a higher term. vote compares (last_term, last_index) lexicographically. A longer old-term log is not necessarily fresher. A same-term heartbeat preserves the previous vote, while an older term is rejected. Exhaustive set pairs establish these finite intersection cases, not a complete protocol proof.

Offline Paxos and commit-rule checks

The following second program models a single decree, not a distributed service. It tests the accepted/chosen distinction, highest-accepted carry-forward and rejection of lower ballots, then checks the current-term direct-commit predicate. It complements rather than replaces the exact retained voter program.

from dataclasses import dataclass
 
@dataclass
class Acceptor:
    promised: int = -1
    accepted: tuple | None = None
 
    def prepare(self, ballot):
        if ballot < self.promised:
            return False, None
        self.promised = ballot
        return True, self.accepted
 
    def accept(self, ballot, value):
        if ballot < self.promised:
            return False
        if self.accepted and self.accepted[0] == ballot and self.accepted[1] != value:
            raise ValueError('proposer reused ballot for a different value')
        self.promised = ballot
        self.accepted = (ballot, value)
        return True
 
def choose_value(replies, proposed):
    prior = [value for ok, value in replies if ok and value is not None]
    return max(prior, key=lambda x: x[0])[1] if prior else proposed
 
a, b, c = Acceptor(), Acceptor(), Acceptor()
assert a.prepare(7)[0] and b.prepare(7)[0]
assert a.accept(7, 'red') and b.accept(7, 'red')
replies = [b.prepare(8), c.prepare(8)]
value = choose_value(replies, 'blue')
assert value == 'red'
assert b.accept(8, value) and c.accept(8, value)
assert not c.accept(7, 'blue')
 
def direct_commit(current_term, entry_term, acknowledgers, voters):
    valid = set(acknowledgers) & set(voters)
    return entry_term == current_term and len(valid) >= len(voters) // 2 + 1
 
voters = {'A', 'B', 'C', 'D', 'E'}
assert not direct_commit(5, 2, {'A','B','C'}, voters)
assert direct_commit(5, 5, {'A','B','C'}, voters)
assert not direct_commit(5, 5, ['A','A','B','outsider'], voters)
print('Paxos carry-forward and Raft direct-commit predicate: PASS')

Prepare/accept changes here are in memory; a crash-recovering implementation must persist the corresponding state before acknowledgements. choose_value assumes the caller collected a valid quorum of replies for one ballot; it is not a complete proposer. Ballots must be globally unique/ordered and a proposer must not reuse one for inconsistent values. The direct-commit predicate assumes successful matching-log acknowledgements from the current configuration and omits the rest of Raft. Finite tests are not a formal safety/liveness proof.

Operating consensus without magical availability claims

Quorum loss can come from hardware, partitions, storage stalls or human changes; it is not always human-caused. Check configured voter membership, connectivity, current terms and stable-storage evidence before changing topology. Do not “repair” an outage by inventing a smaller quorum over survivors; use the implementation's supported recovery procedures and understand any data-loss boundary.

Disk latency matters because relevant protocol acknowledgements follow stable-state updates. Dedicated/appropriately provisioned storage can isolate contention, but “NVMe means single-digit milliseconds” is not a guarantee. Monitor fsync tail latency, leader-change rate, proposal/commit latency, queues, space and network latency. Occasional legitimate leader changes do not make a cluster unhealthy merely because the count is nonzero.

Placement matters beyond node count. Five voters across zones 2+2+1 tolerate any two individual voter failures. Losing a two-voter zone plus another voter leaves only two and loses quorum: it does not guarantee survival of “any two things.” Moving three to five voters increases machine count by 5/3, not doubles availability or necessarily doubles cost. Learners are non-voting replicas for supported purposes; they do not improve voter quorum tolerance or automatically make every read linearizable.

Membership, snapshots, reads and locks

Membership changes need overlapping/joint or another implementation-supported safe configuration protocol. Replacing all voters at once can create disjoint groups that each believe they own a quorum. Snapshots must preserve committed application state and recovery boundaries before older log data is discarded. Backup restore requires consistent cluster identity/membership handling, not copying one arbitrary log directory into every node.

A stale leader must establish current authority for a linearizable read—through a quorum/read-index mechanism or a correctly specified lease with its timing assumptions—and apply through the required index. A lease in a consensus-backed lock service does not physically prevent a paused old client from writing to an external database. Use sink-enforced fencing tokens/version rules where stale-owner effects matter.

A concrete joint-configuration transition

Let the old voters be A/B/C and the new voters be C/D/E. A/B alone is an old majority; D/E alone is a new majority. Those sets are disjoint, so simply switching some nodes to the new set can let two groups act independently. In the extended paper's joint phase, a decision needs a majority of the old set and a majority of the new set, not merely a majority of their union. A/C/D satisfies both (A/C and C/D); A/B/D is three of five but satisfies only the old majority.

The protocol first records the joint configuration, then transitions to the new-only configuration through its specified commitment rules. In this paper's protocol, a server uses the latest configuration in its log even before that configuration entry is committed; the leader must commit the joint entry before proposing the new-only entry. Do not replace this activation rule with an improvised “everyone flips after a timeout.” Catch up new servers before letting lagging voters endanger availability, and do not overlap arbitrary reconfigurations. Different implementations can use other proven membership mechanisms; this predicate is an explanation of joint consensus, not a membership-change API.

from itertools import combinations
 
def majority(acks, voters):
    return len(set(acks) & voters) > len(voters) // 2
 
def joint_quorum(acks, old, new):
    return majority(acks, old) and majority(acks, new)
 
old, new = set('ABC'), set('CDE')
assert not joint_quorum('ABD', old, new)  # union majority is insufficient
assert joint_quorum('ACD', old, new)
subsets = [set(s) for k in range(6) for s in combinations('ABCDE', k)]
valid = [s for s in subsets if joint_quorum(s, old, new)]
assert all(a & b for a in valid for b in valid)

The exhaustive 32-subset check shows this fixed membership predicate has intersecting successful sets. It does not model log configuration activation, durable writes, a rolling upgrade or arbitrary failures.

Read authority, applied state and retry identity

Suppose a new leader owns all entries through index 8 but has applied only through 7. Serving a local application read now can miss a committed command. In the paper's read-only path, a leader commits an entry in its own term to learn the committed prefix, confirms current authority with a majority for the read, and waits for the application to cover the required committed index before answering. Merely receiving a heartbeat earlier or having a large term is insufficient; an isolated old leader may still have both. Lease alternatives require their own clock/timing assumptions.

A client sends (client=C, sequence=12, debit=5); the command commits and applies, but its response is lost. Retrying with a fresh identity can debit twice even though both log entries are perfectly agreed. Store the request identity and result in the replicated state machine; replay of that identity returns the saved result instead of repeating the mutation. Include that state in snapshots and define retention/session expiry. The paper's latest-sequence approach assumes the relevant client request discipline; concurrent/out-of-order requests need an appropriate deduplication window. External payment/email effects still require an idempotent sink or durable delivery protocol—Raft cannot atomically rewind an external service.

Historical incident pointers

The original Cloudflare KV incident pointer is retained for quorum-loss investigation, not as freshly verified evidence for a 2020, 27-minute, human-caused outage. The etcd v3.5 performance guide supports disk/network constraints, not the original invented aggregate of Kubernetes postmortems. A three-voter cluster losing one zone plus one surviving voter has no majority; this is a hypothetical fault-placement calculation, not a claim that five voters survive any two correlated incidents.

Control plane, data plane and geography tradeoff

Use a mature consensus implementation for required single decisions. Avoiding coordination is valuable where operations genuinely commute or ownership is safely partitioned, but idempotency and event sourcing do not automatically eliminate cross-object invariants or ownership changes. CRDTs have specific convergence semantics, not unbounded free scaling.

Consensus can coordinate infrequent partition assignment while data operations run locally under fenced ownership. It can also correctly sit on every shard's data-write path, as replicated databases demonstrate. Cross-shard atomicity introduces another coordination layer. Neither “consensus everywhere” nor “never on the data path” is a universal rule.

A WAN quorum can improve resilience to region failure at the cost of network-dependent commit latency and partition availability. A write commonly waits for enough durable acknowledgements to form the relevant majority, not every voter or invariably the slowest node in the cluster. Disk, batching and pipelining also affect latency. Independent regional groups plus asynchronous replication lower local latency but change the consistency/conflict and failover contract; they are not an equivalent replacement for a single globally linearizable group.

Original recall questions, corrected worked answers

1. State FLP accurately

In a fully asynchronous message-passing model with a possible crash, deterministic consensus cannot guarantee termination for all admissible executions. The result does not forbid safety or successful decisions in many executions, and is not limited to a fixed-time bound.

2. Does Raft escape it?

No contradiction: safety and progress have different assumptions. Randomized timeouts reduce repeated split votes when a majority and sufficiently favorable timing exist; permanent loss of quorum or hostile scheduling can still prevent progress.

3. Three sub-protocols

Election chooses a proposer; log replication transfers entries and repairs matching prefixes; safety rules constrain votes, durable state, commitment and leader succession. Election alone does not decide a durable application result.

4. Five-node failures

Majority is three, so two unavailable voters can be tolerated if the remaining voters can communicate and satisfy protocol requirements. With only two left, recovery of one suitable voter restores a possible quorum; “until a fourth recovers” was wrong.

5. Why prefer odd voter counts?

Three needs two, four needs three; both tolerate one unavailable voter. Five needs three, six needs four; both tolerate two. Odd sizes are often economical for this metric, but placement and operational requirements still govern the final design.

6. What demotes a stale leader?

Observation of a higher term triggers persistent term update and follower behavior under Raft's rules. Same-term heartbeats must preserve votedFor. A minority can temporarily believe it leads without being able to commit conflicting entries.

7. Four Raft examples and one Paxos example

etcd, Consul, CockroachDB's range replication and TiKV's Region replication have documented Raft use. Google's Paxos Made Live documents Chubby's Paxos-backed replication. ZooKeeper uses Zab; do not pad the list with unverified product claims.

8. Why prioritize storage for etcd?

Relevant acknowledgements wait on stable storage, so contention and slow fsync can increase commit latency and election disruption. Provision and measure disk/network tails; dedicated SSDs are an operational option, not a mathematical latency guarantee or a prohibition on every shared-storage design.

9. Why did Raft emphasize understandability?

The 2014 paper explicitly decomposes the protocol and studies understandability. That explains a design goal and measured study result, not a universal industry victory, unique correct implementation, or claim that most Paxos implementations are defective.

10. Three-region design stretch

First state the required region-failure tolerance, read/write consistency and latency budget. Place voters so the desired surviving region set can form a quorum, then estimate/measure WAN and disk costs. If replacing global consensus with regional groups plus async replication, explicitly accept conflict resolution, stale reads and recovery-point changes. Neither architecture is a free improvement over the other.

Original election-sketch disposition

The former threaded sketch reset votedFor on same-term heartbeats, lacked log freshness/persistence and used timers that were not a durable network protocol. It could not demonstrate committed-write safety because it had no replicated log. The retained voter program and the additional ballot/commit exercises repair those teaching objectives with deterministic assertions. A 2/3 partition is reasoned through against the real protocol above, not advertised as a complete simulation of production Raft.

Explain-out-loud test

Without notes, explain why uncertain delay makes termination difficult, trace a candidate's persistent term/vote and log-freshness check, and derive why three configured voters need two while five need three. Then use the red/blue Paxos trace to explain how a prior accepted value survives a proposer crash. A complete explanation distinguishes election, durable replication, commitment, application and client acknowledgement; it names the current-term rule and why retries/linearizable reads need additional conditions.

Connections and source scope

Consistency models state the external promise; sharding repeats coordination in separate groups; multi-region placement changes quorum latency/availability; Kubernetes depends on etcd; controller and lock-service designs need explicit membership and fencing. These relationships preserve the original study route without implying every system uses the same algorithm.

Continue with S074 · Sharding & Partitioning Strategies. Return to The 6-Month Learning Plan. For preparation, revisit S072 consistency, S071 replication and S061 TCP/IP/DNS concepts; the original S042 networking label pointed to the wrong topic.

Current complete lesson review: 2026-10-10. Primary snapshots captured 2026-10-08 are reused after raw-to-canonical and exact-quotation verification, not claimed as fresh downloads. All three in-memory programs are bounded checks, not a native Paxos/Raft service or general safety/liveness proof. No cluster, transport, durable log, failover drill, lease, snapshot restore or external-effect integration was executed. MDX/diagram checks are independent of deployment correctness.

Governing references:

• FLP, JACM 1985

• Raft extended paper, 2014

• Paxos Made Simple, 2001

• etcd v3.5 API guarantees and performance

• Consul consensus architecture

• CockroachDB replication layer

• TiKV 7.1 architecture

• Chubby, OSDI 2006

• ZooKeeper 3.9.3 internals

• Paxos Made Live, PODC 2007

• Apache ZooKeeper Zab1.0 protocol