Time, clocks and ordering

On a single computer, time seems simple. Events happen one after another, a clock tells you when, and if event x has an earlier timestamp than event y, x happened first. In a distributed system every one of those assumptions breaks. Each machine has its own clock, and no two clocks agree exactly. Messages take an unknown time to arrive, so a node cannot tell how old the information it receives is. Without a shared clock there is not even an obvious meaning to saying that an event on one machine happened before an event on another. This lesson builds the tools that replace a global clock: physical clock synchronization, which narrows but never removes the disagreement, and logical clocks, which capture what matters for correctness, namely which events could have influenced which.

Ordering matters everywhere in Ledgerline. If a refund is recorded before the payment it refunds, the account goes briefly negative and a fraud rule may fire. If two replicas apply the same two updates in different orders, they end up with different data. If an audit log orders events by machine timestamps from skewed clocks, investigators may conclude that an approval came after the transfer it authorized. Each of these is an ordering bug, and each has a different correct fix.

Physical clocks and their limits

Computers keep time with a quartz crystal oscillator. Quartz is stable but not perfect: typical server oscillators drift by tens of parts per million, depending on temperature and manufacture. A drift of 20 parts per million is 1.7 seconds a day. Two machines whose clocks start together can therefore disagree by seconds after a few days if nothing corrects them. The difference between two clocks at a given moment is called skew or offset; the rate at which it changes is drift.

Clocks are corrected by synchronizing them with a more accurate source. The Network Time Protocol (NTP), designed by David Mills in the 1980s and still universal, organizes servers in strata: stratum 0 is a reference clock such as a GPS receiver or atomic clock, stratum 1 servers are attached to one, stratum 2 servers synchronize with stratum 1, and so on. Over the public internet NTP typically keeps clocks within a few milliseconds to tens of milliseconds of true time; within a well-run data center it can do better. The Precision Time Protocol (PTP, IEEE 1588), using hardware timestamping in network cards and switches, achieves sub-microsecond agreement and is used in financial trading and telecommunications.

The basic idea behind synchronization is Cristian's algorithm, published by Flaviu Cristian in 1989. A client sends a request at its local time \(t_0\), the server replies with its current time \(T\), and the client receives the reply at \(t_1\). The reply is somewhere between \(t_0\) and \(t_1\) old, so the client estimates the server's current time as \(T + (t_1 - t_0)/2\). If the delays in the two directions are unknown, the error of this estimate is at most half the round-trip time. Taking several samples and keeping the one with the shortest round trip tightens the bound.

# Cristian's algorithm: estimate a server's clock from one request-reply round trip.
import random
random.seed(450)
TRUE_OFFSET = 0.0472          # the client's clock is 47.2 ms behind the server (unknown to it)

def probe():
    # one-way delays are random and need not be symmetric
    d1, d2 = random.uniform(5, 40) / 1000, random.uniform(5, 40) / 1000
    t0 = 100.0                                 # client clock when the request leaves
    server_time = t0 + TRUE_OFFSET + d1        # server clock when it stamps the reply
    t1 = t0 + d1 + d2                          # client clock when the reply arrives
    rtt = t1 - t0
    estimate = server_time + rtt / 2           # assume the reply took half the round trip
    error = estimate - (t1 + TRUE_OFFSET)      # true server time at t1 is t1 + offset
    return rtt, error

samples = [probe() for _ in range(8)]
for rtt, err in samples:
    print(f"round trip {rtt * 1000:5.1f} ms   estimate error {err * 1000:+6.1f} ms   bound +/-{rtt * 500:4.1f} ms")
best = min(samples)                            # keep the sample with the shortest round trip
print(f"best sample: round trip {best[0] * 1000:.1f} ms, error {best[1] * 1000:+.1f} ms")

