Unit 5.3 · about 4 h
268 / 324Consistency models and conflict resolution
Assume Programming's transactions-isolation unit. This unit moves from database transaction interleavings to client-visible replica histories, where convergence and freshness are different contracts.
- explain
You can now
- Classify explicit histories under linearizable, causal, eventual and session contracts.
- Distinguish serializable transactions from real-time ordered single-object operations.
- Explain what last-write-wins discards and choose an application merge that preserves the required intent.
Covers
- Strong, eventual, causal and session consistency vocabulary
- Linearizability versus serializability vocabulary
- Conflicts, last-write-wins limits and application resolution
Study, in this order
2 steps
- DDIA, 2nd edition: consistency definitions and conflict intentDesigning Data-Intensive Applications, 2nd edition - distributed data path
Chapter 6, Problems with Replication Lag, pp. 209 to 214; Dealing with Conflicting Writes, pp. 222 to 228; Chapter 10, Linearizability and What Makes a System Linearizable?, pp. 402 to 408, including Linearizability Versus Serializability
- Consistency Models: bounded definition reviewAlgoMaster System Design - distributed fundamentals slice
Sections 3.1 Linearizability, 3.3 Serializability and Strict Serializability, 4.1 Eventual Consistency, 4.2 Causal Consistency, and 5 Client-Centric Consistency Models
Depth · Use after DDIA to label your histories. Skip the product-choice tables and quiz; do not treat the consistency spectrum as a total ordering of all guarantees.
Focus on
- A linearization is a legal sequential object history that respects response-before-invocation order. Overlapping operations need not follow invocation order.
- Serializability orders whole transactions but does not by itself require real-time order. Strict serializability adds it; per-object linearizability alone does not make a multi-object transaction atomic.
- Eventual convergence needs propagation and a resolution policy. Read-your-writes and monotonic reads are session guarantees; causal consistency also preserves dependencies across clients.
- LWW converges with a deterministic total timestamp order, but discards acknowledged updates. Sibling merge must preserve application meaning, especially deletion.
Reproduce closed-book
write(x,1) at event 1 and receives OK at 2; P2 invokes read(x) at 3 and receives 0 at 4. It is not linearizable; if each operation is its own transaction, serializability alone permits the order read, write. H2: P1 invokes write(x,1) at 1 and receives OK at 4; P2 invokes read(x) at 2 and receives 0 at 3. It is linearizable in the order read, write. Separately, simulate two concurrent writes \((\text{timestamp}=100, \text{node}=A, \text{value}=\text{red})\) and \((90, B, \text{blue})\), comparing \((\text{timestamp}, \text{node})\): both arrival orders converge to red and discard blue. Merge cart siblings \(\{\text{book}\}\) and \(\{\text{dvd}\}\) by union after each device removed the other item from \(\{\text{book}, \text{dvd}\}\); both deleted items reappear. Explain why convergence is not preservation of intent. Event numbers and timestamps are synthetic, not elapsed-time measurements.Traps
- Using the phrase strong consistency without specifying the object, operations and real-time requirement.
- Claiming eventual convergence bounds lag or guarantees durability.
- Assuming set union correctly handles removals, or that LWW's greatest timestamp identifies the physically latest write.
Practice
The section mini-project covers this: classify permitted and rejected histories, reproduce LWW data loss, and test an application conflict policy including removals.
Self-test
-
May a read overlapping a write return the old value?
Yes, if a legal linearization places it before the write. Other completed observations can constrain that order. -
While
write(1)is pending, read A returns 1; after A completes, read B returns 0. Is that linearizable if no other write exists?No. A forces the write before A, real time forces A before B, and then B must read 1. -
Does read-your-writes imply all users see the newest value?
No. It constrains the writer's session, not arbitrary readers. -
P writes a post; Q reads it and writes a reply; R sees the reply but not the post. Which model rejects this?
Causal consistency rejects visibility of the dependent reply without its causal predecessor. Eventual consistency alone does not reject a temporary lagging view.
Completion criterion
Stop when
You give legal orders for H2 and the merely serializable H1, reject H1 under linearizability, and explain a convergent merge that still violates application intent.
Mark passed, then open 5.4 Only mark this when you can do it without notes.Leads to
- 5.7 Distributed histories and deterministic failure simulation Turn the stated model into an independent history checker.
Comes after
- 5.2 Replication, quorums and consensus vocabularyName the histories that an intersecting replica set still does not rule out.
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.
- 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.
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.