Distributed Systems Theory

Clock Synchronization & Ordering

Wall-clock time on different machines can never be perfectly synchronized, which breaks the naive idea of ordering events by timestamp. Logical clocks (Lamport, vector) capture causal order — what happened before what — without needing synchronized time at all.

NTP typically synchronizes clocks to within milliseconds, but drift, network jitter, and leap seconds mean two machines' clocks are never provably equal at a given instant
A Lamport clock is a single counter per node, incremented on every event and on every message received (taking the max with the sender's timestamp) — it gives a total order consistent with causality, but not real time
Lamport timestamps can't tell concurrent events from causally-related ones just by comparing numbers — two unrelated events can get the same, or an ambiguous, ordering
Vector clocks (one counter per node, tracked as a vector) can detect concurrency: if neither vector dominates the other, the events are genuinely concurrent
Google Spanner sidesteps the whole problem for its use case with TrueTime: GPS + atomic clocks bound clock uncertainty to a known interval, and the database waits out that interval to guarantee external consistency

"What happened first?" is a deceptively hard question once "first" spans multiple machines. Physical clocks drift and cannot be perfectly synchronized (NTP corrections can even move a clock backward), so comparing raw timestamps from two different nodes to decide event order is unreliable at the granularity most systems need. Logical clocks solve a narrower, achievable version of the problem: capturing causal order — if event A could have influenced event B, logical clocks guarantee A is ordered before B — without requiring synchronized wall time at all.

Lamport clock: one counter, updated on send/receive

class LamportClock {
    private long counter = 0;

    synchronized long tick() {                 // local event
        return ++counter;
    }

    synchronized long onReceive(long messageTimestamp) {
        counter = Math.max(counter, messageTimestamp) + 1;
        return counter;
    }
}

Lamport timestamps across a message

B's clock jumps to stay causally after A's message, not just after its own prior events

A vector clock generalizes this: instead of one shared counter, each node keeps a full vector of counters, one per node it knows about, incrementing its own slot on every event and merging (taking the elementwise max) on message receipt. Comparing two vector clocks tells you not just an order but whether one event happened-before the other, or whether they're truly concurrent — information a single Lamport counter cannot recover.

Lamport vs vector clocks
	Lamport clock	Vector clock
State per node	One integer	One integer per node in the cluster
Gives a total order	Yes (with tie-breaking by node id)	A partial order — concurrency is representable
Detects true concurrency	No — cannot distinguish concurrent from ordered events	Yes — incomparable vectors mean concurrent
Used for	Simple causal ordering, log sequencing	Conflict detection in systems like Dynamo/Riak