Advanced Distributed Systems #clocks #Lamport #vector-clocks #TrueTime

Distributed Clocks

5 exercises — master distributed clock vocabulary: why wall clocks fail for ordering, Lamport timestamps and their limits, vector clock causality detection, Hybrid Logical Clocks (HLC) in CockroachDB and YugabyteDB, and Google Spanner's TrueTime with commit wait.

0 / 5 completed

Distributed clock quick reference

Wall clocks (NTP) — ±1-100ms typical uncertainty; clock drift between syncs; leap second issues; do NOT use for event ordering.
Happens-before (→) — A→B means A causally precedes B; captured by logical clocks.
Lamport timestamp — counter incremented before each event; on receive: max(local, received)+1. If A→B then L(A) < L(B). Reverse NOT guaranteed — cannot detect concurrency.
Vector clock — vector of counters (one per node). Can detect concurrent events: incomparable vectors = concurrent. O(n) space cost.
HLC — (physical_time, logical_counter). Stays within ε of NTP; Lamport-style causal ordering. Used in CockroachDB, YugabyteDB.
TrueTime (Spanner) — GPS + atomic clocks; returns interval [earliest, latest]; ε ≈ 7ms.
Commit wait — Spanner waits until TT.now().earliest > commit_timestamp before acknowledging; ensures external consistency.

1 / 5

A junior engineer asks: "Why can't we just use the system timestamp (Date.now()) on each server to determine the order of events in a distributed system?"

Wall clock synchronisation limitations make timestamps unsuitable for strict event ordering in distributed systems.

Sources of clock inaccuracy:
• NTP synchronisation error — typical LAN: ±1-5ms. WAN: ±50-100ms. GPS-disciplined: ±1μs but expensive
• Clock drift — quartz oscillators drift ~1-10ms/day between NTP syncs. A 30-second sync interval at 10ms/day = ~350μs/interval drift
• Leap seconds — UTC adds a second when Earth's rotation slows; OS handling varies: clock freeze (Linux historical), smear (Google), jump; all cause problems
• VM clock skew — VM clocks are emulated; during host overload or live migration, guest clocks may fall behind by seconds
• Network jitter — NTP corrections themselves are imprecise because the correction is based on round-trip time divided by 2, assuming symmetric latency

The Einstein insight for distributed systems:
In special relativity, there is no universal "now" for observers in different locations. Similarly, in a distributed system, there is no globally agreed "current time" — only message ordering relationships. Leslie Lamport formalised this insight into the happens-before relationship (1978), which forms the basis for logical clocks.

What you CAN use timestamps for (with caveats):
• Approximate ordering when events are seconds apart and precision doesn't matter
• Human-readable audit logs (not as ordering keys)
• TTL expiration (bounded accuracy acceptable)
• TrueTime (Spanner) — bounded uncertainty makes causal ordering possible, but requires GPS + atomic clocks

Key vocabulary:
• NTP (Network Time Protocol) — protocol for synchronising computer clocks over a network; typical accuracy ±1-100ms depending on network quality
• Clock drift — the gradual divergence of a clock from true time between synchronisation rounds; caused by oscillator imprecision
• Clock skew — the difference in clock readings between two nodes at any given moment
• Leap second — an occasional 1-second addition to UTC to account for Earth's variable rotation; can disrupt software expecting monotonic time
• Happens-before (→) — a partial order relationship between events in a distributed system: A→B means A causally precedes B

2 / 5

An interviewer asks: "Explain Lamport timestamps. How do they work, and what problem do they solve — and not solve?"

Lamport timestamps (1978) — the foundational logical clock algorithm: a simple mechanism that captures causal order without physical time.

The algorithm:

# Each process maintains a counter C, initialised to 0

# On internal event at process P:
C[P] = C[P] + 1

# On send event at process P:
C[P] = C[P] + 1
message.timestamp = C[P]
send(message)

# On receive event at process P, receiving message M:
C[P] = max(C[P], M.timestamp) + 1
# Process M

What this guarantees:
If A happens-before B (A→B), then L(A) < L(B).

What this does NOT guarantee:
If L(A) < L(B), we cannot conclude A→B. A and B may be concurrent events.
Example: Node 1 sends message at L=5. Node 2 increments to L=6 for an internal event before receiving the message. L(internal)=6 > L(msg)=5, but internal event is concurrent with the send event.

Lamport timestamps provide a total order, not causal order:
You can always break ties (e.g., by process ID) to get a total order — useful for distributed state machines, event logs, and linearisation. But that total order does not necessarily reflect causality.

