# 1-3 Time, Clocks, and the Ordering of Events in a Distributed System
## The Partial Ordering
每個 process 裡面有許多事件(event)。看你怎麼實作，執行 subprogram 可以是事件、執行一條 machine instruction 可以是事件。
我們可以假設 process 裡面的 event 可以形成一個順序，可以說 $a$ occurs before $b$ 如果 $a$ happens before $b$。
我們可以把*這個定義*(happens before)延伸到多個 subprocess。
### happened before
:::info
happened before ($\to$) 定義：
以下 $a, b$ 皆為事件(event)
(1) 如果 $a$ 跟 $b$ 事件在同一 process ，且 $a$ 比 $b$ 先執行，那麼 $a\to b$
(2) 如果 $a$ 是訊息發送端， $b$ 是訊息接收端(兩者不同 process)，那麼 $a\to b$
(3) 如果 $a\to b$ 且 $b\to c$ ，那麼 $a\to c$
:::
事件 $a, b$ 為 concurrent 的條件是 $a\not\to b$ 且 $b\not\to a$
我們假設 $a\not\to a$ ($a$ happened before $a$ 不合邏輯)。

==這代表 $\to$ 是*非反身性偏序*的(irreflexive partial ordering)==


以圖1當中為例，$p_1 \to r_4$。($p_1\to q_2\to q_3\to q_4\to r_3\to r_4$)
:::info
$a\to b$ 也可以解釋成： $a$ 可以因果效應影響 $b$ (it is possible for event a to causally affect event b)
:::
==如果兩個事件之間不存在因果關係，那他們為 concurrent。例如$p_3, q_3$。==

## Logical Clocks
Clock 在此定義為一個單純為事件發給數字的東西。(例如今天早上0600起床，你為起床這個事件給了一個0600的數字)
我們定義每個 process $P_i$ 有一個 clock $C_i$，其能為每個 event $a$ 發給一個數字。
整個系統的 clock 定義為 $C$ ，其可為任何事件 $b$ 發給數字 $C(b)$，其 $C(b) = C_j(b)$ 如果 $b$ 屬於 $P_j$
這邊並不保證 $C_i$ 給的數字跟物理時鐘的數字有關係。所以可以把 $C_i$ 想成 logical clock。他們可用任意方式實作。

