Logical Clocks (Lamport / Vector)

Wall-clock timestamps cannot order events across nodes. NTP synchronization drifts by milliseconds to seconds, can step backwards, and even with PTP the uncertainty is non-zero. So distributed systems use logical clocks — counters that capture causality based on message-passing rather than wall time.

There are two foundational rules:

1. Happens-before (Lamport's ->): event A 'happens before' event B if (a) A and B are on the same node and A came first, (b) A is the send of a message and B is the receipt of that same message, or (c) there is a chain of such relations linking A to B.
2. Concurrent: A and B are concurrent if neither A -> B nor B -> A. They did not causally influence each other.

Logical clocks assign numbers to events such that if A -> B, then clock(A) < clock(B). Note the contrapositive does NOT hold: clock(A) < clock(B) does not imply A -> B. Vector clocks fix this — they let you distinguish 'A happened before B' from 'A and B are concurrent.'

Lamport timestamps (Leslie Lamport, 1978) assign a single integer to every event. The rules:

1. Each node maintains a local counter starting at 0.
2. Before every event, the node increments its counter.
3. When sending a message, the node attaches its current counter to the message.
4. When receiving a message, the node sets its counter to max(local, received) + 1.

This gives a total order consistent with causality: if A -> B, then L(A) < L(B). To break ties (events with the same Lamport timestamp on different nodes), append a node ID — L(A) = (5, node_3) is a unique, comparable identifier.

Lamport timestamps are used in distributed mutex algorithms (Lamport's mutual exclusion), in transaction ordering (Spanner uses TrueTime-bounded Lamport-like timestamps), and anywhere you need a total order that respects causality. They are cheap (one integer per event) and simple. Their weakness: if L(A) < L(B), you cannot tell whether A caused B or whether they are concurrent — both look the same.

Vector clocks (Mattern, Fidge, 1988) detect concurrency. Each node keeps a vector of N integers (one per node). The rules:

1. Each node's vector starts at [0, 0, ..., 0].
2. Before every local event, the node increments its own slot.
3. When sending a message, the node attaches its full current vector.
4. When receiving a message, the node takes the per-slot maximum of its vector and the received vector, then increments its own slot.

To compare two events:

• v < w if every v[i] <= w[i] and at least one v[i] < w[i] — v happened before w.
• v > w if the reverse holds — w happened before v.
• Otherwise — v and w are concurrent (neither causally influenced the other).

This is the algorithm Dynamo, Riak, and Voldemort use for conflict detection: when a read returns multiple versions of a key, the database compares their vector clocks. If one is greater than another, the older is discarded (a write superseded it). If two are concurrent, both are returned to the client as 'siblings' — the application must merge them (CRDTs make this automatic) or prompt the user.

The cost: each event now carries an N-element vector, so vector clocks are O(N) in storage and comparison time. This is fine for small clusters but impractical for thousands of nodes — which is why production systems use dotted version vectors or version vectors with causality tokens that scale better.

Version vectors are a practical refinement of vector clocks optimized for the common case: tracking causality between versions of the same data, not all events. A version vector clocks writes per-key, not per-event. Amazon DynamoDB and Riak use these. Each write to a key carries the current version vector for that key; the storage system uses vector comparison to detect siblings and discard superseded versions.

The variant used in production systems like Cassandra and Riak is the dotted version vector — it adds a 'dot' (node ID + counter pair) to each version so the merge can detect when one version subsumes another. This handles the case where node A writes, replicates to B, then both A and B write again — without dotted version vectors, you get sibling explosions; with them, the merge is clean.

The general lesson: logical clocks are necessary for causality tracking, but the naive vector-clock implementation has scaling problems. Production systems use specialized variants tuned for their access patterns.

Mental model. Think of Logical Clocks (Lamport / Vector) as a deliberate boundary in a system. The boundary exists because something becomes harder to manage when everything is done in one place: latency, scale, failure isolation, consistency, cost, or team ownership. The useful question is not “what does Logical Clocks (Lamport / Vector) mean?” but “what pressure makes this boundary worth introducing, and what new failure mode does it create?”

Numerical lens: write down traffic, payload size, read/write ratio, peak multiplier and durability target before choosing a component. The numbers should justify the architecture.

Answer this without notes: When would you choose Logical Clocks (Lamport / Vector), and when would you intentionally avoid it? Mention at least one bottleneck it addresses, one failure mode it introduces, and one alternative. Then quantify the workload you are designing for.

Numerical sanity check

Back-of-the-envelope reasoning beats fake precision. State your traffic, payload, concurrency and growth assumptions explicitly, then calculate enough to know whether the current architecture is orders of magnitude away from the target.