Main Page | See live article | Alphabetical index 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). This article is from Wikipedia. All text is available under the terms of the GNU Free Documentation License.