round trip  46.5 ms   estimate error  -14.9 ms   bound +/-23.3 ms
round trip  44.4 ms   estimate error  +12.1 ms   bound +/-22.2 ms
round trip  77.9 ms   estimate error   -0.4 ms   bound +/-39.0 ms
round trip  64.9 ms   estimate error   -6.9 ms   bound +/-32.5 ms
round trip  43.1 ms   estimate error   +8.0 ms   bound +/-21.5 ms
round trip  55.6 ms   estimate error   +2.4 ms   bound +/-27.8 ms
round trip  24.6 ms   estimate error   -4.2 ms   bound +/-12.3 ms
round trip  44.7 ms   estimate error   +7.9 ms   bound +/-22.4 ms
best sample: round trip 24.6 ms, error -4.2 ms

The Berkeley algorithm, from the Berkeley Unix project in 1989, takes a different approach suitable when no node has an accurate source: a coordinator polls all machines, averages their clocks (discarding outliers) and tells each one how much to adjust. The goal there is internal agreement rather than agreement with true time.

Clock corrections bring their own hazards. If a clock is ahead and is simply set back, local time jumps backwards, and a program that measures elapsed time by subtracting two readings can get a negative duration. Operating systems therefore offer two clocks. The wall clock (time of day, such as CLOCK_REALTIME on Linux) can jump. The monotonic clock (CLOCK_MONOTONIC) never goes backwards and is the right one for timeouts and durations, though its value means nothing on another machine. Leap seconds have caused real outages when software mishandled a minute with 61 seconds; large operators now smear the extra second over many hours instead, and in 2022 the General Conference on Weights and Measures decided to stop adding leap seconds by 2035.

The consequence for system design is a rule worth memorizing: never use timestamps from different machines' clocks to decide the order of events when correctness depends on that order. A common bug is last-writer-wins conflict resolution, where each write carries the writer's wall-clock time and the replica keeps the write with the larger timestamp. If one writer's clock runs fast, its writes win even when they were made earlier, and later writes from other machines are silently discarded.

Happened-before

Leslie Lamport's 1978 paper Time, Clocks, and the Ordering of Events in a Distributed System replaced the question "which event happened first in real time?" with one a system can actually answer: "could one event have influenced the other?" He defined the happened-before relation, written \(a \to b\), as the smallest relation satisfying three rules. If a and b are events in the same process and a comes first, then \(a \to b\). If a is the sending of a message and b is its receipt, then \(a \to b\). And if \(a \to b\) and \(b \to c\), then \(a \to c\). Two events where neither happened before the other are concurrent, written \(a \parallel b\). Concurrent does not mean simultaneous; it means that no chain of messages connects them, so neither could have affected the other.

Happened-before is the right notion of order for most correctness questions. If a refund was issued by a clerk who had seen the payment, then the payment happened before the refund, and every replica must apply them in that order. If two clerks independently edited an invoice without seeing each other's edits, the edits are concurrent and the system must either merge them or ask someone to choose; there is no fact of the matter about which came first.

Lamport clocks

A Lamport clock gives every event a number consistent with happened-before. Each process keeps a counter. Before each event it increments the counter. When it sends a message, it attaches the counter's value. When it receives a message with timestamp \(t\), it sets its counter to \(\max(\text{counter}, t)\) and then increments. The resulting timestamps satisfy the clock condition: if \(a \to b\) then \(L(a) < L(b)\). Ties between processes can be broken by process identifier, giving a total order consistent with causality, which Lamport used to implement distributed mutual exclusion and which underlies many replicated state machines.

The converse does not hold. \(L(a) < L(b)\) does not imply \(a \to b\); the events may be concurrent. Lamport clocks therefore order events safely but cannot detect concurrency. For that we need more information.

Vector clocks

Vector clocks, developed independently by Colin Fidge and Friedemann Mattern in 1988, record not one counter but one per process. Process \(i\) keeps a vector \(V_i\) of length \(n\). Before each event it increments \(V_i[i]\). It attaches its whole vector to every message. On receipt it sets each entry to the maximum of its own and the message's entry, then increments its own entry. Entry \(V_i[j]\) is the number of events at process \(j\) that process \(i\) knows about, directly or through chains of messages.

