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).