Happened-Before

Happened Before ( English for " happened before " ) is in the computer science a logical relationship between two time points.

The Happened -before relation is important to determine the causal order of events in asynchronous distributed systems. It was formulated by Leslie Lamport. The Happened -before relation is implemented by a logical clock in general. Conversely, defining the Happened -Before relation the clocks condition for this logical clock.

To determine the relative time between two events that occur in a distributed system without a global clock, to use the Happened -before - relation ( → ) is defined for Lamport clock as follows:

• On the same process, a → b when the time of a < b the period (the time is given by the local clock )
• If a process sends a message to another process, then a → b where a is the transmitter and B the receiver.
• For three events a, b ​​, c, when B and a → b → c, then a → c ( transitivity ).

The value of the local clock is attached to each message as a timestamp.

The Happened -before relation by Lamport provides only a partial order for the events. It is not sufficient if one wants to consider concurrent events: the concurrency can be connected to a Lamport clock not read, because a → b means that time (a) < time ( b ), but time (a) < time ( b ) does not mean that a → b.

To obtain a total ordering of events, one can eg use vector clocks.

• Theoretical computer science