Summary

  • Lamport's happened-before relation is the smallest partial order generated by local process order, message send-to-receive edges and transitivity. It records where influence could travel inside the chosen event model.
  • The Clock Condition runs in one direction: a → b requires C(a) < C(b). A smaller scalar timestamp does not prove the reverse claim that a caused, informed or even physically preceded b.
  • Concurrent events have no happened-before path in either direction. That means unordered within the observed model, not simultaneous on a wall clock; later vector clocks preserve that incomparability more faithfully than one scalar.

Two services write apparently decisive records. Event A carries logical time 41. Event B carries 42. A dashboard sorts the rows, draws an arrow and invites the incident team to say that A caused B. The numbers make the story easy. They do not make it true.

Leslie Lamport's 1978 paper, Time, Clocks, and the Ordering of Events in a Distributed System, gave distributed computing a disciplined alternative to such intuition. Its central move was not to discover a hidden universal clock. It was to define exactly which event order the system could justify without one.

A partial order built from observable edges

Lamport models a system as processes, each containing a sequence of events, connected by messages. The relation later called happened-before is the smallest relation satisfying three rules. Within one process, an earlier event precedes a later one. Sending a message precedes receiving that same message. If a precedes b and b precedes c, then a precedes c.

The word “smallest” matters. The relation includes what these rules require and their transitive consequences; it does not fill every gap with a guess. If neither a → b nor b → a, the two distinct events are concurrent.

Lamport explains a → b by saying that a can causally affect b. That is a reachability statement. Information may move along the local steps and message edges from a to b. It is not proof that a's business payload actually changed b, that an operator intended the result, or that a party is responsible for it. A causal route and a semantic cause are different evidence.

The event model also has a boundary. Lamport notes that defining message receipt as an interrupt bit being set rather than the interrupt handler running can change the order of receive events. Before an investigator asks what preceded what, the investigator must know what counts as an event.

The Clock Condition is an implication, not an equivalence

A logical clock assigns a number to each event. Lamport's Clock Condition says that if a happened before b, then the clock value of a must be smaller than the clock value of b. His implementation rules are compact: advance a process's counter between successive events; attach the current value to every outgoing message; and, on receipt, advance the receiving clock beyond both its present value and the message timestamp.

Those rules preserve the known arrows. They do not make the converse true. From C(a) < C(b) alone, one cannot conclude a → b.

That asymmetry is not a defect hidden in the fine print. The paper explains why the converse cannot generally hold for scalar clocks. If every numerical comparison represented happened-before, concurrent events would need to share the same time. One event may be concurrent with two events that are ordered within another process, making that requirement contradictory.

The practical consequence is severe. Scalar time is a safe certificate for one claim when backed by the clock algorithm: a known happened-before edge will not point from a larger value to a smaller one. It is not a certificate that every ascending pair has a causal edge.

A total order is a decision, not a recovered world

Systems often need one answer even where the partial order offers several valid choices. Lamport shows how to extend the order by sorting on logical time and using a fixed process order to break ties. The resulting order is total and remains consistent with happened-before.

But it is not unique. Different clocks satisfying the Clock Condition, or different tie-break rules, can produce different total orders. Lamport writes that only the partial order is uniquely determined by the event system.

This is exactly why a queue, replicated service or audit interface may legitimately choose one order without claiming that it recovered the only real chronology. The tie-break is part of a control rule. It should be recorded as such. Rebranding it as evidence turns a deterministic policy into a false historical fact.

The missing phone call

The paper's “anomalous behavior” example is an early warning about evidence outside the telemetry boundary. A person submits request A on one computer, then telephones a friend in another city and asks the friend to submit B. Because the phone call is outside the computer system, B can receive a lower timestamp and be ordered before A.

Nothing in the internal logical-clock algorithm can recover an edge it never observed. Lamport offers two remedies: explicitly carry the missing ordering information into the system, or use suitably synchronized physical clocks under stronger assumptions.

The example remains contemporary. A support engineer reads one alert and calls a colleague; a customer sees one screen and acts through another channel; an automated workflow triggers a manual approval that returns through a different application. If the evidence graph omits those channels, “no path found” means “no path in this capture,” not “no influence in the world.”

Logical, vector and physical time answer different questions

Lamport's scalar clocks preserve the forward implication required by the Clock Condition and can support an arbitrary consistent total order. A decade later, Colin Fidge and Friedemann Mattern developed vector-time structures that retain more of the partial order. Mattern put the contrast plainly: mapping partially ordered events onto linearly ordered integers loses information because events that may be concurrent can receive different numbers as if they had a definite order.

Vector timestamps can make two events incomparable when neither lies in the other's causal past. That is valuable for debugging, snapshots and conflict reasoning. It still depends on the recorded processes, events and message edges. It does not discover an unlogged telephone call or prove why a human made a decision.

Physical clocks address another problem. Lamport's own paper moves from logical clocks to a Strong Clock Condition, clock-rate error, drift, minimum message delay and synchronization bounds. Those assumptions can align event labels with physical time closely enough for specified purposes. They do not turn logical counters into wall clocks, and they require an uncertainty model of their own.

This division also preserves authorship. Lamport introduced the happened-before framework and scalar logical clocks in the 1978 paper, while crediting Paul Johnson and Bob Thomas for the prior idea of message timestamps. Vector time belongs to the later work of Fidge and Mattern. Combining the results is useful; collapsing their authors into one legend is not.

What an ordering claim should disclose

A defensible incident record should identify the event definition, the process or actor, local sequence, message identity, send/receive match, clock algorithm and the telemetry boundary. If it asserts real-time order, it should also name the physical clock source and error bound. If it asserts cause, it needs evidence about the mechanism that changed the outcome, not merely a rising counter.

The result may be one of several honest statements: happened-before within the captured model; concurrent within that model; placed earlier by a total-order tie-break; physically earlier within a stated uncertainty; or semantically causal evidence still absent.

Lamport's contribution was not a license to sort everything and call the result truth. It was a method for separating the order the system knows, the order it chooses, and the order it cannot yet prove.

Sources