Time Is an Illusion: Logical Clocks in Distributed Systems

In a distributed system, there is no global clock. This single fact has more consequences than most engineers appreciate.

The Problem

Two servers, A and B. Server A writes x = 1 at time $t_1$. Server B writes x = 2 at time $t_2$. Which write came first?

If $t_1 < t_2$, A was first — right? Wrong. Wall clocks drift. NTP corrections can make time go backwards. You cannot use physical time to establish causality.

Lamport Timestamps

Leslie Lamport's 1978 insight: we don't need physical time. We need a logical clock that respects causality.

Rules:

1. Before each event, increment the counter: $C_i = C_i + 1$
2. When sending a message, include the timestamp
3. On receiving a message with timestamp $t$: $C_j = \max(C_j, t) + 1$

This gives us: if $a \to b$ (a causally precedes b), then $L(a) < L(b)$.

But not the converse: $L(a) < L(b)$ does not imply $a \to b$. Events may be concurrent.

Vector Clocks

To detect concurrency, we need vector clocks. Each process $i$ maintains a vector $VC_i[1..n]$:

$$VC_i[j] = \text{number of events at } j \text{ that causally precede } i\text{'s current state}$$

Now we can determine:

• $a \to b$ iff $VC(a) < VC(b)$ (componentwise)
• $a \| b$ (concurrent) iff neither $VC(a) \leq VC(b)$ nor $VC(b) \leq VC(a)$

class VectorClock:
    def __init__(self, n: int, pid: int):
        self.clock = [0] * n
        self.pid = pid

    def tick(self):
        self.clock[self.pid] += 1

    def send(self) -> list[int]:
        self.tick()
        return self.clock.copy()

    def receive(self, other: list[int]):
        for i in range(len(self.clock)):
            self.clock[i] = max(self.clock[i], other[i])
        self.tick()

The tradeoff: vector clocks have $O(n)$ space per event, where $n$ is the number of processes. For large systems, this is prohibitive.

Hybrid Logical Clocks

HLC combines physical and logical time, giving us the best of both worlds:

$$\text{HLC} = (\text{physical}_{\max}, \text{logical})$$

The physical component captures "roughly when" something happened. The logical component breaks ties. This is what CockroachDB uses for MVCC timestamps.

The beauty of HLC: the timestamp is always within a bounded offset of the true physical time, while still providing the causal ordering guarantees of logical clocks.