Unit 5.2 · about 4 h
267 / 324Replication, quorums and consensus vocabulary
Copies alone do not define which writes survive or which reads are fresh. Quorum arithmetic becomes useful only when membership, persisted acknowledgements and version comparison are explicit.
- explain
- derive
You can now
- Trace replication lag and acknowledged-write loss during asynchronous failover.
- Derive quorum intersection and construct a stale-membership counterexample.
- Separate consensus safety properties from termination assumptions and failure-detector suspicions.
Covers
- Replication leaders, followers, lag and failover vocabulary
- Quorums, intersection assumptions and stale membership counterexamples
- Consensus and failure-detector vocabulary
Study, in this order
2 steps
- DDIA, 2nd edition: leaders, lag and quorum limitsDesigning Data-Intensive Applications, 2nd edition - distributed data path
Chapter 6, Single-Leader Replication and Synchronous Versus Asynchronous Replication, pp. 198 to 201; Handling Node Outages, pp. 204 to 206; Problems with Replication Lag, p. 209; Leaderless Replication through Understanding the limitations of quorum consistency, pp. 229 to 234
- DDIA, 2nd edition: failure detection and consensus contractDesigning Data-Intensive Applications, 2nd edition - distributed data path
Chapter 9, Fault Detection and Timeouts and Unbounded Delays, pp. 351 to 354; Chapter 10, Consensus, pp. 425 to 429, through the single-value consensus properties
Depth · Stop before Compare-and-set as consensus. Learn agreement, integrity, validity and conditional termination, not a Raft implementation. Timeouts alone do not guarantee termination in a fully asynchronous execution; practical progress needs additional assumptions such as eventual synchrony.
Focus on
- State whether an acknowledgement means receipt, persistence or application at each replica. Asynchronous failover can discard acknowledged writes that never reached the promoted follower.
- For a fixed replica universe of size \(n\), \(|W \cap R|\) is at least \(w+r-n\). This proves overlap, not a complete linearizability protocol.
- Membership changes, forgotten acknowledged data, concurrent writes and faulty timestamp resolution can break the freshness argument.
- Consensus agreement, integrity and validity are safety properties. Progress requires the protocol's fault and timing assumptions; a timeout supplies suspicion, not knowledge.
Reproduce closed-book
write(x,1) using old membership ABC; event 2, A and B persist 1 and P receives OK; event 3, Q invokes read(x) using new membership CDE, before state transfer; event 4, D and E reply 0 and Q returns 0. Both configurations have \(n=3\),\(w=2\),\(r=2\), but \(W=\{A,B\}\) and \(R=\{D,E\}\) do not intersect. Check by hand that this violates linearizability: the completed write precedes the stale read. State why a coordinated membership transition is missing.Traps
- Adding quorum sizes across different membership views as though they were subsets of one universe.
- Calling a majority vote consensus without a protocol that preserves earlier decisions across leaders and restarts.
- Calling leader receipt durable on a follower, or assuming replication replaces a backup.
Practice
The section mini-project covers this: replica lag, persisted acknowledgements, node loss and a stale-membership history, with configuration IDs recorded in every operation.
Self-test
-
For \(n=5\),\(w=3\),\(r=3\), what overlap is guaranteed?
At least one replica, provided both sets belong to the same five-member configuration. -
Does \(w+r>n\) alone prove linearizability?
No. It proves set intersection. Version ordering, concurrent operations, read behavior, persistence and membership transitions still need a correct protocol. -
What happens if an asynchronous leader acknowledges a write, dies, and a follower without it is promoted?
The acknowledged write can be lost from the surviving history. Local persistence on the old leader does not guarantee survival of that failover. -
Must a consensus group keep deciding during a permanent partition?
Not unconditionally. Safety must be preserved, while termination depends on reachable participants and the protocol's timing assumptions.
Completion criterion
Stop when
You derive the intersection bound and explain exactly why the two-majority history violates linearizability without contradicting the bound.
Mark passed, then open 5.3 Only mark this when you can do it without notes.Leads to
- 5.3 Consistency models and conflict resolution Name the histories that an intersecting replica set still does not rule out.
Comes after
- 5.1 Partial failure, clocks and event orderingApply uncertain failure detection to replication and failover.
Resources for this unit
- Designing Data-Intensive Applications, 2nd edition - distributed data path Read the selected chapters on replication, partitioning, distributed-system trouble, consistency and consensus, batch processing and stream processing. For each guarantee, write its assumptions, a confirming history and one counterexample outside the boundary.
Also in this section
- Gossip Glomers - Echo, Unique ID and Broadcast Complete Challenge 1 Echo, Challenge 2 Unique ID Generation and Challenge 3a Single-Node Broadcast. Add 3b Multi-Node Broadcast only after writing the delivery, duplicate and partition assumptions. Preserve protocol histories rather than relying on a success banner.
- MIT 6.5840 - MapReduce, RPC and consistency bridge Use the introductory MapReduce, RPC, GFS and consistency lectures after the local RPC and store gates. The MapReduce lab is optional. Do not begin Raft or sharded KV as foundation work.
- Apache Kafka documentation - design Read Persistence, The Consumer (Consumer Position), Message Delivery Semantics, Using Transactions, Replication and Log Compaction for a concrete log: offsets, consumer positions, the at-most-once, at-least-once and exactly-once boundaries, in-sync replicas and compaction guarantees. Map each guarantee onto your own log before trusting it.
- Building Distributed Systems from Scratch - one challenge path Choose one messaging, durable-log or partitioning challenge that matches a failed checkpoint. State the model, failures and evidence independently because interactive grading behavior has not been verified.
- AlgoMaster System Design - distributed fundamentals slice Use Database Replication, Consistency Models, Logical Clocks, Vector Clocks, Network Partitions, Split Brain Problem, Leader Election, Database Partitioning, Consistent Hashing, Delivery Semantics, Dead Letter Queues, Idempotency, Two-Phase Commit (2PC), Outbox Pattern and Streaming Engines as bounded review after DDIA. Attempt only the exercise that matches your implemented history, then challenge its assumptions with a node-loss, delay or duplicate case.