《Time, Clocks, and the Ordering of Events in a Distributed System》 阅读笔记。

## 1. The Partial Ordering

System model

• The system is composed of a collection of processes
• Each process consists of a sequence of events
• Sending or receiving a message is an event in a process

Happened before

The relation “happened before” (denoted by $\rightarrow$) on the set of events of a system is the smallest relation satisfying the following three conditions:

• if $a$ and $b$ are events in the same process, and $a$ comes before $b$, then $a \rightarrow b$
• 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$
• 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$.

Causally affect

Another way of viewing the definition is to say that $a \to b$ means that it is possible for event $a$ to causally affect event $b$.

Compare to special relativity

• In relativity, the ordering of events is defined in terms of messages that could be sent.
• In “happened before” relation, only considering messages that actually are send.

也就是说，在分布式系统的 “happened before” 中不考虑隐式因果关系.

## 2. Logical Clocks

Definition

• We define a clock $C_i$ for each process $P_i$ to be a function which assigns a number $C_i(a)$ to any event $a$ in that process.
• The entire system of clocks is represented by the function $C$ which assigns to any event $b$ the number $C(b)$, where $C(b) = C_j(b)$ if $b$ is an event in process $P_j$

Clock Condition

Clock Condition: For any event $a, b$: if $a \to b$ then $C(a) < C(b)$.

• based on the order in which events occur.
• $C(a) < C(b) \nRightarrow a \to b$, since that would imply that any two concurrent events must occur at the same time.

It is easy to see from our definition of the relation $\to$ that the Clock Condition is satisfied if the following two conditions hold:

• 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 pocess $P_j$, then $C_i(a) < C_j(b)$

Implementation Rule of Clock Condition

• IR1 (meet condition C1): Each process $P_i$ increments $C_i$ between any two successive events
• IR2 (meet condition C2)
• 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)$
• Upon receiving a message $m$, process $P_j$ sets $C_j$ greater than or equal to its present value and greater than $T_m$

## 3. Ordering the Events Totally

More precisely, we define a relation $\Rightarrow$ as follows: if $a$ is an event in process $P_i$ and $b$ is an event in process $P_j$, then $a \Rightarrow b$ if and only if either

• $C_i(a) < C_i(b)$

Implies that if $a \to b$ then $a \Rightarrow b$

• $C_i(a) = C_j(b)$ and $P_i \prec P_j$

The oridering $\Rightarrow$ depends upon the system of clocks $C_i$, and is not unique.

## 4. Strong Clock Condition

Strong Clock Condition: For any events $a, b$ in $\varphi$, if $a \leadsto b$ then $C(a) < C(b)$.

where,

• $\varphi$ denote the set of all system events.
• $\leadsto$ denote the “happened before” relation for $\bar{\varphi}$
• $\bar{\varphi}$ denote the set of events which contains the events in $\varphi$ together with all other relevant external events
• $a \leadsto b \nRightarrow a \to b$

## 5. Physical Clocks

For mathematical convenience, we assume that $C_i(t)$ is a continuous, differentiable function of $t$ except for isolated jump discontinuities where the clock is reset.

Physical Clock Condition

• PC1(correct): There exists a constant $\kappa \ll 1$, such that for all $i$: $|\frac{dC_i(t)}{dt} - 1| < \kappa$
• PC2(synchronized): There must be a sufficiently small constant $\epsilon$, such that for all $i, j$: $|C_i(t) - C_j(t)| < \epsilon$

Implementation Rule

Let $m$ be a message which is sent at physical time $t$ and received at time $t'$. We define $v_m = t' - t$ to be the total delay of the message $m$. This delay will, of course, not be known to the process which receives $m$. However, we assume that the receiving process knows some minimum delay $\mu_m > 0$ such that $\mu_m \le v_m$. We call $\xi_m = v_m - \mu_m$ the unpredictable delay of the message.

We now specialize rules IR1 and IR2 for our physical clocks as follows:

• PCIR1: For each $i$, if $P_i$ does not receive a message at physical time $t$, then $C_i$ is differentiable at $t$ and $\frac{dC_i(t)}{dt} > 0$.
• PCIR2:
• If $P_i$ sends a message $m$ at physical time $t$, then $m$ contains a timestamp $T_m = C_i(t)$
• Upon receiving a message $m$ at time $t'$, process $P_j$ sets $C_j(t')$ equal to maximum $(C_j(t' - 0), T_m + \mu_m)$

$C_j(t' - 0) = lim_{\delta \to 0} C_j(t' - |\delta|)$

THEOREM

Assume a strongly connected graph of processs with diameter $d$ which always obeys rules PCIR1 and PCIR2. Assume that for any message $m$, $\mu_m \le \mu$ for some constant $\mu$, and that for all $t \ge t_0$:

• PC1 holds
• There are constants $\tau$ and $\xi$ such that every $\tau$ seconds a message with an unpredictable delay less than $\xi$ is sent over every arc. Then PC2 is satisfied with $\epsilon \approx d(2\kappa \tau + \xi)$ for all $t \gtrsim t_0 + \tau d$, where the approximations assume $\mu + \xi \ll \tau$