In the absence of a global clock, we use Happened-Before relation to order events occurring on different processes running on separate systems. We can say an event e "happened before" an event f (notated by: e → f) if one or more of the following cases hold. 1. e and f are events on the same process and e happened before f. 2. e and f are communication events of the same message and e is the send event and f is the receive event. 3. e and f are related by transitivity and event e happened before event g and event g happened before event f. Any two events that cannot be classified under happened before relation are said to be concurrent. Concurrency is shown by '||' symbol. ![]() Note that the transitivity property does not hold for concurrency relation. |
Foundations > Distributed Computing >