The happened-before relation
) is a means of ordering
events based on the causal relationship
of two events in asynchronous distributed systems
. It was formulated by Leslie Lamport
The happened-before relation is formally defined as:
- If events and occur on the same process, if the occurrence of event preceded the occurrence of event .
- If event is the sending of a message and event is the reception of the message sent in event , .
- Transitivity property: for three events , , and , if and , then .
The happened-before relation is irreflexive and antisymmetric, i.e.:
- (irreflexivity) ;
- such that , if then (antisymmetry).
The processes that make up a distributed system have no knowledge of the happened-before relation unless they use a logical clock, like a Lamport clock or a vector clock. This allows to design algorithms for mutual exclusion and tasks like debugging or optimising distributed systems.