Happened-before
|
|
The happened-before relationship is important in figuring out partial ordering of events and in producing and synchronizing logical clocks 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 clocks must be used.
The happened-before relationship is used in timestamping messages (Lamport Timestamps) and in building logical clocks (Lamport Clocks).