Time and Clocks

Distributed systems lack a global clock—timestamps on two nodes cannot be directly compared. From Lamport logical clocks (happens-before) to vector clocks (concurrency detection) to TrueTime (GPS + atomic clocks), each type of "clock" approaches the seemingly simple problem of "event ordering" at different cost points.

Problem: No Global Clock

On a single machine, gettimeofday() can compare the order of two events A and B. But in a distributed system, if A occurs on node 1 at 12:00:00.000 and B occurs on node 2 at 12:00:00.001—can you determine that A happened first? No, because the clocks of the two nodes cannot be perfectly synchronized. NTP synchronization accuracy is ~1ms, meaning the order of events within 1ms cannot be determined by physical time.

Lamport Logical Clock (1978)

Leslie Lamport's insight: We don't need physical time to determine causality—we only need to ensure that the happens-before relationship is reflected in timestamps.

Algorithm

Each node maintains an integer counter C, initialized to 0:

1. A local event occurs (including sending a message): C = C + 1, the timestamp of the event = C
2. When sending a message, attach the node's current C
3. Upon receiving a message (timestamp = C_msg): C = max(C, C_msg) + 1, the timestamp of the receive event = C

Property: If a happens-before b, then C(a) < C(b). However, the converse is not true—C(a) < C(b) does not imply a → b (they might be concurrent events that just happened to have different counter values).

Distributed Mutual Exclusion Algorithm (Lamport Mutex)

Implement mutual exclusion without a central node using logical clocks:

1. Node i wants to enter the critical section: sends REQUEST(ts_i, i) to all nodes
2. Node j receiving the request: if not in the critical section and not intending to enter, replies with REPLY If in the critical section or intending to enter and its own request has higher priority (ts_j < ts_i) → delays the reply
3. Node i, after receiving REPLY from all nodes → enters the critical section
4. Exiting the critical section → sends RELEASE to all nodes

Advantages: No single point of failure, fully distributed. Disadvantages: 3(N-1) messages, and a single node failure will block the entire system.

Vector Clock

Limitation of Lamport clocks: C(a) < C(b) cannot be reversed to deduce a → b. Vector clocks solve this problem.

Data Structure

Each node maintains a vector V[1..N] of length N, where V[i] = the number of events the node knows have occurred on node i.

V_a = [3, 5, 2]  means: Node 1 knows: 3 events on itself, 5 on Node 2, 2 on Node 3

Algorithm

1. An event occurs on local node i: V[i] = V[i] + 1
2. When sending a message, attach the current V
3. Upon receiving a message (with attached V_msg): V[k] = max(V[k], V_msg[k]) for all k, then V[i] = V[i] + 1

Comparison Rules

• V(a) < V(b) (a happens-before b): Every element in V(a) is ≤ the corresponding element in V(b), and at least one is strictly less
• V(a) and V(b) are incomparable: There exist k, j such that V(a)[k] < V(b)[k] and V(a)[j] > V(b)[j] → concurrent events

Practical Application

Dynamo/Riak KV uses vector clocks to detect conflicts: when get(key) returns vector clock V_old, the client modifies it and calls put(key, value, V_old). If the current version on the server is V_cur, compare V_cur with V_old:

• V_cur < V_old: Overwrite directly (the client saw the current version before modifying)
• V_cur > V_old: Reject (the client modified based on an outdated version) → requires read-modify-write
• Incomparable: Concurrent modifications → requires conflict resolution (application-level merge or keeping multiple sibling versions)

Google TrueTime (Spanner)

The most extreme industrial practice: using atomic clocks + GPS to provide bounded clock uncertainty intervals for global data centers.

TT.now() returns interval [earliest, latest]

Guarantee: The real time must fall within this interval. The interval width is typically ~1-7ms (depending on GPS/atomic clock synchronization status).

Spanner's External Consistency

Spanner transactions use TrueTime to guarantee the strongest external consistency (stronger than linearizability—real-time ordering across data centers):

commit wait: The transaction's commit timestamp = TT.now().latest
              Before the transaction takes effect on replicas, wait for TT.after(commit_ts) = True
              → Ensures all nodes see the commit order consistent with real time

Why Hardware is Needed

Software cannot provide clocks with bounded error—NTP can only estimate error, but asymmetric network latency and jitter make the error bounds unknown. TrueTime's guarantee comes from the physical properties of GPS/atomic clocks: atomic clock frequency error < 10^-13.

NTP/PTP Practices

NTP (Network Time Protocol): Estimates time deviation from the server by exchanging UDP packets. Accuracy is ~1ms (LAN), ~10ms (WAN). Issues:

• Step changes: NTP suddenly corrects large deviations → clock jumps backward → CLOCK_MONOTONIC exposes this jump, but wall-clock time goes backward
• Oscillation: NTP continuously corrects → clock frequency undergoes continuous tiny changes → Prometheus TSDB, which relies on monotonic time, may be affected (though Prometheus uses CLOCK_MONOTONIC for scrape timing)
• Synchronization failure: NTP server unreachable → clock drift accumulates → error can reach seconds after hours/days

PTP (Precision Time Protocol, IEEE 1588): Data center-level time synchronization with accuracy ~100ns. Requires hardware support (NIC timestamping). Used for financial trading (MiFID II compliance) and as an alternative clock source for Spanner.

References

• Paper: "Time, Clocks, and the Ordering of Events in a Distributed System" (Lamport, 1978)
• Paper: "Spanner: Google's Globally-Distributed Database" (2012, TrueTime section)
• Paper: "Virtual Time and Global States of Distributed Systems" (Mattern, 1989 — vector clocks)

Keywords: Lamport clock, vector clock, happens-before, TrueTime, Spanner, NTP, PTP, logical time