Vectors are compared entry by entry. \(V \le W\) if every entry of V is at most the corresponding entry of W; \(V < W\) if \(V \le W\) and they differ. The key theorem is that vector clocks characterize happened-before exactly: \(a \to b\) if and only if \(V(a) < V(b)\), and a and b are concurrent if and only if neither vector is less than the other. The program below runs both clocks on the same trace as the figure and uses the vectors to classify pairs of events.

# Lamport clocks and vector clocks on the same message trace, with happened-before checks.
# Events: ("local", p) | ("send", p, msg) | ("recv", p, msg)
TRACE = [
    ("local", "A"), ("send", "A", "m1"), ("local", "B"), ("recv", "B", "m1"),
    ("send", "B", "m2"), ("local", "C"), ("send", "C", "m3"), ("recv", "A", "m3"),
    ("recv", "C", "m2"), ("local", "A"),
]
PROCS = ["A", "B", "C"]
lam = {p: 0 for p in PROCS}
vec = {p: [0, 0, 0] for p in PROCS}
in_flight = {}
events = []                                   # (name, lamport, vector)
count = {p: 0 for p in PROCS}
for ev in TRACE:
    kind, p = ev[0], ev[1]
    i = PROCS.index(p)
    if kind == "recv":
        ml, mv = in_flight.pop(ev[2])
        lam[p] = max(lam[p], ml)              # Lamport: take the max, then tick
        vec[p] = [max(a, b) for a, b in zip(vec[p], mv)]   # vector: element-wise max
    lam[p] += 1
    vec[p][i] += 1
    if kind == "send":
        in_flight[ev[2]] = (lam[p], vec[p][:])
    count[p] += 1
    name = f"{p}{count[p]}"
    events.append((name, lam[p], vec[p][:], kind + (" " + ev[2] if len(ev) > 2 else "")))
    print(f"{name}: {kind:5s} {ev[2] if len(ev) > 2 else '':3s} Lamport {lam[p]}  vector {vec[p]}")

def hb(v, w):                                 # v happened before w
    return all(a <= b for a, b in zip(v, w)) and v != w

E = {n: (l, v) for n, l, v, _ in events}
for a, b in [("A1", "C3"), ("C1", "A3"), ("B1", "C2"), ("C2", "B3"), ("B3", "A4")]:
    (la, va), (lb, vb) = E[a], E[b]
    rel = "->" if hb(va, vb) else ("<-" if hb(vb, va) else "||")
    print(f"{a} vs {b}: Lamport {la} vs {lb}; vectors say {a} {rel} {b}")

A1: local     Lamport 1  vector [1, 0, 0]
A2: send  m1  Lamport 2  vector [2, 0, 0]
B1: local     Lamport 1  vector [0, 1, 0]
B2: recv  m1  Lamport 3  vector [2, 2, 0]
B3: send  m2  Lamport 4  vector [2, 3, 0]
C1: local     Lamport 1  vector [0, 0, 1]
C2: send  m3  Lamport 2  vector [0, 0, 2]
A3: recv  m3  Lamport 3  vector [3, 0, 2]
C3: recv  m2  Lamport 5  vector [2, 3, 3]
A4: local     Lamport 4  vector [4, 0, 2]
A1 vs C3: Lamport 1 vs 5; vectors say A1 -> C3
C1 vs A3: Lamport 1 vs 3; vectors say C1 -> A3
B1 vs C2: Lamport 1 vs 2; vectors say B1 || C2
C2 vs B3: Lamport 2 vs 4; vectors say C2 || B3
B3 vs A4: Lamport 4 vs 4; vectors say B3 || A4

Compare C2 and B3. Their Lamport timestamps are 2 and 4, which suggests that C2 came first, but the vectors [0, 0, 2] and [2, 3, 0] show that neither could have influenced the other: they are concurrent. B3 and A4 even share the Lamport timestamp 4 and are also concurrent. By contrast C1 and A3 are genuinely ordered, through C2 and message m3, and A1 happened before C3 through the chain m1, m2. Only the vector comparison distinguishes these cases with certainty. Vector clocks are used in practice to detect conflicting updates in replicated stores. Amazon's Dynamo (2007) attached a vector clock to each version of an object; when a read found versions with concurrent vectors, it returned all of them to the application to reconcile. Their cost is size: a vector has one entry per process, which is awkward when thousands of clients write. Practical systems use variants such as dotted version vectors, or keep entries only for replicas rather than clients.

