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 $% $.

C1. If $a$ and $b$ are events in process $P_i$ and $a$ comes before $b$, then $% $.

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 $% $.

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