Distributed Systems · Cluster
Time and Ordering
Clocks, causality, and happens-before.
- 01 Wall-Clock Timestamps Do Not Order Distributed Events Why two machines reading the same instant produce different numbers, how far the disagreement grows between synchronizations, and what an interval-bounded timestamp can still support.
- 02 Happens-Before and the Scalar Logical Clock How Lamport replaced physical time with a partial order defined by message passing, why one integer per process suffices for that order, and what the integer provably cannot tell you.
- 03 Vector Clocks and the Detection of Concurrency Why one counter per process turns the happens-before relation into a comparison, how the merge rule is defined, and the per-message size that makes the scheme expensive at scale.
- 04 Interval Tree Clocks and Membership Change How a tree-shaped stamp splits and joins without renumbering every process, why vector clocks break when the participant set changes, and what the fork and join operations cost.
- 05 The NTP Four-Timestamp Exchange and Its Asymmetry Limit How four timestamps yield an offset estimate, why the estimate is only as good as the path symmetry, and how the protocol decides which of several servers to believe.
- 06 Monotonic and Civil Clocks in Running Programs Why interval measurement needs a clock that never goes backwards, how leap seconds and suspend break civil time, and which timeout a kernel or runtime actually uses.
- 07 Hybrid Logical Clocks: Physical Time With a Logical Counter How HLC timestamps stay close to wall-clock time while preserving causality, why the counter only appears inside the uncertainty window, and what a bounded timestamp costs.
- 08 Consistent Cuts and the Marker Algorithm for Global Snapshots Why a set of per-process snapshots taken at different moments is usually inconsistent, and how markers travelling on the same channels as messages capture a cut that could have occurred.
- 09 Total-Order Broadcast: One Order for Every Replica Why a single sequencer turns concurrent updates into a deterministic log, what the ordering guarantee costs in latency and availability, and how the order survives a sequencer failure.
- 10 Bounded Clock Uncertainty and the Commit-Wait Rule How a clock that returns an interval instead of an instant lets a system order transactions by physical time, why reads must wait out the uncertainty, and what the wait costs.