在全連接式網路的諸多應用中，例如在分散式資料庫系統中的二階段委託，重複檔案
的儲存位置，或者飛行控制系統中的降落任務‧‧‧等等，經常需要使每一個功能正
常的處理機能達成同一協議值，這種問題可分為三類：拜占庭協議問題，合議問題，
及交互合議問題。過去有關這些協議問題的研究均侷限於只有處理機可損壞的情形。
而實際上，網路中的傳輸線亦有可能損壞；故在本論文中，協議問題的研究範圍即擴
大到一個普及化的假設：即網路中的處理機與傳輸線均有可能損壞。基於這個假設，
只允許處理機損壞的情形及只允許傳輸線損壞的情形均為普及化假設下的特例。如果
普及化的協議問題得以解決，則各種特例亦可解決。針對普及化協議問題，本論文所
提出的方法僅須最少的資訊交換時間，即可使每一個功能正常的處理機達成協議，並
可容許在伓連接式網路中最多數目的損壞元件存在。
本文中並根據前述三類協議問題的定義證明了：
１）交互合議問題可用時執行Ｎ組拜占庭協議問題的解決方法而獲得解決；
２）合議問題可用交互合議問題的解，取其多數值而獲得解決。
依此結論，若拜占庭協議問題得以解決，其餘兩類協議問題亦可獲得解決。故本文中
先討論拜占庭協議問題的解決方法，而後才延伸至交互合議問題及合議問題的解決方
法。有了以上結果，根據本文所述解決協議問題的最佳解，前述各種在分散式系統中
的應用問題，如二階段委託，重複檔案的儲存位置，或者飛行控制系統中的降落任務
‧‧‧等等，經常需要使每一個功能正常的處理機能達成協議的問題，均可賴以解決
。
|