:::success
這篇 paper 主要提出了一種解決多個分散式系統主機要對資料做出更新時的衝突解決方法。
核心觀念為讓所有主機為更新請求做投票，多數主機同意才能允許更新請求。
:::

# 1. INTRODUCTION

在電腦網路環境中，人們往往想要有多台電腦各自有一份資料 copy 並且散佈在各處。
各電腦間固有的網路延遲往往是無法保證各資料 copy 的一致性。
:::info
### *mutual consistency*
所有資料 copy 最終都趨向同一結果

### *internal consistency*
單一 copy 內部的不變式(invariant)要維持不變
例如有資料 $x, y, z$，要求 $x+y+z=3$ 一定要符合，這就是 invariant。
:::

以下例子中
$x=y=z=1$ 且 $x+y+z=3$
有主機 $A, B$ ，有兩個更動請求 $R1, R2$
$R1: x:=-1,\ y:= 3$
$R2: y:=-1,\ z:= 3$

- 如果讓兩個請求都接受的話那麼 *internal consistency* 就違反了。
所以兩個請求中至少要有一個被拒絕。

換個角度講，一個請求$R1$會被拒絕，是因為當另一個更新$R2$被接受後，原本$R1$基於的資訊就算是過時了。

- 如果 $R1$ 被 $A$ 接受而 $R2$ 被 $B$ 接受，那麼 *mutual conistency* 就違反了

這裡提出的演算法可以被歸納為一種 *majority consensuss algorithm*。
要令一個請求被接受並套用到所有主機，需要多數的主機去同意他。
投票流程中要讓主機接受一個請求，需要在投票時該請求內容對該主機是合法的。

這個演算法是 Deadlock-free 且保持 *internal / mutual consistency*。
這個演算法也可以從網路或主機事故中恢復。

# 2. DISTRIBUTED DATABASE ENVIRONMENT

這裡假設所有使用者都是透過 DBMP(database managing process) 來做存取，而非直接跟 database copy 做存取。
查詢跟更新請求都是由 AP(application processes) 發出的。

資料庫被假設為由具名變數(named variable)組成，每個具名變數都有資料與時間戳記(timestamp)，時間戳記代表該變數獲取他目前值的時間。
時間戳記有兩個用途：

1. 同步更新時用於確保 *internal consistency*
2. 幫助操作一個類似於 mutial exclusion locks 的功能

另外也會在 DBMP 更新他的 database copy 時需要用到。

:::info
### 更新流程可以以下幾種步驟組成：
1. **Query Database**
AP 向 database 查詢所需要的用於更新的資料，稱作 *base variables* 。
DBMP 也會向 AP 提供資料的 timestamp。
2. **Compute Update**
AP 計算更新後的資料，要更新的資料稱作 *update variables*。
演算法要求 update variable $\subseteq$ base variables。
3. **Submit Request**
AP 組織一個*更新請求 (update request)*，其中包含要更新的資料、舊資料以及其 timestamp，然後發送給 DBMP。
4. **Synchronize Update**
DBMP 主機群投票決定要接受或拒絕請求
其中包含比較 *base variable* 跟自己 copy 的資料的 timestamp；這個檢查可以確定 AP 做出請求的期間資料有沒有被更動。
5. **Apply Update**
如果請求被接受，所有 DBMP 都要套用更新到他們的 copy。
6. **Notify AP**
DBMP 通知 AP 請求的結果，如果被拒絕，那 AP 可能會重複上述步驟並重新發送。
:::

上述更新流程牽涉到了兩種程序間通訊。
AP 跟 DBMP 間的通訊；以及 DBMP 跟 DBMP 間的通訊。
後者為系統確保共識與更新被所有 database copies 套用的關鍵。

# 3. THE MAJORITY CONSENSUS ALGORITHM

