Unreliable Failure Detectors for Reliable Distributed Systems (證明篇)

Weak Completeness to Strong Completeness

演算法

lemma 1: Transforming weak completeness into strong completeness

根據 weak completeness的定義，至少有一個process $p$知道所有的faulty process。根據演算法，$p$ 會不斷的broadcast他自身的結果，在某個時間$t$以後所有的correct process都會接收到$p$的訊息，更新自身的$output$並且所有的faulty process都crash，所以correct process不會在收到faulty process的訊息，也不會把它們從output中移除，因此對每一個 $t'$ > $t$，所有的correct process都會output所有的faulty process，滿足strong completeness的定義。

lemma 2: Perserving perpetual accuracy

定義: $p$在$t$ 之前沒有被suspect，在transform後也一樣

證明: 在某個時間點$t$以前，沒有任何process suspect $p$，故滿足lemma 2。

lemma 3: Preserving eventual accuracy

定義: $p$在$t$之後沒有被suspect，在transform後也一樣

證明: 在某個時間點以後，faulty process都crash，而所有的correct process $p$的訊息都被其他correct process接受過，並且把$p$從自身的output中移除。

證明

從lemma 1可以把weak completeness transform成strong completeness。從lemma 2可以知道，如果是strong accuracy 或是 weak accuracy，在tranform以後還是滿足accuracy。從lemma 3 可以知道，如果detector原本是eventual strong或eventual weak在transform以後還是滿足accuracy。

從以上可以知道，我們可以把相同accuracy的weak completeness detector用來處理strong completeness detector的問題。

Solving Consensus using weak accuracy ans strong completeness failure detector

演算法

lemma 1: 對每個phase的任何 $p$ and $q$，$p$的output set $V_p$，$V_p[q]$ is either $V_q$ or none

證明: 從演算法明顯可見。

lemma 2: 所有的correct process都可以reach phase 3

證明: 只有phase 1和phase 2的 $wait$會block process，所以我們要證明這兩個地方都不會block。

因為是strong completeness，所有的faulty process最後都會出現在failure list中，所以correct process不會因為等待faulty process的訊息而被block，所以每個correct process都可以reach phase 3。

因為是weak accuracy，系統中存在一個correct process $c$，$c$從來沒有被suspect過。

lemma 3

lemma: 在phase 1的每一個round， $1 <= r <= n-1$，所有的process $p$都從$c$收到$(r, O_c, c)$，也就是說$(r, O_c, c)$在$msg_p[r]$ 證明: 因為$p$ 執行n-1 round，且$c$沒被suspect，所以$p$會等待$c$的訊息，並把$(r, O_c, c)$放入$msg_p$中。

lemma 4: 對於phase 1的每個process $p$，在phase 1結束的時候， $V_c$被 $V_p$包含

證明: 分成兩個部份來證明。

1: $r <= n-2$，因此在 r+1 round的時候，$r+1 <= n-1$，$c$ relays $q$的訊息，並把$O_c[q]$設成$v_q$，從lemma 3可以知道，$p$在$r+1$結束的時候，會收到$(r+1, O_c, c)$，並且把$V_p[q]$設定成$v_q$。

2: $r = n-1$，$c$第一次收到$q$的訊息，因為每個process最多relays $q$的訊息一次，因此$p$也已經收到過$q$的訊息，並且把$V_p[q]$設定成$v_q$。

有以上兩點可知，$V_c$被$V_p$包含。

lemma 5: 對於每個phase 2的 process $p$，在phase 2結束的時候，$V_c = V_p$

證明: 分成兩種可能來討論

1: $V_c[q] = V_q$。跟據lemma 4，在phase 1結束的時候，如果$V_c$被$V_p$包含，如果$V_c[q] = V_q$，對其他$p$來說，$V_p[q] = V_q$。

2: $V_c[q] = none$。因為$c$從來沒有被誤判為faulty process，所以在phase 2它的訊息一定會被收到。根據演算法，收到$c$訊息的process，都會把 $V_c[q]$更新成$none$，故 $V_c[q] = V_p[q]$。

從以上兩種情況來看，對每個$q$來說，$V_c[q] = V_p[q]$，故$V_c = V_p$，故得證。

lemma 6: 每個process都decide同樣的值

證明: 從lemma 5可以得到在phase 2結束，每個process的$V$都一樣，且它們會挑選第一個不是$none$的值，因此也會挑出一樣的值來decide。

lemma 7: 每個phase 2的$p$，在phase 2結束的時候，$V_p[c] = v_c$

證明: 從lemma 4可以知道在phase 1結束的時候，$V_q[c] = v_c$，而在phase 2的時候，也不會有任何一個$p$ send $V_p[c] = none$的訊息，所以得證。

Theorem: 可以用Weak accuracy解決 consensus

證明: 滿足consensus的三個條件: validity, agreement and uniform integrity。

根據 lemma 6每個proccess都decide同樣的值，所以滿足agreement。根據lemma 2，每個correct process都會進入phase 3，而根據lemma 7，至少有一個不是$none$的值可以用，所以這個演算法會結束，滿足termination。承上，這個非$none$的值是由某個process所propose，所以滿足validity，因為三個條件都滿足，故得證。

Solving Consensus using eventual weak accuracy ans strong completeness failure detector

演算法

lemma 1: 每個process都decide同樣的值

證明: 如果在phase 4要decide，代表phase 3的時候coordinator $c$至少收到majority的ack，也代表$c$在 phase 2的提出$estimate_c$。我們假設$c$ propose $estimate_c$的round為$r$，嘗試證明對於 $r' >= r$，$estimate_{c'} = estimate_c$。

