Time, Clocks, and Ordering in Distributed Systems

A distributed system has no shared clock and no shared memory. Each node has its own clock, and messages take an unbounded time to arrive. To decide which of two events happened first, the system needs either synchronized physical clocks with a known error bound, or logical clocks that track causality without measuring time at all.

Problems with physical clocks

• Clock drift. A quartz oscillator runs slightly fast or slow. Two clocks that agree now will differ later. Drift of 10 to 50 parts per million (a typical order of magnitude for quartz oscillators) accumulates to roughly 1 to 4 seconds per day.
• Clock skew. The difference between two clocks at one instant. NTP (Network Time Protocol) periodically corrects the local clock from a reference server. Over a network, the accuracy is usually milliseconds on a LAN and can be tens of milliseconds or worse over the internet.
• Non-monotonic wall clocks. NTP can step the wall clock backwards. Leap seconds can repeat or smear a second. A duration measured as the difference of two wall-clock reads can be negative. Systems measure durations with a monotonic clock (in Java, System.nanoTime(); Instant.now() reads the wall clock), which never goes backwards but is meaningful only within one machine.
• Last-write-wins hazards. If two nodes stamp writes with their wall clocks and the highest timestamp wins, a node with a fast clock overwrites newer data from other nodes, and a write can be silently lost.

Physical time is adequate for timeouts, leases with safety margins, log timestamps, and TTLs. It is not adequate for deciding the order of concurrent updates unless the clock error is bounded and accounted for.

Bounded-error clocks

Google Spanner exposes TrueTime, an API that returns an interval [earliest, latest] guaranteed to contain the true time. The error bound comes from GPS receivers and atomic clocks in data centers. Spanner assigns a commit timestamp and waits until that timestamp is guaranteed to be in the past before making the transaction visible (commit wait). This gives externally consistent transactions at the cost of latency proportional to the clock uncertainty.

Happens-before

Lamport defined the happens-before relation, written a → b, using three rules:

1. If a and b are events on the same process and a occurs before b, then a → b.
2. If a is the sending of a message and b is its receipt, then a → b.
3. If a → b and b → c, then a → c (transitivity).

Two events with neither a → b nor b → a are concurrent. Concurrent means no causal path connects them, not that they occurred at the same instant.

sequenceDiagram
    participant A
    participant B
    participant C
    A->>B: m1 (send is a1, receive is b1)
    B->>C: m2 (send is b2, receive is c1)
    Note over A,C: a1 happens-before c1 by transitivity

Lamport clocks

A Lamport clock is a single integer counter per process.

1. Before each local event, increment the counter.
2. When sending a message, attach the current counter value.
3. When receiving a message with timestamp t, set the counter to max(local, t) + 1.

Example: process A's counter is 1 after its first event and it sends a message with timestamp 1. Process B's counter is 5. On receipt, B sets its counter to max(5, 1) + 1 = 6. If B's counter had been 0, it would become max(0, 1) + 1 = 2, which is greater than the send timestamp in both cases.

Property: if a → b then L(a) < L(b). The converse does not hold. L(a) < L(b) does not imply a → b, because two concurrent events can have any relative timestamp values. A Lamport timestamp therefore cannot detect concurrency.

To make a total order of all events, break ties by process ID: order by (counter, node_id). This order is consistent with causality but arbitrary among concurrent events. It is used, for example, to implement a distributed mutual exclusion queue.

Vector clocks

A vector clock stores one counter per process. Process i keeps a vector V where V[j] is the number of events of process j that i knows about.

1. On a local event or send at process i, increment V[i].
2. Attach V to outgoing messages.
3. On receive of vector W, set V[j] = max(V[j], W[j]) for every j, then increment V[i].

Comparing two vectors A and B:

Unlike Lamport clocks, vector clocks give the exact characterization: a → b if and only if V(a) < V(b).

Dynamo-style stores (Riak, and the original Amazon Dynamo) use vector clocks, or the closely related version vectors, to detect conflicting writes to the same key. When two versions are concurrent, the store keeps both as siblings and the application or a merge function resolves them (see CRDTs). Riak later added dotted version vectors to limit sibling growth.