:::info
### majority consensus algorithm 由以下五個規則訂定：
1. **DBMP/DBMP Communication Rule**
定義了主機間的溝通模式，包括 daisy chaining、 daisy chaining with timeouts and retransmission、 還有 broadcasting。
2. **Voting Rule**
所有 DBMP 主機在考慮更新請求時要遵循的規定，內容跟用哪個 DBMP/DBMP Communication Rule 息息相關。
3. **Request Resolution Rule**
在 DBMP 投完票之後決定請求的結果為何，，內容跟用哪個 DBMP/DBMP Communication Rule 息息相關。
4. **Update Application Rule**
規定了當更新請求通過時，更新要如何套用到 DBMP 自身的 copy。
5. **Timestamp Generation Rule**
當 AP 提出更新請求時，timestamp 會被產生並附加到請求上。當請求被接受時，timestamp 會套用到被更動的變數資料上。
:::

以上 **Voting Rule** 以及 **Request Resolution Rule** 確保了不會有兩個衝突的更新請求會被同時接受。

## 3.1 DBMP/DBMP Communication Rule
由 AP 發出的更新請求必須在 DBMP 間傳送並投票統計結果。兩種可能的傳送規則如下：
:::info
1. Broadcast
當 DBMP 收到 AP 傳送的請求時，會廣播到其他 DBMP 進行投票，投票後各 DBMP 會傳回結果到發出的 DBMP 統計結果。
2. Daisy Chain
一個 DBMP 收到請求時會投票，並轉送請求給下一位尚未投票的 DBMP。這個步驟會執行到請求被解決為止。
:::

要用哪個傳送規則取決於系統資源與要求。

**Voting Rule** 以及 **Request Resolution Rule** 取決於 DBMP/DBMP 的傳送規則，以下舉例 daisy chaining。

請求處理過程終止的情況有以下兩種：
1. DBMP 找不到下一個可以轉送請求的尚未投票的 DBMP
2. DBMP 在處裡請求到一半 crash 了

Timeout 可以用於解決第二種終止情況。
一個投過票且已轉送請求的 DBMP 可以幫忙看時間內有沒有進一步的結果。
方法是 DBMP 可以跟他轉送的 DBMP 溝通看看有沒有回應。
如果沒有回應，那就會重新轉送請求到另一個還沒投票的 DBMP。
如果有回應，那就只需要設一個 timeout 來確保時間後一定有結果。
這個過程就像是許多網路傳輸協定中的 "timeout and retransmit"。

## 3.2 DBMP Voting Rule

如果兩個更新請求的 *update variable* 有所交集，那兩個更新請求就為互相衝突的。
當 DBMP 考慮更新請求合法性時，會檢查所有 *base variable* 是否在請求之後有做更改，如果沒有的話那就代表沒有其他會衝突的請求有被接受過。
如此， DBMP 可能會對更新請求投下 (OK) 票，否則前提違反時必須投下 (REJ)。
檢查 *base variable* 有沒有被更改的方式為檢察 timestamp。
處在投票與解決之間的請求我們稱作未決狀態(pending)的。

有時候 DBMP 必須考慮兩個衝突的 pending 請求。
有可能 DBMP 已經替先來的請求投下 (OK) 了，這時 DBMP 不能輕易地為第二個請求投下 (OK)，即使第二個請求的 *base variable* 是最新的，因為第一個衝突請求也許會被其他 DBMP 接受，導致 *base variable* 作廢。
一個可能解是 DBMP 可以延後投票直到另一個 pending 請求被接受。

這又引出了另一個問題： deadlock。
例如兩個由不同 DBMP 發出的請求彼此各被投下 (OK) 跟被延後。

解決方法是引入另一個新的投票選擇 (PASS)。
(PASS) 會在當有可能發生 deadlock 時用於通知其他 DBMP 的。當請求衝突時，DBMP 要麼投 (PASS) ，要麼延後投票直到衝突的請求有個結果。
DBMP 對於請求的選擇取決於兩個請求之間的關係。關係可以用一個優先次序場景(priority scheme)解決，一個簡單的例子為替每個請求附上 timestamp。

