在同步分散式網路以及限制訊息遺失假設下能容忍單一動態錯誤的一致性演算法

Abstract

一致性問題（consensus problem）在分散式系統裡是一個很重要的議題。然而，就我們所知，所有針對這個議題的研究，大部份都是在討論靜態錯誤，只有少數幾篇在討論動態錯誤。靜態錯誤是指若一個 process 有發生錯誤，則它會一直保持在錯誤狀態，但不會導致其它 process 發生錯誤；而動態錯誤則是指隨著時間的改變，會有錯誤發生的 process 不一定是同一群。討論動態錯誤的理由在於，在某些情況下，動態錯誤比靜態錯誤更符合系統的行為。例如：process 會因為電腦病毒而運作失常，但當電腦病毒被防毒軟體治瘉後，process 就不會再有錯誤發生。因此，在這篇論文裡，我們只針對動態錯誤做研究。為了簡化，我們只討論動態錯誤裡的一個特例─單一動態錯誤﹙single mobile failure﹚。 已知在同步分散式系統（synchronous distributed system）下，如果會有單一動態錯誤發生，則一致性問題是無解的。因此，為了使一致性問題有解，我們對系統做了一個嚴苛的假設─限制訊息遺失假設（bounded lost assumption）。我們假設存在一個正整數 r_min，使得對任意 process i，存在另一個 process j 能在回合 r <= r_min 時收到 process i 送出來的訊息。在這個假設之下，我們提出一個需要 rmin + 1個回合的演算法 FloodCons 來解一致性問題。

Consensus problem is one of the most fundamental problems in distributed computing. Most of the papers about this problem focus on static failures, but few focus on dynamic failures. The feature of static failures is that if a process is faulty, then it will remain faulty and cannot cause other process faulty; The feature of dynamic failures is that from time to time, the faulty processes may not be the same group. The reason why we consider dynamic failures is that in some cases, using dynamic failures for capturing system behavior is more suitable than using static failures. For example, process will malfunction due to computer viruses, and function correctly after computer viruses were be healed by anti-virus software. Thus, in this thesis, we only consider the dynamic failures. For simplicity, we focus on a special case of the dynamic failures, called the single mobile failure. Santoro and Widmayer showed that the consensus problem is unsolvable if the single mobile failure may occur. Therefore, in order to cause the consensus problem solvable, we make a very strong assumption, called the bounded lost assumption. This assumption says that there exists an integer $r_{\min}$ such that for all process $i$, there exists some process $j \neq i$ that can receive a message sent from $i$ in round $r \leq r_{\min}$. Then, we present an algorithm \textbf{FloodCons} that requires $r_{\min} + 1$ rounds to solve the consensus problem in this setting.