1.3. Time and Ordering
There is no global “now” in a distributed system. Each node has its own clock, drifting independently, and the network delivers messages with variable delay — so “which event happened first” often has no physically meaningful answer. This chapter builds the machinery that replaces wall-clock intuition: the happened-before relation that defines causality, logical and vector clocks that capture it without physical time, hybrid clocks that bound the gap, and the extreme engineering (Google’s TrueTime) required to make physical time trustworthy at all.
Topics Covered
Section titled “Topics Covered”- 1.3.1. Physical Clocks: Quartz Drift, NTP Limitations, Leap Second Problem: Quantifies quartz drift, NTP synchronization limits, and the leap-second problem that breaks time-dependent code.
- 1.3.2. Monotonic Clocks vs. Time-of-Day: Which One to Use: Explains why measuring elapsed time requires a monotonic clock, never the wall clock that can jump backward.
- 1.3.3. The Happened-Before Relation: Foundation of Causality: Establishes Lamport’s happened-before relation as the rigorous partial order that defines causality without physical time.
- 1.3.4. Lamport Timestamps: Capturing Causality: Introduces logical counters that capture causal ordering across nodes with a single integer per event.
- 1.3.5. Vector Clocks: Detecting Concurrency: Extends logical clocks to detect concurrency: telling whether two events are causally ordered or genuinely parallel.
- 1.3.6. Hybrid Logical Clocks (HLC): Combining Physical and Logical Time: Combines physical and logical time into a single timestamp that stays close to wall-clock while preserving causality.
- 1.3.7. Google TrueTime & Spanner: Working with Uncertainty: Shows how Google’s TrueTime bounds clock uncertainty with atomic clocks and GPS to enable external consistency at global scale.
- 1.3.8. Distributed ID Generation: UUIDv7, Snowflake, ULID: Compares UUIDv7, Snowflake, and ULID for generating sortable, unique identifiers without central coordination.