Symptom

Two writes to the same key. Which one wins?

Your first instinct is timestamps: whichever has the later wall-clock time is newer. This works in testing. In production you get a bug report saying an update vanished, and when you dig in, node B’s clock was 40 ms behind node A’s, so B’s later write carried an earlier timestamp and lost. NTP is running. NTP does not make clocks identical, it makes them close, and “close” is not “ordered.”

It gets worse. Clocks go backwards during NTP corrections, so your monotonically increasing sequence is not. Leap seconds have taken down production systems. Virtual machine migration can jump a clock by seconds.

There is no global “now” you can consult. This is not a limitation of your infrastructure budget. It is a property of distributed systems that no amount of better hardware removes, and once you accept it the question becomes: what ordering can you have?

Statement

Define the happens-before relation $\to$ on events, as the smallest relation satisfying:

  1. If $a$ and $b$ occur on the same process and $a$ precedes $b$, then $a \to b$.
  2. If $a$ is the send of a message and $b$ is its receive, then $a \to b$.
  3. Transitivity: if $a \to b$ and $b \to c$ then $a \to c$.

If neither $a \to b$ nor $b \to a$, the events are concurrent, written $a \parallel b$. Happens-before is a partial order, not a total one, and the partiality is the physics, not a defect.

Lamport clocks. Give each process a counter $C$. Increment before each local event. Attach $C$ to every message sent. On receive, set $C \leftarrow \max(C, C_{\text{msg}}) + 1$.

The theorem:

$$a \to b \implies C(a) < C(b)$$

And the crucial converse failure: $C(a) < C(b)$ does not imply $a \to b$. Lamport clocks are consistent with causality but do not characterize it. Small timestamps tell you nothing; only the implication in one direction holds.

Argument

Why wall clocks cannot work, in principle. Determining that $a$ happened before $b$ on different machines requires comparing clocks, and comparison requires communication, and communication takes unbounded and variable time. You can bound the error — that is what NTP does, to milliseconds on a LAN — but you cannot eliminate it. For events closer together than the uncertainty, wall-clock comparison is a coin flip. The uncertainty interval is where the ordering lives, and it never shrinks to zero.

Proof that $a \to b \implies C(a) < C(b)$. By induction on the derivation.

Same process: the counter increments before every local event, and never decreases, so a later local event has a strictly larger value.

Send/receive: if $a$ is the send with $C(a) = t$, the message carries $t$, and the receiver sets $C(b) = \max(C_{\text{recv}}, t) + 1 \ge t + 1 > C(a)$.

Transitivity: $<$ is transitive, so chaining works.

Every happens-before edge is one of the two base cases, so any causal chain gives a strictly increasing sequence of counter values.

Why the converse fails, concretely. Two processes that never communicate both increment freely. Process A reaches $C = 5$; process B independently reaches $C = 3$. Nothing connects them, so $3 < 5$ means nothing — those events are concurrent. The order is real but its meaning is one-directional, and treating a Lamport timestamp as a real ordering is the classic misuse.

Why the partial order is the right object. Concurrency is not ignorance. It is a positive fact: if $a \parallel b$, then no observer could have seen $a$ influence $b$ or vice versa, so the system is genuinely free to order them either way. Any total order you impose is a choice, and it must be one you can defend.

Total order by tiebreaking. Order by $(C(e), \text{process id})$. This is a total order consistent with happens-before, which is exactly what state machine replication needs: every replica applies the same operations in the same order, so every replica reaches the same state. That is the foundation the whole consensus literature is built on, and Lamport’s paper derives it in the same few pages.

The connection to relativity, which is not decoration. Lamport’s insight came from special relativity: in spacetime, events outside each other’s light cones have no observer-independent order, and different observers disagree about which came first. Distributed systems have the same structure, with message latency playing the role of the speed of light. The impossibility of global time is the same impossibility in both cases, which is why no engineering advance removes it.

A concrete trace. Three processes, all counters starting at 0. A does a local event ($C_A = 1$) and sends to B ($C_A = 2$, message carries 2). B is at $C_B = 4$ from its own local work, receives, and sets $C_B = \max(4, 2) + 1 = 5$. Meanwhile C has done five local events and sits at $C_C = 5$ having spoken to nobody.

