The Happens Before Relation
In a distributed system there is no trustworthy global clock, so you cannot order events by wall time. Instead Lamport defined a causal ordering called happens before, written with an arrow.
Three rules define it. First, if two events occur in the same process, the earlier one happens before the later one. Second, sending a message happens before receiving that message. Third, the relation is transitive, so if A happens before B and B happens before C, then A happens before C.
The crucial point is that happens before is a partial order, not a total order. Some pairs of events are unrelated. If neither A happens before B nor B happens before A, the two events are concurrent. Concurrent does not mean simultaneous in time, it means neither could have influenced the other through any chain of messages.
This relation captures causality precisely. If A happens before B, then A could have caused B, so any correct ordering must place A first. If A and B are concurrent, either order is acceptable because no information flowed between them.
- In process order is by program sequence.
- Across processes order comes only through messages.
- Concurrent events have no causal link and can be ordered freely.
Key idea
The happens before relation orders events by causality using process order and message passing, forming a partial order where unrelated events are concurrent rather than simultaneous.