Happened-Before

Happened-before is a strict partial order over occurrences that preserves potential causal influence without requiring one global clock or one total execution order.

In the classic distributed-system formulation, happened-before is generated by:

• Program order between occurrences in one participant.
• A message transmission preceding the corresponding reception.
• Transitive closure: if A happened before B and B happened before C, then A happened before C.

If neither A happened before B nor B happened before A, the occurrences are concurrent relative to this relation.

Interpretation

A happened before B means information from A could have influenced B through the modeled order. It does not prove that A semantically caused B, that A occurred earlier on every wall clock, or that an observer actually saw A before observing B.

The relation is strict: no occurrence happened before itself. It is transitive and allows incomparable pairs. Scalar logical clocks can preserve happened-before in one direction, while vector clocks and related metadata can distinguish more causal order and concurrency.

Derived Uses

• Consistent cuts are downward closed under happened-before.
• Causal consistency preserves the order of happened-before-related operations.
• Version histories can use causal metadata to distinguish succession from concurrency.
• Actor activation and message reception relations can contribute local happened-before edges.
• Provenance can refine happened-before by recording which dependency actually contributed to a result.

An implementation may impose a total order that extends happened-before. That total order is one linear extension of the partial order; it introduces comparisons among concurrent occurrences and should not be mistaken for additional semantic causation.

Modeling Checks

• Which local and communication edges generate the relation?
• Is the relation strict, partial, and transitively closed?
• Which events remain incomparable?
• Does metadata preserve causality fully, partially, or only in one direction?
• Is a later total order a realization choice or part of domain meaning?
• Which observations require closure under happened-before?

External References

• Leslie Lamport, Time, Clocks, and the Ordering of Events in a Distributed System, Communications of the ACM 21(7):558-565, 1978.

Related concepts: causality, ordering, event, observation, process, interaction, consistent cuts, version histories, consistency models, time, actor systems, boundaries.