Main Page | See live article | Alphabetical index

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:

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