拜占庭協議之新領域

Abstract

在分散式系統的諸多應用中，例如在分散式資料庫系統中的二階段委託，重複檔案的 儲存位置，或者飛行控制系統中的降落任務……等等，經常需要使每一個功能正常的 處理機能達成同一協議值，這種問題稱為拜占庭協議問題。 過去有關拜占庭協議問題的研究均侷限於全連接式網路或廣播式網路上只有處理機可 損壞的情形。然而，隨著科技的進步，一個多處理機系統中包含的處理機數目愈來愈 大，若是用全連接式網路，則每個處理機須提供數百個輸出入埠，且系統中傳輸線的 總數更是不計其數，硬體的成本在可預見的未來內為不可行。 反之，若是系統採用廣播式網路，則當處理機數目很大時，每條廣播線路須連接所有 的處理機，所發生的負載問題與資訊傳輸的碰撞問題，均不易解決。所以廣播式網路 亦不切實際。在這兩種不切實際的網路上，所得到的所有結果也必然不切實際了。為 了真正解決拜占庭問題，本論文提出一種新的網路模式，它不但能使每個處理機間能 直接通訊，且較全連接式網路與廣播式網路而言，切合實際得多。本論文所探討的問 題，就是如何在此新網路模式之下，尋找一個解決拜占庭協議問題的最佳解。 由於本文所提出的網路模式是將全連接式網路與廣播式網路混合而作，換言之，全連 接式網路與廣播式網路均為此新網路模式的特殊情形。因而，解決新網路模式下拜占 庭協議問題的解，也同樣可以解決全連接式網路與廣播式網路上的拜占庭協議問題。 除此外，在實際應用上，網路中的傳輸線亦有可能損壞；故在本論文中，拜占庭協議 問題的研究範圍即擴大到一個普及化的假設：即網路中的處理機與傳輸線均有可能損 壞。基於這個假設，共允許處理機損壞的情形及只允許傳輸線損壞的情形均為普及化 假設的特例。如果普及化的拜占庭協議問題得以解決，則各種特例亦可解決。針對普 及化拜占庭協議問題，本論文所提出的方法僅須最少的資訊交換時間，即可使每一個 功能正常的處理機達成協議，並可容許網路中最多數目的損壞元件存在。 有了以上結果，根據本文所述解決拜占庭協議問題的最佳解，可加以擴展以解決交互 合議問題，而此結果又可以偵測系統中的損壞元件，其包括了損壞的處理及損壞的傳 輸線。同時前述各種在分散式系統中的應用問題，如二階段委託，重複檔案的儲存住 置，或者飛行控制系統中的降落任務……等等，經常需要使每一個功能正常的處理機 能達成協議的問題，均可賴以解決。