我們用induction來嘗試證明$r <= r' < k$，對每個k都成立，我們定義round k的coordinator 為$c_k$，也就是$estimate_{c_k} = esticate_c$。

根據演算法，$c_k$如果在phase 2的時候提出$estimate_{c_k}$，代表它已經收到majority的estimate。那至少有一個$p$在round r phase 3的時候送ack給$c$ with $(p, r, ack)$，而且$p$也在round k phase 2的時候send estimate給$c_k$ with $(p, k, estimate_p, ts_p)$。

因為$ts_p$是nondecreasing，而且只有在收到coordinator的時候才會增加，因此$ts_p >= r$，而且也可以輕鬆看出$ts_p < k$，我們定義$t$是$msg_k$中最大的ts，因此存在關係式$r <= t < k$。

在round k phase 2的時候，$c_k$會adopt $(q, k, estimate_q, t)$，也就是$q$在 rount $t$提出的estimate。round t 的coordinator在phase 2的時候send $estimate_q$ to q，因為$r <= t < k$，根據induction，我們可以得出$estimate_q = estimate_c$，故得證。

lemma 2: 每個correct process最終決定some value

證明: 分成兩種狀況討論

1. Some correct process decides。如果這些process要decide，他們會送$(-, -, -, decide)$，根據Reliable Broadcast，這些process一定會$R-deliver$並$decide$。

2. No correct process decides，我們可以用contradiction來證明不會發生。假設$r$是有process blocks的最小round number，因為majoriy會送訊息到coordinator $c$所以有兩種情況:

a. $c$最終收到majority的訊息並提出estimate，所以沒有block。 b. $c$ crash掉。

因為是strong completeness，所以correct process都知道$c$掛掉不會被block，而因為是eventual accuracy，所以最終會有一個process $p$不會被suspect，並完成所有的phase並decide。

Theorem: 在majority存活的情況下，可以用eventual weak accuracy detector solve consensus

證明: 可從lemma 1與lemma 2得證。

Consensus cannot be solved using eventual strong accuracy detector in asynchronous system without majority

證明: 可以用contradiction來證明。如果可以solve consensus的話，我們可以把processes分成兩個set，一群在$t_0$存活，另一群在$t_1$存活，且各自提出不同的值，這樣會造成一種狀況是在$t_0$的時候提出的值與$t_1$提出的值不同，違反consensus，故跟假設矛盾。

Atomic Broadcast and Consensus

演算法

lemma 1: 對任兩個correct process $p$和$q$和message $m$，如果$m$屬於$R-delivered_p$，則最終$m$屬於$R-delivered_q$

證明: 如果$m$屬於$R-delivered_p$，則$p$在task 2 $R-delivered$ $m$，因為$p$, $q$都是correct process，根據Reliable Broadcast的特性，最終$q$ $R-delivers$ $m$，然後把$m$加到$R-delivered_q$。

lemma 2

定義

對任何兩個correct process $p$, $q$和所有 $k >= 1$:

1. 如果$p$執行$propose(k, -)$，則最終$q$執行$propose(k, -)$
2. 如果$p$ A-delivers messages in $A-deliver^k_p$，則最終$q$ A-delivers messages in $A-deliver^k_q$，且$A-deliver^k_p = A-deliver^k_q$

證明

第一點

使用induction來證明。如果$p$執行了$propose(1, -)$，則根據lemma 1，$q$最終會$R-deliverd_q m$，並且根據間眼演算法$task 3$，$R-delivered_q$ - $A-delivered_q$不等於空集合，所以$q$最終會執行$propose(1, -)$。

第二點

如果$p$執行了$porpose(1, -)$，根據第一點所有的$q$最終都執行了$propose(1, -)$，而根據consensus，所有的process最終都$decide(1, msgSet^1)$。因為$A-delivered_p$和$A-delivered_q$一開始都是空的，而且根據consensus，$msgSet^1_p = msgSet^1_q$，所以$A-deliver^1_p = A-deliver^1_q$。

根據induction與上面相似證明，我們可以證明在任意k都成立，因此得證。

lemma 3: 演算法滿足 A-boradcast需要的agreement和total order

證明: 從lemma 2可以知道所有的correct process都以同樣順序send message。

lemma 4: 如果一個correct process $A-broadcasts m$，則最終它$A-delivers m$

證明: 用contradiction來證明。如果$p$ $A-broadcasts m$但沒有$A-delivers m$，代表$m$永遠地停在$R-deliverd_p - A-delivered_p$裡。

根據lemma 2，在某個時間點$k1$以後，也就是時間點$l, l >= k_1$，correct process執行了$propose(l, -)$。而在某個時間點$k_2$，$k_2$以後所有的fault process都crash。假設$k = max(k_1, k_2)$，correct process執行了$propose(k, -)$，根據consensus與lemma 2，msgSet^k會$A-delivered$且包含$m$，故與假設矛盾。

lemma 5: 對任何一個message $m$，$A-delivers m$ only once iff m 之前被$A-broadcast$ by $sender(m)$

證明: 根據演算法，如果$m$ in $A-delivered$，它就在也不會被pick，故滿足only once。而根據演算法，如果$p$執行$decide(k, msgSet^k)$，且$m$在$msgSet^k$裡面，根據consensus，它必定已經被$R-deliver$ by $sender(m)$，所以$sender(m)$ $A-broadcasts$ $m$。

Theorem: 從以上可知我們可用consensus來作出Atomic Broadcast