Unit 5.7 · about 6 h
272 / 324Distributed histories and deterministic failure simulation
Assume Programming's debugging-hypotheses and synchronization-hazards units. Here the scheduler controls network and persistence boundaries rather than local thread races, and the evidence is a client history checked against a named distributed contract.
- implement
- measure
You can now
- Implement a deterministic scheduler for delayed, dropped and duplicate messages and crash-recovery transitions.
- Check a small register history against an independent sequential specification.
- Count stale responses and progress events under controlled faults, preserving a repeatable counterexample trace.
- Distinguish a finite liveness stall from a demonstrated safety violation.
Covers
- Distributed histories, safety violations and liveness stalls
- Deterministic network and node-failure simulation
Study, in this order
2 steps
- DDIA, 2nd edition: models, safety and controlled failuresDesigning Data-Intensive Applications, 2nd edition - distributed data path
Chapter 9, System Model and Reality, pp. 380 to 383; Formal Methods and Randomized Testing through Deterministic simulation testing, pp. 384 to 387; Chapter 10, What Makes a System Linearizable?, pp. 404 to 408
Depth · Use application-level deterministic scheduling and a tiny exhaustive checker. Stop before runtime-level simulation; full model checking and consensus proofs are later work.
- Gossip Glomers: broadcast contractsGossip Glomers - Echo, Unique ID and Broadcast
Challenge 3a, Specification for broadcast, read and topology; Evaluation
Depth · Read the protocol contract before coding. Challenge 3a is single-node; its success says nothing about partitions or process-crash durability.
Focus on
- Record process, operation ID, object, input, result and ordered invocation/response events. Internal logs alone do not specify what clients observed.
- A register checker enumerates legal sequential orders constrained by completed-before-invoked edges. Treat pending timed-out writes as potentially executed, not automatically absent.
- Control scheduling, clock reads, randomness, iteration order and I/O completions. A random seed alone does not make an uncontrolled concurrent program deterministic.
- Separate durable state from volatile state on restart. A bad completed read is a finite safety witness; no progress during a bounded observation interval is a stall, not proof of permanent nontermination.
Reproduce closed-book
write(x,1), L persists 1; 2 P1 receives OK; 3 P2 invokes a read served by F; 4 P2 receives 0; 5 F crashes, losing only volatile state; 6 F restarts with durable 0; 7 heal the link; 8 deliver a repair assigning \(F=1\); 9 deliver that repair again; 10 P2 invokes another read from F; 11 it returns 1. Preserve the client events as JSON. A closed-book checker enumerating complete-operation permutations, enforcing response-before-invocation edges and the register rule, must reject the first read under linearizability. Fix this specific schedule by routing reads to the reachable, unchanged \(L\); responses become \([1,1]\) rather than \([0,1]\). Repeat each version three times and assert byte-identical traces within each version. Count stale responses, not wall-clock latency. These are synthetic logical ticks, not network timings. Add a pending read that waits during a partition, then completes after repair; report the bounded wait as a liveness stall, not a safety violation or proof of nontermination.Traps
- Checking replicas against one another instead of checking the observed history against an independent object specification.
- Dropping timed-out operations from a safety history. Their effects may be visible to later completed reads.
- Calling an in-memory model a crash-durability test, or claiming a single passing fault schedule proves all executions correct.
Practice
Gossip Glomers Challenge 3a: Single-Node Broadcast
Implement broadcast, read and topology; use the Evaluation command's one-node broadcast workload
Reuse the Echo protocol harness and Maelstrom setup from Challenge 1, not a copied broadcast solution. Preserve protocol histories. The section mini-project adds explicit process-loss and persistence tests outside Maelstrom's failure model.
Gossip Glomers Challenge 3b: Multi-Node Broadcast (optional extension)
Specification and Evaluation with five nodes, no network partitions
Attempt only after writing delivery, duplicate and partition assumptions and passing 3a. Stop at 3b; do not infer partition tolerance from this workload or continue into the later challenges as foundation work.
Self-test
-
Why is the first read a safety violation rather than just a slow follower?
The write completed before the read began. With no intervening write, returning 0 cannot fit a real-time-respecting register order, regardless of why the follower lagged. -
If a read has not completed by tick 100, is linearizability violated?
Not by that fact alone. It shows a bounded progress stall. Linearizability is a safety property and does not require operations to complete. -
A write times out, then a read returns its value. Must the history be rejected?
No. The pending write may have taken effect. A checker must consider a completion or placement of it consistent with the observed completed operations. -
Does Challenge 3b test network partitions?
No. It uses multiple nodes without partitions. A partition-resilience claim needs separate failure evidence; 3a and 3b also do not intentionally crash node processes.
Completion criterion
Stop when
The checker rejects the stale-read trace and accepts the reachable-leader repair, repeated schedules have identical traces, and your dossier separates the synthetic safety witness, the bounded progress stall and your broadcast challenge results.
Mark passed, then open 5.8 Only mark this when you can do it without notes.Leads to
- 6.7 Failure domains, correctness signals and safe rollout Use correctness histories alongside availability signals during faults.
Comes after
- 3.8 Deterministic network fault injectionLift the fault schedule to distributed histories and model checking.
- 5.3 Consistency models and conflict resolutionTurn the stated model into an independent history checker.
- 5.6 Consumer lag, watermarks and state rebuildInject gaps, duplicates and node loss into your state rebuild contract.
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.
- 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.
Also in this section
- 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.