Costs:

• The vector grows with the number of writers, which is unbounded if every client is a writer. Systems prune old entries or use server IDs instead of client IDs, which can lose precision.
• Every message and stored value carries the vector.

Java vector clock

import java.util.Map;
import java.util.TreeMap;

public class Main {
    enum Order { BEFORE, AFTER, EQUAL, CONCURRENT }

    static final class VectorClock {
        private final Map<String, Long> counts = new TreeMap<>();

        VectorClock copy() {
            var c = new VectorClock();
            c.counts.putAll(counts);
            return c;
        }

        void tick(String node) {
            counts.merge(node, 1L, Long::sum);
        }

        void merge(VectorClock other) {
            other.counts.forEach((node, count) -> counts.merge(node, count, Math::max));
        }

        Order compare(VectorClock other) {
            boolean less = false;
            boolean greater = false;
            var nodes = new java.util.TreeSet<>(counts.keySet());
            nodes.addAll(other.counts.keySet());
            for (String node : nodes) {
                long a = counts.getOrDefault(node, 0L);
                long b = other.counts.getOrDefault(node, 0L);
                if (a < b) {
                    less = true;
                }
                if (a > b) {
                    greater = true;
                }
            }
            if (less && greater) {
                return Order.CONCURRENT;
            }
            if (less) {
                return Order.BEFORE;
            }
            if (greater) {
                return Order.AFTER;
            }
            return Order.EQUAL;
        }
    }

    public static void main(String[] args) {
        var a = new VectorClock();
        a.tick("A"); // A: {A:1}

        // B receives A's state, then writes.
        var b = a.copy();
        b.tick("B"); // B: {A:1, B:1}

        // C also receives A's state, then writes independently.
        var c = a.copy();
        c.tick("C"); // C: {A:1, C:1}

        System.out.println("a vs b: " + a.compare(b));
        System.out.println("b vs c: " + b.compare(c));

        // Merging b and c, then ticking, dominates both.
        var d = b.copy();
        d.merge(c);
        d.tick("A");
        System.out.println("b vs d: " + b.compare(d));
        System.out.println("c vs d: " + c.compare(d));
    }
}

a vs b: BEFORE
b vs c: CONCURRENT
b vs d: BEFORE
c vs d: BEFORE

Hybrid logical clocks

A hybrid logical clock (HLC) combines a physical timestamp with a logical counter. Each timestamp is a pair (l, c), where l tracks the highest physical time seen and c breaks ties when l does not advance.

• On a local event or send: let pt be the current wall-clock time. If pt > l, set l = pt and c = 0. Otherwise keep l and increment c.
• On receive of (l_m, c_m): set l to the maximum of the local l, l_m, and pt. Set c according to which values were equal to the new l: one greater than the largest matching counter, or 0 if pt alone was the maximum.

Properties:

• Preserves causality like a Lamport clock: if a → b then HLC(a) < HLC(b).
• Stays close to physical time (within the clock skew bound), so timestamps are meaningful for humans and for time-range queries.
• Uses fixed space, unlike a vector clock. It cannot detect concurrency.

CockroachDB and YugabyteDB use HLCs for transaction timestamps and MVCC versions.

Comparison

Interview questions

• Why can't a distributed database order writes by wall-clock timestamps? Node clocks drift and are skewed, so a later write can carry an earlier timestamp. With last-write-wins, this silently discards the actually newer write.
• What does a Lamport clock guarantee, and what does it not? If a → b then L(a) < L(b). The reverse fails, so comparing two Lamport timestamps cannot tell whether events are causally related or concurrent.
• When would you choose vector clocks over Lamport clocks? When the system must detect concurrent updates to the same data and preserve both versions, as in leaderless replicated stores. The cost is a vector whose size grows with the number of writers.
• How does Spanner avoid clock-skew anomalies? TrueTime returns a bounded uncertainty interval. A transaction waits out that uncertainty before committing, so commit timestamps order transactions consistently with real time.