In computer science, the happened-before relation (denoted: ) is a relation between the result of two events, such that if one event should happen before another event, the result must reflect that, even if those events are in reality executed out of order (usually to optimize program flow). This involves ordering events based on the potential causal relationship of pairs of events in a concurrent system, especially asynchronous distributed systems. It was formulated by Leslie Lamport. In Java specifically, a happens-before relationship is a guarantee that memory written to by statement A is visible to statement B, that is, that statement A completes its write before statement B starts its read.
The happened-before relation is formally defined as the least strict partial order on events such that:
- 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 , .
If there are other causal relationships between events in a given system, such as between the creation of a process and its first event, these relationships are also added to the definition.
- , if and , then (transitivity) ;
- (irreflexivity) ;
- if then (antisymmetry).
Because the happened-before relation is both irreflexive and antisymmetric, it follows that: if then .
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 one to design algorithms for mutual exclusion, and tasks like debugging or optimising distributed systems.
- Lamport, Leslie (1978). "Time, Clocks and the Ordering of Events in a Distributed System", Communications of the ACM, 21(7), 558-565.