:::info
現在 DBMP voting rule 可以列為以下幾點：
1. 比較請求的 *base variable* timestamp 與自身 copy 相對應變數的 timestamp。
2. 如果請求有過期 *base variable* ，投下 (REJ)。
3. 如果沒有任何衝突就投下 (OK) ，並把該請求標記為 pending。
4. 如果 *base variable* 沒問題但是與其他更高次序的請求衝突，投下 (PASS)。
5. 否則就延後投票。
:::

延後的情形可能發生於請求跟某個更低次序的請求衝突；或請求中的 *base variable* 比 DBMP 自身 copy 的變數還要來的新。
如果 timeout and retransmit 規則被使用，那某個 DBMP 可能會重複投同一個請求，在這個情況下 DBMP 不能投的跟之前不一樣。

## 3.3 Request Resolution Rule

投完票後，DBMP 會遵照 *request resolution rule* 檢查自己的一票有沒有解決請求。
基本理念是，如果大部分 DBMP 都投下 (OK)，請求應被接受。
==majority consensus 的關鍵在於兩個多數群一定會有一個決定性 DBMP 交集在中間。==
這代表如果兩個請求同時被接受，一定有個 DBMP 同時覺得兩者 (OK)。
:::info
daisy chaining 的 DBMP resolution rule 有以下兩大部分：
1. 替請求\(R)投票後：
a. 如果投的是 (OK) 且多數共識(majority consensus)存在，接受請求 R 並通知所有 DBMP。
b. 如果投 (REJ)，拒絕 R 並通知所有 DBMP。
c. 如果投 (PASS) 且多數共識已經不可能了，拒絕 R 並通知所有 DBMP。
d. 否則轉送 R 給下一個請求。
2. 得知請求\(R)被解決後：
a. 如果 R 被接受：
  i. 用 *update application rule* 來套用 R 。
  ii. 拒絕所有因 R 而延後投票的請求。
b. 如果 R 被拒絕：
  i. 用 *voting rule* 來重新考慮因 R 而延後投票的請求。
:::

**1\(c)** 預防了 deadlock。
記得 DBMP 會在請求有衝突時投 (PASS) ，是為了通知其他 DBMP 可能的 deadlock 情形存在。
該請求可以被其他 DBMP 繼續考慮，直到夠多的 (PASS) 導致共識不可能發生。此時 DBMP 發現他必須拒絕請求。
結果而言，這個條件代表著所有 DBMP 有個共識說這個請求要被拒絕以預防 deadlock。

考慮以下例子：
有 $2N$ 個 DBMP 主機的系統，其中有兩個衝突的請求被各自提出，每個請求也許會發展到各自都各有 $N$ 個 (OK) 票，如果沒有 (PASS) 的機制，那沒有一個請求可以再繼續往後前進，從而發生 deadlock。

注意在 daisy chaining 溝通場景中，一個持不同意見的票就足以讓請求被拒絕。
如果有使用 timeout and retransmit 規則，那投 (REJ) 的條件要被弱化：

:::info
1. b. 如果投 (REJ) 且多數共識已經不可能了，拒絕 R 並通知所有 DBMP。
:::

要弱化的原因是為了避免 DBMP 組織中同時拒絕又接受了請求。
之前的 (REJ) 規則可以運作是因為在純 daisy chaining 的環境中，請求是走一條單純的路徑直到被最後一個 DBMP 決定其命運。
如果有使用 timeout and retransmit 規則，那就有可能會讓請求的路徑產生分支，可能發生多個 DBMP 來決定請求的結果。
弱化 (REJ) 確保所有 DBMP 都下同一個決定。

## 3.4 Update Application Rule

由於接受更新請求的消息的傳送方式，有可能發生通知請求被接受的消息(R1)，在到達某 DBMP 的時候該 DBMP 已經接受另一個請求(R2)，好死不死 R2 會令 R1 的更新內容相比之下並非最新版。