Now B’s receive and C’s fifth event both carry the timestamp 5, and they are genuinely concurrent. Worse, A’s send at 2 is causally before B’s receive at 5, while C’s second event, also at 2, is causally unrelated to anything. The same number means “caused by” in one place and nothing at all in another, and no inspection of the numbers distinguishes the cases. That is the converse failure, in five lines, and it is worth writing out once because the abstract statement does not produce the same discomfort.

Forbids

Ordering distributed events by wall-clock timestamp. Clock skew makes this wrong, silently, and last-write-wins conflict resolution on wall clocks loses data. Cassandra’s LWW behaviour is the well-documented example.

A globally consistent “now.” No protocol gives every node the same instant. The best available is a bounded interval.

Inferring causality from timestamp comparison. $C(a) < C(b)$ is compatible with concurrency. This is the single most common misuse of Lamport clocks in practice.

Detecting concurrency with Lamport clocks. You cannot tell $a \parallel b$ from the counters, because concurrent events still get comparable numbers. That requires vector clocks, and it is exactly why they exist.

Does not forbid

It does not make NTP or PTP useless. They are essential for log correlation, certificate validity, metrics alignment and human debugging. Millisecond-accurate wall clocks are extremely useful; they are just not an ordering primitive. Using them for one thing and Lamport clocks for the other is the correct architecture.

It does not stop bounded-uncertainty clocks from providing real guarantees. Google Spanner’s TrueTime is the counterexample everyone should know: with GPS and atomic clocks it reports an interval $[t_{\text{earliest}}, t_{\text{latest}}]$ with bounded width, typically single-digit milliseconds, and Spanner simply waits out the uncertainty before committing. That buys externally consistent distributed transactions across continents. The theorem is not violated — Spanner pays for ordering with latency, in the open, rather than pretending clocks agree. AWS Time Sync now offers microsecond-level bounds, so this approach is no longer Google-only.

It does not mean hybrid logical clocks are unsound. HLC combines physical time with a logical counter, giving timestamps close to wall clock and consistent with happens-before. CockroachDB, MongoDB and YugabyteDB all use it. You get human-meaningful timestamps without breaking causality, which is usually what you actually wanted.

It does not mean last-write-wins is always wrong. For genuinely idempotent or commutative updates — a cache entry, a heartbeat, a presence flag — LWW is correct and cheap. The failure mode is applying it to non-commutative updates on structured data, which is where CRDTs earn their keep.

It does not require message passing to be visible. Causality can flow through channels your system does not see — a user reads a value on one screen and types it into another. Lamport clocks track only the causality you instrument, and external causality is invisible to them. This is a real source of anomalies in production and not a theoretical footnote.

Boundary

  • Vector clocks characterize causality exactly. One counter per process gives $a \to b \iff V(a) < V(b)$ componentwise, so concurrency becomes detectable. The cost is $O(n)$ metadata per message, which is what T059 is about.
  • Version vectors and dotted version vectors are the production form, used by Dynamo, Riak and Voldemort, with pruning strategies to bound growth.
  • Consistent snapshots. The Chandy–Lamport algorithm records a globally consistent cut without stopping the system, using exactly this causal structure. Flink’s checkpointing is a direct descendant.
  • Where this feeds forward. Total order broadcast is equivalent to consensus, which FLP (T062) proves impossible in an asynchronous system with one crash failure. Lamport clocks give you a consistent order cheaply; agreeing on the order is the expensive problem.
  • Causal ordering is cheaper than total ordering. Delivering messages in an order consistent with happens-before requires only local bookkeeping, and it is what causal consistency in Dynamo-style stores provides. Agreeing on a single total order requires consensus and a majority round-trip, which is orders of magnitude more expensive. Knowing which of the two your application actually needs is usually worth more than any optimization downstream of the choice.
  • The practical rule. Use physical clocks for humans and logical clocks for machines. Any code that compares timestamps from two machines to decide correctness is a bug waiting for the right amount of skew.