# 1-3 Time, Clocks, and the Ordering of Events in a Distributed System
Logical clock，是一種可以在分散式系統上定義Events的causal order的方法，本篇論文提出該方法，並說明為何需要該方法，還有該方法具體的實作方式。

## 1. Introduction

* 為何需要去定義event之間的order:
* 為了讓各個node有一致的total order，也就是每個node看待一連串的event時有合理的順序，當達成total ordering之後才可能去解synchronization的問題。
> * Total order: 在一個集合中(set)每兩個事件一定可以比較，也因此一定存在唯一一個順序。
例如: UserA register -> UserA login -> order -> buy
> * Partial order: 在一個集合中不一定存在唯一一個順序，也就是有些事件是不能比較的。
例如: UserA register與UserB register，並不真的存在事件的因果關係
> * Causality Order: 是Partial order的一種，但是如果系統中有傳收訊息的發生，這是我們可以排序的。
例如: register UserB -> greet to UserB 這是可以知道順序，因為你要可以向UserB招手，UserB一定有註冊在系統中。
* 為何不用physical time去決定event之間的order:
* 電腦的時間本身不精準，會產生時間飄移的現象，導致不同的的電腦如果在沒有sync的話時間會不同。
* 因此作者轉而利用happened before這個性質去定義事件的發生順序，也就是所謂的causal order，最後再從各個事件的causal order推廣到整體的total order。

## 2. The Partial Ordering
* 論文本身先從定義出一個partial order開始，再從partial order延伸到total order。
* 定義 $\rightarrow$ :
* $a, b$ 本身是event。
* 符合以下其中一個條件者，則 $a \rightarrow b$。
* 如果 $a, b$ 在同一個process上運行且 $a$ 執行的比 $b$ 早，則 $a \rightarrow b$。
* 如果 $a$ 是發送訊息的event且 $b$ 是接收該訊息的event，則 $a \rightarrow b$。
* 如果 $a \rightarrow b$ 且 $b \rightarrow c$，則 $a \rightarrow c$。
* 如果 $a \nrightarrow b$ 且 $b \nrightarrow a$，則說 $a, b$ 兩個event是concurrent。
* example:
* $p1 \rightarrow r4$
* 因為 $p1 \rightarrow q2$ , $q2 \rightarrow q4$ , $q4 \rightarrow r3$ , $r3 \rightarrow r4$。
* $p2$ 跟 $r1$ 是 concurrent。


## 3. Logical Clocks
* 首先定義一個函數C，使得clock condition成立。
$$
\begin{align*}
\text{Clock Condition. } &\text{For any events } a, b
\\
&\text{if}\ a \rightarrow b\ then \ C(a) < C(b)
\end{align*}
$$
* 利用這個C去比較兩個不同的event的partial order。
* 演算法的步驟如下:
1. 為每個process指定一個變數 $C$，初始化所有process的 $C$ 為 0，$C_i$ 為第 $i$ 個process的變數。
2. 當某一個 process $i$ 發生message send時:
* 令 $C_i = C_i+1$。
* message在傳送時必須附上自己當前的 $C_i$。
* 將這個event稱為 $a$，則令 $C(a) = C_i$。
3. 當某一個process $i$ 收到process $j$ 的message時:
* 令 $C_i = max(C_i, C_j)+1$。
* 將這個event稱為 $b$，則令 $C(b) = C_i$。

利用這個演算法就可以找出整個event的partial order。

## 4. Ordering the Events Totally
* 這一個section主要是從2提出的partial order做延伸，定義一個新的operator可以使events本身成為total order，而不只是partial order。
* 定義 $\Rightarrow$ :
* $a, b$ 本身是event。
* $P_i, P_j$ 是 process id。
* 符合以下其中一個條件者，則 $a \Rightarrow b$。
* $C(a)<C(b)$
* $C(a)=C(b)$ 且 $P_i < P_j$
* Section後半部的部分是在說明可以利用上面定義的operator在synchronous network的環境下構建一個distributed lock algorithm。
* Algorithm本身無法處理process failure，如果有單一節點fail，那整個系統都必須重啟。

## 5. Anomalous Behavior
* 
* 在上圖中 $C(e)<C(c)$ ，但 $c, e$ 本身並沒有因果關係。
* 根本原因就是 $\Rightarrow$ 操作本身並不代表兩個event有絕對的時間順序，而只代表一個相對的因果順序。也就是
$$
\begin{align*}
&\text{For any events } a, b
\\
&\text{if}\ C(a) < C(b)\ then \ a \rightarrow b\
\end{align*}
$$
這個關係不成立。

## 6. Physical Clocks
* 這一個section嘗試使用Physical Clocks去定義event本身的order，在使用Physical Clocks時有以下兩個條件需要被滿足。
> * There exists a constant $\kappa << 1$
such that for all $i$: $\| dC_i(t)/dt - 1 \|<\kappa$
> * For all i, j: $\|C_i(t) - C_j(t)\|<\epsilon$
* 第一個條件代表的意思是在每個process上的時間流逝速度的誤差必須小於某個極小值，這個性質保證了每個process time shift的幅度不會太大。
* 第二個條件代表的意思是對於同樣的一個物理時間t，在每個process上的Physical Clocks算出來的值的誤差必須小於某個值，這個性質保證了每個process的Physical Clocks會趨近於相同。

## 7. Conclusion
本篇論文利用"happening before"為event定義了一種不變的partial order，並從該order延伸出一種total order，但本篇論文所說的total order本身是一種任意的total order而不是真的按照物理時間的total order。但任意的 total order 會造成 anomalous behavior，所以提出Physical Clocks的概念嘗試找出一個符合時間順序的total order。

## Reference
1. Time, Clocks, and theOrdering of Events ina Distributed System
2. https://ithelp.ithome.com.tw/articles/10218827