Skip to content

Logical Clocks — Notes#

Problem#

Across distributed nodes there is no global wall clock; physical clocks drift. We still need to: - Order events causally. - Detect concurrent updates that must be merged. - Provide consistent reads / snapshots.

Lamport's "happens-before" (1978)#

  • a → b if a precedes b in same process, or a is a send and b the matching receive, transitively.
  • a || b (concurrent) if neither happens-before the other.
  • Lamport TS gives total order consistent with → (but loses concurrency info).

Vector clocks#

  • One counter per node.
  • Compares element-wise: ≤ everywhere ⇒ happens-before; some less / some greater ⇒ concurrent.
  • Memory O(N) replicas — fine for small N, not for millions of clients.

HLC = wall ms + logical counter#

  • tick(now): pt = max(pt, now); l = max(l + 1, pt + 1) (simplified).
  • Read as causal but stays within bounded ε of real time → good for OLTP.

TrueTime (Spanner)#

  • API returns [earliest, latest] interval.
  • Commit wait = wait out ε; ε ≈ a few ms with atomic clocks + GPS.

Where this matters in this repo#

  • CRDTs need vector / dotted version vectors.
  • Spanner-style designs (Spanner, CRDB, YugabyteDB) need HLC/TrueTime.
  • Multi-leader replication needs conflict ordering.
  • Distributed tracing uses logical span IDs (causal ordering across services).

Refs#

  • Lamport: "Time, Clocks, and the Ordering of Events" (CACM '78).
  • Mattern: "Virtual Time and Global States of Distributed Systems."
  • Kulkarni et al.: "Logical Physical Clocks" (HLC, 2014).
  • Spanner paper, CockroachDB blog "Living without atomic clocks."