Classic use cases:
• Mutual exclusion algorithms (Lamport's mutex)
• Event logging where total order is needed (but causality isn't critical)
• Foundation for understanding vector clocks (the successor)

Interview depth signals:
• Mentioning "happens-before" relationship specifically
• Noting that implication is one-directional (→ implies <, not < implies →)
• Explaining that concurrent events may have any relative Lamport timestamp ordering
• Connecting to vector clocks as the solution for concurrent event detection

Key vocabulary:
• Lamport timestamp — a logical clock counter associated with each event; incremented on each event and on message receipt
• Happens-before (→) — if A→B, then L(A) < L(B); the causal precedence relationship Lamport timestamps capture
• Concurrent events — events with no causal relationship; neither A→B nor B→A; Lamport timestamps cannot distinguish these from causally-ordered events
• Logical clock — a counter that tracks causal ordering without physical time; advances via event increments and max-merges on message receipt

3 / 5

A system design interview question: "Amazon's Dynamo (and Riak) used vector clocks to resolve conflicts. How do vector clocks improve on Lamport timestamps, and what are their trade-offs?"

Vector clocks solve the fundamental limitation of Lamport timestamps: they can detect concurrent events where Lamport timestamps cannot.

Vector clock algorithm (3-node example: N1, N2, N3):

# Each node P maintains vector VC[P] = [0, 0, ..., 0] (one slot per node)

# On internal event at node P:
VC[P][P] = VC[P][P] + 1

# On send at node P:
VC[P][P] = VC[P][P] + 1
message.vc = copy(VC[P])
send(message)

# On receive at node P from message M:
for each i: VC[P][i] = max(VC[P][i], M.vc[i])
VC[P][P] = VC[P][P] + 1

Ordering rules for two vector clocks V1 and V2:
• V1 = V2: identical events
• V1 < V2 (V1 causally precedes): ∀i, V1[i] ≤ V2[i] AND ∃j, V1[j] < V2[j]
• V1 > V2 (V2 causally precedes): symmetric
• V1 ∥ V2 (concurrent): neither V1 < V2 nor V2 < V1 — concurrent events

Example — conflict detection in Dynamo:

# User writes "item: book" to replica R1, causing: V=[1,0,0]
# User writes "item: pen" to replica R2 (concurrent), causing: V=[0,1,0]
# R1 and R2 cannot merge automatically — concurrent writes
# System returns both versions to client (the "siblings" in Riak)
# Client (or application) resolves the conflict

Trade-offs of vector clocks:
• Space: O(n) per event for n nodes — problematic for large clusters. A 1000-node cluster means a vector of 1000 counters per message
• Garbage collection needed — clients that generate vector clocks (Dynamo's "client VC" variant) cause unbounded growth; requires periodic pruning
• Conflict resolution still required — vector clocks detect concurrency, but you still need application logic or CRDTs to merge concurrent versions

Where vector clocks are used:
• Amazon Dynamo (shopping cart: concurrent writes = siblings, all shown to user)
• Riak (version vectors, a more practical variant avoiding orphaned vector entries)
• Git (DAG of commits captures same information as vector clock; merge conflicts require human resolution)

Key vocabulary:
• Vector clock — a vector of logical counters (one per node) tracking causal dependency and detecting concurrent events
• Version vector — a variant of vector clock tracking object versions rather than events; used in Riak and Voldemort
• Concurrent events (∥) — two events where neither causally precedes the other; detected by incomparable vector clocks
• Sibling — Riak's term for concurrent conflicting values that need resolution
• Conflict resolution — mechanism to merge concurrent versions; may be LWW (last-write-wins), CRDT, or application-level logic

4 / 5

An interviewer asks: "CockroachDB and YugabyteDB use Hybrid Logical Clocks (HLC). What problem does HLC solve that neither Lamport timestamps nor vector clocks address?"

HLC (Hybrid Logical Clock, Kulkarni et al. 2014) bridges the gap between pure logical clocks and physical time — used in distributed databases that need both causal ordering and time-based queries.

HLC structure:
Each HLC timestamp has two components: (pt, lc) — physical time component (wall clock, millisecond granularity) and logical counter (incremented for same-ms events).

HLC algorithm:

# On event at node P (send or internal):
l' = max(pt[P], NTP.now())  
if l' == pt[P]:
    lc[P]++
else:
    pt[P] = l'; lc[P] = 0

# On receive at node P of message with (pt_m, lc_m):
l' = max(pt[P], pt_m, NTP.now())
if l' == pt[P] == pt_m:
    lc[P] = max(lc[P], lc_m) + 1
elif l' == pt[P]:
    lc[P]++
elif l' == pt_m:
    lc[P] = lc_m + 1
else:
    lc[P] = 0
pt[P] = l'

HLC guarantees:
• Causal order — if A→B (A causally precedes B), then HLC(A) < HLC(B); same as Lamport clock
• Bounded deviation — HLC is always within ε of NTP wall clock time. Most implementations: ε = 500ms. CockroachDB aborts transactions with clock skew > 500ms by default
• Monotonically increasing — HLC never goes backward, unlike NTP which can step backward after correction

Why this makes distributed databases practical:
• You can write time-bounded queries: "all transactions between 14:00 and 14:05" — meaningful because HLC is close to real time
• Human-readable audit logs: event times correspond to wall clock time
• Build on top of existing infrastructure: just needs NTP (not GPS + atomic clocks like Spanner)
• CockroachDB uses HLC for MVCC (Multi-Version Concurrency Control) timestamps across nodes

HLC vs Spanner TrueTime:

Property	HLC	TrueTime
Hardware required	Standard NTP	GPS + atomic clocks
Uncertainty bound	~500ms (configurable)	~7ms
Commit wait latency	None (no commit wait)	7-14ms commit wait
Infrastructure	Any cloud/on-prem	Google-only

Key vocabulary:
• Hybrid Logical Clock (HLC) — a timestamp combining a physical time component (close to NTP) and a logical counter (for same-ms ties); provides causal ordering within bounded wall-clock deviation
• Physical component (pt) — the wall-clock portion of HLC; stays within ε of NTP time
• Logical counter (lc) — incremented when pt doesn't advance; ensures strict ordering within the same millisecond
• Clock skew tolerance — the maximum allowed difference between node clocks; CockroachDB default 500ms; transactions exceeding this are aborted

5 / 5

A senior interviewer asks: "Google Spanner achieves global external consistency using TrueTime. Explain how TrueTime works and why the commit wait mechanism is necessary."

TrueTime is the core innovation in Google Spanner that makes globally-distributed external consistency practical.

TrueTime architecture:
• GPS receivers and atomic clocks colocated with servers in every Google data centre
• Time master servers in each DC, slaved to GPS/atomic clock reference
• TrueTime API: TT.now() returns interval [earliest, latest]; TT.after(t) is true when t is definitely past; TT.before(t) is true when t is definitely in the future
• Typical interval width ε: 1-7ms (goal: under 10ms)

Why an interval rather than a timestamp?
Even with GPS, there is irreducible uncertainty: message transmission time, oscillator drift between synchronisation cycles. TrueTime explicitly exposes this uncertainty via an interval, rather than hiding it and pretending clocks are perfect.

The commit wait protocol:

# Transaction T1 commits:
1. Coordinator runs Paxos across replicas → T1 is durable
2. Assign commit timestamp s1 = TT.now().latest  ← latest possible "now"
3. COMMIT WAIT: wait until TT.now().earliest > s1
   (wait until true time has definitely passed s1)
4. Acknowledge commit to client

# Why this ensures external consistency:
# If T2 starts after T1's commit acknowledgement,
# then TT.now().earliest > s1 when T2 acquires its timestamp
# → s2 > s1 → T2 reads a snapshot that includes T1's writes

Why commit wait duration = ε (the interval width):
The wait lasts from when s1 was assigned (TT.now().latest) until TT.now().earliest > s1. Since latest - earliest = 2ε, the wait is approximately 2ε — for typical 7ms intervals, commit wait ≈ 7-14ms.

What external consistency means:
External consistency is strictly stronger than serializable isolation: if transaction T1 commits (acknowledgement returned to client) before transaction T2 begins, then T1's timestamp is less than T2's timestamp. This is the property Spanner guarantees across globally distributed shards, which is remarkable since standard distributed databases only guarantee serializability within a single shard.

Spanner without TrueTime (why not NTP)?
NTP's uncertainty window with standard hardware is ±100ms. A commit wait of 100ms for every transaction is untenable for production workloads. TrueTime's ε of ~7ms makes the 7-14ms commit wait acceptable for most financial and enterprise workloads. This is why Spanner requires specialised hardware.

Key vocabulary:
• TrueTime — Google's GPS + atomic clock infrastructure that exposes time as a bounded interval [earliest, latest], making clock uncertainty explicit
• TT.now() — TrueTime API returning a time interval; the true current time is guaranteed inside this interval
• Commit wait — delay after Paxos commit before acknowledging to client; waits until TrueTime confirms the commit timestamp is definitely in the past everywhere
• External consistency — if T1 commits before T2 starts (real time), then T1's commit timestamp precedes T2's; equivalent to strict serializability across distributed shards
• ε (epsilon) — TrueTime interval half-width; the maximum clock uncertainty; typically 1-7ms with GPS/atomic-clock infrastructure