Event Ordering

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.


In the above diagram, the following examples hold true (green arrows indicate messages).
a → b b → e a → e (transitive) a || d h || c
Note that the transitivity property does not hold for concurrency relation.