db-16 — References

Primary sources

  • Leslie Lamport, Time, Clocks, and the Ordering of Events in a Distributed System, CACM 21(7), 1978. The original paper. Defines happens-before, the logical clock, and (in §4) the construction of a total order consistent with causality. https://lamport.azurewebsites.net/pubs/time-clocks.pdf
  • Colin Fidge, Timestamps in Message-Passing Systems That Preserve the Partial Ordering, 11th ACSC, 1988. Introduces vector clocks and proves they characterize the happens-before relation exactly.
  • Friedemann Mattern, Virtual Time and Global States of Distributed Systems, 1989. The companion vector-clock paper; reads more approachably than Fidge.
  • Sebastiano Vigna, splitmix64 — a small, fast, well-distributed 64-bit mixer used as the seeder for xoroshiro. https://prng.di.unimi.it/splitmix64.c

Determinism and reproducibility

  • Frans Kaashoek et al., Eraser: A Dynamic Data Race Detector for Multithreaded Programs, SOSP 1997. Not directly cited here, but the motivation — "if you cannot replay a bug deterministically you cannot debug it" — is the entire reason this lab exists.
  • FoundationDB's simulation testing (Apple/Snowflake) — a production example of deterministic discrete-event simulation at scale. https://apple.github.io/foundationdb/testing.html
  • Jepsen — Kyle Kingsbury's distributed-systems testing harness. Not deterministic itself (it injects real faults), but the methodology of "generate events, observe a history, check it against a model" is the vocabulary db-16 sets up. https://jepsen.io/

Production engines that use these primitives

  • Riak / Dynamo — vector clocks for sibling reconciliation.
  • CRDTs (Shapiro, Preguiça, Baquero, Zawirski, 2011) — vector clocks and version vectors are the substrate for state-based merge functions.
  • TLA+ — Lamport's specification language; ordering events by Lamport clock is the mental model behind every TLA+ refinement proof.

Cross-lab dependencies

  • This lab has no upstream dependencies. It is the bedrock for the distributed track.
  • db-17 Raft consumes the simulator: leader-election scenarios and log-replication invariants will be expressed as scripted event sequences run against a deterministic transport built on top of db-16.
  • db-18 Paxos, db-19 ZAB, db-20 distributed-kv reuse the same vocabulary (Lamport/VC for causality assertions, deterministic scheduler for fault-injection replay).