04 September 2017

Definition. The relation \(\rightarrow\) on the set of events of a system is the smallest relation satisfying the following three conditions: (1) If \(a\) and \(b\) are events in the same process, and \(a\) comes before \(b\), then \(a \rightarrow b\). (2) If \(a\) is the sending of a message by one process and \(b\) is the receipt of the same message by another process, then \(a \rightarrow b\). (3) If \(a \rightarrow b\) and \(b \rightarrow c\) then \(a \rightarrow c\). Two distinct events \(a\) and \(b\) are said to be concurrent if \(a \nrightarrow b\) and \(b \nrightarrow a\).

We assume that \(a \nrightarrow a\) for any event a. \(\rightarrow\) is an irreflexive partial ordering.

Clock Condition For any events a, b:if a \(\rightarrow\) b, then \(C(a) < C(b)\).

C1. If \(a\) and \(b\) are events in process \(P_i\) and \(a\) comes before \(b\), then \(C_i(a) < C_i(b)\).

C2. If \(a\) is the sending of a message by process \(P_i\) and \(b\) is the receipt of that message by process \(P_j\), then \(C_i(a) < C_j(b)\).

IR1. Each process \(P_i\) increments \(C_i\) between any two successive events.

IR2. (a) If event \(a\) is the sending of a message m by process \(P_i\), then the message m contains a timestamp \(T_m= C_i(a)\). (b) Upon receiving a message m, process \(P_i\) sets \(Ci\) greater than or equal to its present value and greater than \(T_m\).