如果事件 $a$ occurs before $b$，那 $a$ 應該發生於比 $b$ 還早的時間。更正式地定義如下：
### Clock Condition
:::info
Clock Condition. For any events a, b:
if $a\to b$ then $C(a) < C(b)$
:::
:::danger
這邊我們並不能說他的逆命題(converse condition)為真
if $C(a) < C(b)$ then $a\to b$
因為那樣代表所有 concurrent 事件要同時發生。
[證明](https://cs.stackexchange.com/questions/131744/why-does-the-converse-of-the-clock-condition-imply-that-any-two-concurrent-event)
:::
:::info
Clock Condition 滿足條件：
**C1**: 如果 $a, b$ 同屬 $P_i$，且 a 比 b 早，那麼 $C_i(a) < C_i(b)$
**C2**: 如果 $P_i$ 的 $a$ 發訊息給 $P_j$ 的 $b$，那麼 $C_i(a) < C_j(b)$
:::

我們想像 process 的 clock 上的數字會跳動走訪每個數字，跳動發生的時間在事件跟事件之間。
例如 $P_i$ 中的 $a, b$，$C_i(a)=4, C_i(b)=7$，那麼 clock 就會於事件 $a, b$ 中間跳動走訪過 5, 6, 7。
我們把每個跳動發生畫在 Fig. 1 中的虛線，可得到 Fig. 3

:::info
**C1** 代表同 process 的兩個事件中一定有虛線。
**C2** 代表訊息的傳遞一定會經過虛線。
:::
更動 clock $C_i$ 的值並不算是一種事件(event)。
接下來討論如何實作滿足上述兩個條件的時鐘。

滿足 **C1** 只需要 **IR1**。
為了滿足 **C2** ，我們需要發送端有個時間戳記 $T_m$ ，然後接收端在收到的當下要把自己的時鐘設為比 $T_m$ 還晚。
:::info
**IR1**: 每個 process $P_i$ 應該在兩個連續的 event 中增加 $C_i$ 的值。
**IR2**:
(a) 如果 $a$ 是訊息 $m$ 的傳遞者，那麼訊息 $m$ 應該包括時間戳記 $T_m=C_i(a)$
(b) $P_j$ 收到訊息的當下要把自己的 $C_j$ 的值設為 $max(C_j, T_m+1)$
:::

## Ordering the Events Totally
我們可以使用一系列符合 **Clock Condition** 的 clock 來為 events 做完全排序(total ordering)
我們只需要按照事件發生的時間來排序就好。
不過要破解同時發生，只需要另外定義任意關係 $\prec$ 來排序 processes。
我們定義 $\Rightarrow$ 如下：
### 定義 $\Rightarrow$
:::info
如果 $P_i$ 有事件 $a$、 $P_j$ 有事件 $b$，那麼：
$a \Rightarrow b$ if and only if ((i) or (ii))
(i) $C_i(a) < C_j(b)$
(ii) $C_i(a) = C_j(b)$ and $P_i \prec P_j$
:::
也就是說 $\Rightarrow$ 是把 happened before ($\to$) 從偏序(partial ordering)推廣到全序(total ordering)的方法。

### Solving mutual exclusion problem
能夠全序定義事件對於分散式系統非常有用，以下舉例：
考慮有數個 process 的系統，所有系統共享一個資源，同時只能有一個 process 存取資源。
我們想要實做一個演算法來達成以下三點 Condition：
:::info
Condition
I. process 必須釋放資源才能給下個 process 用
II. 不同 request 必須依其產生的順序滿足(於 process 內產生的時間)
III. 如果每個允許過資源的 process 最終會釋出資源，那所有 request 最終都會被滿足。
:::
注意 **II** 並沒有註明 concurrent request 的處理方式。
如果是以一個中央管理 process 來給予資源，會按照 request 送到的順序來給予，那可能會違反 **II**。

這裡我們可以用 **IR1** 跟 **IR2** 來定義所有事件的全序($\Rightarrow$)。
這就只是確保所有 process 都知道其他 process 在幹嘛、進度到哪。

### Algorithm
每個 process 都會維護自己的 **request queue**。
一開始每個 **request queue** 都有一則訊息 "$T_0:P_0$ request resource" ，$P_0$ 是最一開始持有資源的，$T_0$ 為小於任何 clock 的初始值。
以下五個規則可以被定義：
:::info
1. 要要求資源時， $P_i$ 發送要求訊息 "$T_m:P_i$ request resource" 給其他所有 process，然後把該訊息放入自己的 **request queue**。$T_m$ 為時間戳記。
2. 當 $P_j$ 收到訊息 "$T_m:P_i$ request resource" 時，會把它放入自己的 **request queue** ，然後發送具時間戳記的答覆(acknowledgment)給 $P_i$。
3. 要釋放資源時， $P_i$ 從 **request queue** 中移除訊息，然後發送具時間戳記的 "$P_i$ release resource" 訊息給其他所有 process
4. 當 $P_j$ 收到 "$P_i$ release resource" 時，會把 "$T_m:P_i$ request resource" 從 **request queue** 中移除。
5. $P_i$ 可以拿到資源的條件如下:
(i) 自己的 "$T_m:P_i$ request resource" 在 $\Rightarrow$ 規則排序下為最優先。
(ii) 已經收到來自其他所有 process 具時間戳記大於 $T_m$ 的訊息。
:::
==**核心精神在於 "保證每個 process 在取得資源前已經充分了解其他 process 的訊息。**==

:::spoiler 滿足上面 Condition 的方法：
滿足 **Condition I**：因為 3. 跟 4. 是唯二從 **request queue** 刪除訊息的規則。
滿足 **Condition II**：上面 2. 保證了 $P_i$ 釋放資源後 5.(ii) 最終會被滿足。
滿足 **Condition III**：上面 3. 跟 4. 意味著如果每個有資源的 process 最後會釋放，那 5.(i) 最終會被滿足。
:::

## Anomalous Behavior
如果有外部事件介入，那就無法保證事件的順序一致。
例如 A 在電腦上發送事件 $a$，然後打電話給 B 叫他用電腦發送事件 $b$ ，那麼 $b$ 有可能拿到更低的時間戳記(非物理時間，而是 logical clock)，因為系統不知道打電話這個外部事件。

## Physical Clocks
解決上述外部事件的方法，可以導入物理時鐘。

假設 $C_i(t)$ 為 clock $C_i$ 於物理時間顯示 $t$ 時的數值。
- 一個物理時鐘應該為連續的(而非離散)，而且保值恆定速率，即 $\frac{dC_i(t)}{dt} \approx 1$ (速率接近每秒邁進1個數值)
- 每個物理時鐘的差距應該越小越好
:::info
**PC1** $\exists \kappa \ll 1$ such that $|dC_i(t)/dt-1| \lt \kappa$
**PC2** For all $i, j$: $|C_i(t)-C_j(t)| \lt \epsilon$
:::
通常石英鐘 $\kappa \le 10^{-6}$

設 $\mu$ 為系統傳遞訊息的最小時間，如果 $a\to b$ ，那麼如果 $a$ 發生於 $t$ ，則 $b$ 必然晚於 $t + \mu$ 發生。
所以要免疫外部事件介入，必須滿足
$\forall i, j, t$： $C_i(t+\mu)-C_j(t)>0$
再由 **PC1, PC2** 往下推導可得
$\epsilon/(1-\kappa)\lt\mu$

可以看到 process 之間距離越近($\mu$越小)，對時鐘精準度要求越高($\epsilon也要越小)$
==只要上面關係式成立，那麼外部事件介入也不會影響系統正確性==

## Conclusion
* happened before ($\to$) 定義了不變的偏序(partial ordering)來表達事件的關係。
* 延伸了 happened before ($\to$) 為全序(total ordering)(即$\Rightarrow$)，好定義一組演算法來解決同步問題。
* 為了免疫外部事件介入影響，定義了物理時鐘(physical clock)該有的限制來解決此問題。