Storage and Distributed Failure Semantics
Prerequisites: S5 persistence; S6 replication, transactions, and consistency; lesson 4. Budget: 40-60 hours. Outcome: connect acknowledgment to recovery and consistency claims to observable operation histories.
Diagnostic
Explain the difference between a write reaching a process buffer, becoming durable under a declared failure model, and becoming visible to a reader. Draw a retry after a lost reply. If these collapse into one notion of “success,” revisit S6 first.
Worked example: a torn log tail
A record contains a length, payload, and integrity check. A crash leaves a complete record A followed by only a prefix of B. Recovery must validate framing and integrity before applying a record. The incomplete suffix cannot be treated as a committed operation simply because its length field exists.
An integrity check can detect corruption under its assumptions; it does not establish transaction commitment. Include a commit boundary in your model. Replaying committed records should be idempotent or use a persisted sequence number to avoid duplicate application. Bounded record sizes prevent a corrupt length field from causing unlimited allocation.
This exercise can use simulated persistence. Real storage behavior depends on flush semantics, filesystem, controller, and device assumptions. Record which layers your experiment covers.
Worked example: real-time order constrains a register
An initially zero register receives write(1), which completes. A later, non-overlapping read returns 0. A linearizable register cannot explain this history: the write must precede the read in a sequential order that respects real-time precedence.
If the read overlaps the write, returning 0 or 1 can be consistent with linearizability, depending on where operations are ordered. Completion order alone does not settle overlapping operations. Capture invocation and response events and the sequential specification before judging a history.
Linearizability of a single register is not the same promise as serializability of multi-operation transactions. Nor does a bounded history checker prove every future execution correct.
Guided assignment
Build a small append-only key-value store with put/get, bounded records, commit information, and recovery. Separate volatile and persisted storage in a deterministic model, or use a real implementation with clearly narrower process-crash claims. Inject a crash or truncation after each persistence boundary. Include duplicate operation IDs and corrupt or incomplete record tails.
Create a two-replica simulator with delayed messages. Record put/get invocation and completion events, then compare observed histories with a sequential register specification. Demonstrate one stale non-overlapping read and one overlapping read that can be legally ordered. You may use a brute-force checker for small histories; document its search bound and treatment of pending operations.
Acceptance: acknowledged committed writes survive modeled failures; incomplete records do not become visible; recovery repeated twice yields the same state; the history checker rejects the known stale read. Preserve a crash matrix and at least one minimal failing history. Do not label the simulator a production consensus implementation.
Independent transfer
The client times out after the storage engine committed a write. Can the checker assume the write never happened? Check: no. A pending or timed-out operation may have taken effect; the history model must permit appropriate completion or explicitly resolve its status.
For more depth, choose either a storage-engine lane or a replicated-state-machine lane. The Raft paper and materials and MIT distributed systems course provide a later research/lab sequence. Do not implement both lanes simultaneously merely to increase topic count.
Read recovery and consistency topics in Database Internals and DDIA. Use the assessment contract to defend exactly which guarantees your evidence supports.