拜占庭協議之新領域

Abstract

在分散式系統的諸多應用中，例如在分散式資料庫系統中的二階段委託，重複檔案的 儲存位置，或者飛行控制系統中的降落任務．．．等等，經常需要使每一個功能正常 的處理能達成同一協議值，這種問題稱為拜占庭協議問題． 過去有關拜占庭協議問題的研究均侷限於全連接式網路或廣播式網路上只有處理機可 損壞的情形．然而，隨著科技的進步，一個多處理機系統中包含的處理數目愈來愈大 ，若是用全連接式網路，則每個處理機須提供數百個輸出入埠，且系統中傳輸線的總 數更是不計其數，硬體的成本在可預見的未來內為不可行． 反之，若是系統採用廣播式網路，則當處理機數目很大時，每條廣播線路須連接所有 的處理機，所發生的負載問題與資訊傳輸的碰撞問題，均不易解決，所以廣播式網路 亦不切實際．在這兩種不切實際的網路上，所得到的所有結果也必然不切實際了，為 了真正解決拜占庭問題，且較全連接式網路與廣播式網路而言，切合實際得多．本論 文所探討的問題，就是如何在此新網路模式之下，尋找一個解決拜占庭協議問題的最 佳解． 由於本文所提出的網路模式是將全連接式網路與廣播式網路混合而成，換言之，全連 接式網路與廣播式網路均為此新網路模式的特殊情形．因而，解決新網路模式下拜占 庭協議問題的解，也同樣可以解決全連接式網路與廣播式網路上的拜占庭協議問題． 除此外，在實際應用上，網路中的傳輸線亦有可能損壞；故在本論文中，拜占庭協議 問題的研究範圍即擴大到一個普及化的假設：即網路中的處理機與傳輸線均有可能損 壞．基於這個假設，只允許處理機損壞的情形及只允許傳輸線損壞的情形均為普及化 假設下的特例．如果普及化的拜占庭協議問題得以解決，則各種特例亦可解決．針對 普及化拜占庭協議問題，本論文所提出的方法僅須最少的資訊交換時間，即可使每一 個功能正常的處理機達成協議，並可容許網路中最多數目的損壞元作存在． 有了以上結果，根據本文所述解決拜占庭協議問題的最佳解，可加以擴展以解決交互 合議問題，而此結果又可用以偵測系統中的損壞元作，其包括了損壞的處理機及損壞 的傳輸線，同時前述各種在分散式系統中的應用問題，如二階段委託，重複檔案的儲 存位置，或者飛行控制系統中的降落任務．．．等等，經常需要使每一個功能正常的 處理機能達成協議的問題，均可賴以解決． /////// Traditionally, the Byzantine Agreement (BA) problem is studied either in a fully connected network or in a broadcast network with processors in malicious failure only. A generalized network model for BA is proposed. A fully connected network or a bradcast network is special case of the new network architecture. Under the new generalized network model, the BA problem is reexamined with the assumption of malicious faults on both processor and transmission medium (TM). The proposed algorthm OABA (Optimal Algorithm for the BA problem) uses the minimal number of message exchanges, and can tolerate the maximal number of allowable faulty components to make each healthy processor reach a common agreement for the cases of processor failures, TM failures, or processor/TM failures. The results can also be used to solve the Interactive Consistency problem and the Consensus problem. As for the applications, a fault detection algorthm FDA is proposed to make every healthy processor be agreed on the healthy condition of the processors and TMs in the μ-γ-FCN. With the extension, OABA can also be used to applied for other various distributed problems, such as the Two-Phase Commit Problem, Distributed Locking, ...etc.