Hybrid logical clocks

Logical clocks capture causality but their values bear no relation to real time, which makes them hard to use for queries such as "what was the balance at 3 p.m.?". Physical clocks relate to real time but violate causality when they are skewed. Hybrid logical clocks (HLC), introduced by Kulkarni, Demirbas and colleagues in 2014, combine the two. Each timestamp is a pair: the largest physical time the node has heard of, and a small counter that breaks ties and preserves causality when physical clocks lag. HLC timestamps fit in 64 bits, stay within the clock-synchronization error of real time, and satisfy the clock condition. CockroachDB and MongoDB use them for transaction and replication ordering.

# Hybrid logical clocks (Kulkarni et al. 2014): physical time plus a logical counter.
# Timestamps stay close to real time but still respect causality when clocks are skewed.
class HLC:
    def __init__(self, name):
        self.name, self.l, self.c = name, 0, 0
    def now(self, pt):                        # local or send event at physical time pt
        if pt > self.l:
            self.l, self.c = pt, 0
        else:
            self.c += 1
        return (self.l, self.c)
    def recv(self, pt, msg):
        ml, mc = msg
        new_l = max(self.l, ml, pt)
        if new_l == self.l == ml:
            self.c = max(self.c, mc) + 1
        elif new_l == self.l:
            self.c += 1
        elif new_l == ml:
            self.c = mc + 1
        else:
            self.c = 0
        self.l = new_l
        return (self.l, self.c)

a, b = HLC("A"), HLC("B")
# A's clock runs 30 ms fast relative to B's. Physical readings (ms):
m = a.now(1030)                  # A sends at its local 1030
print("A sends   ", m)
r = b.recv(1005, m)              # B receives when its own clock reads only 1005
print("B receives", r, "(still after the send, though B's clock is behind)")
print("B local   ", b.now(1006))
print("B local   ", b.now(1040), "(physical time has caught up; counter resets)")

A sends    (1030, 0)
B receives (1030, 1) (still after the send, though B's clock is behind)
B local    (1030, 2)
B local    (1040, 0) (physical time has caught up; counter resets)

TrueTime: making uncertainty explicit

Google's Spanner database, described in 2012, took a different approach: instead of pretending clocks are exact, it measures how inexact they are. Its TrueTime interface returns not a timestamp but an interval \([\text{earliest}, \text{latest}]\) guaranteed to contain the true time. Google keeps the interval narrow, typically a few milliseconds, with GPS receivers and atomic clocks in every data center. Spanner then uses commit wait: when a transaction commits with timestamp \(s\), the system waits until TrueTime guarantees that \(s\) is in the past everywhere before making the commit visible. Any transaction that starts afterwards must receive a larger timestamp, so timestamp order agrees with real-time order. The price is a wait of roughly the uncertainty on every commit, which is why Google invests in tight clock synchronization. Amazon later offered a similar service, the Amazon Time Sync Service with clock-bound information, and open-source systems such as CockroachDB use an analogous maximum-offset setting, refusing to run if clocks drift too far apart.

Total order and why it matters

Many distributed algorithms need every node to process the same events in the same order: if every replica of Ledgerline's ledger applies the same commands in the same order, starting from the same state, every replica ends in the same state. This is the state machine replication approach, and it reduces replication to agreeing on an order. Lamport timestamps with process identifiers as tie-breakers give one such order, but only after a node has heard from every other node, so that it knows no smaller timestamp is still on its way. That requirement makes the approach fragile when nodes fail, because one silent node stops everyone. Lessons 8 and 9 show how consensus protocols agree on a total order while tolerating failures.

Worked examples