Happened-before

The happened-before relationship is important in figuring out partial ordering of events and in producing a logical clock for asynchronous distributed systems. It was formulated by Leslie Lamport.

In order to figure out the relative time between two events occurring in a distributed system without a global clock, we use the happened-before (->) relationship defined as follows:

• On the same process, a -> b if time of a < time of b (the time is given by the local clock).
• If a process sends a message to another process, then a -> b if a is the send and b is the receive.
• For three events a, b, c, if a -> b and b -> c, then a -> c.

The happened-before relationship is only useful in the partial ordering of events. It will not be very useful when considering concurrent events because a -> b means that time(a) < time(b), but time(a) < time(b) does not mean that a -> b.

In order to formulate total ordering of events, an algorithm such as vector ordering must be used.

The happened-before relationship is used in timestamping messages (Lamport Timestamps) and in building logical clocks (Lamport Clocks).