考慮一個 3 DBMP 的系統，其中 DBMP 3 停機了，同時 R1, R2 被其他人接受。
又假設 R1 被 DBMP 1 提出然後被 DBMP 2 接受、R2 被 DBMP 2 提出然後被 DBMP 1 接受。
現在假設 DBMP 3 回來了但是同時 DBMP 2 停機了，那 DBMP 3 會收到來自 DBMP 1 的 R2 被接受的消息。
過一段時間後 DBMP 2 回來了， DBMP 3 會收到 DBMP 2 傳來的 R1 被接受的消息。

也就是說可能某變數 x 在 R1 被改成 1，在 R2 被改成 2，那最新版本的 x 應該是 2 ，但是因為更新順序的不一致，所以 DBMP 3 的 x 有可能變成 1 ，也就是過時的資料。

:::info
*update application rule* 保證了更新有好好照著順序進行。
要套用更新\(R)到 database copy 的變數(v)，先要比較 R 的 timestamp ($T$) 與 database 變數的 timestamp ($Tv$)：
如果 $Tv < T$，更改 v 並把 $Tv$ 設成 $T$；否則忽略更新因為它是過時的。
:::

## 3.5 Timestamp Generation Rule

Timestamp 被用於兩種情境。
用於 *voting rule* 中確保更新請求中的 *base variable* 版本。
以及用於 *update application rule* 保證新的更新優於舊的。

請求的 timestamp 由提出請求的 DBMP 來標記提供。

> 由 DBMP 產生的 timestamp 為一對 $(T, i)$ 表示：
> $T$ 為 DBMP 本地的時鐘時間，稱作 c-part
> $i$ 為 DBMP 順序，稱作 d-part。

> 三路比較關係定義如下：
> $T1=(C1,d1), T2=(C2,d2)$
> ($=$): $T1=T2$ iff $C1=C2\ and\ d1=d2$
> ($>$): $T1>T2$ iff $C1>C2\ or\ C1=C2\ and\ d1>d2$
> ($<$): $T1<T2$ iff $C1<C2\ or\ C1=C2\ and\ d1<d2$
> :::spoiler ie. this code in C++
> ```c++
> C1 == C2 ? d1 <=> d2 : C1 <=> C2;
> ```
> :::

有可能發生時鐘偏斜(clock skew)的情況導致異常，稱作 *sequencing anomaly*。
例如有 $x+y+z=3$ 其中 $x=2,\ y=0,\ z=1$
$R1: x:=0,\ y:= 2$
$R2: x:=1,\ z:= 0$
順序應為 R1 $\to$ R2 但因為異常所以順序顛倒，導致 $x+y+z=2$ 違反了 *internal consistency*。

:::info
DBMP $i$ 用於接受請求 $R$ 使用的 *timestamp generation rule* 為：
$T=1+max(time,\ max(\{Tb\}))$
$time$ 為 DBMP $i$ 的本地時鐘、$\{Tb\}$ 為 $R$ 的 *base variable* timestamp 的 c-part。
$R$ 的 timestamp 為 $(T, i)$。
為了確保本地時鐘不會產生同樣的 timestamp， DBMP $i$ 也重設本地時鐘為 $T$。
:::

## 3.6 Discussion

可以觀察到，只需要大多數或甚至更少的 DBMP 就可以解決一個更新請求。
所以 database 可以允許更動的時候某些 DBMP 無法存取。
另外也不要求所有 DBMP 同時要在線上，因為請求轉送只會同時發生在一對主機之間。

也不要求發起請求的 DBMP 要在當請求解決時在線上，他只要在發起並投完票轉送到下一個 DBMP 的期間在線上就好，回傳到 AP 的結果可以由另一個解決請求的 DBMP 通知。

timeout and retransmit 規則提供了更可靠的系統，但是代價是 (REJ) 票的條件被弱化。造成了需要更多票數以及更多延遲。

為了避免某個 DBMP 重複投票同個請求的結果前後不一，需要額外的記憶體空間來記得自己投過了那些請求，也需要一個系統來 "garbage collect" 這些內容。

<!-- # 4. WHY THE ALGORITHM WORKS

# 5. COST OF THE ALGORITHM

# 6. THE PROBLEM OF MEMORY LOSS

# 7. CONCLUDING REMARKS -->