拜占廷協議之新領域

Abstract

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