拜占庭將軍問題

標籤: 暫無標籤

1607

更新時間: 2013-09-17

廣告

拜占庭將軍問題(Byzantine failures)又稱兩軍問題,是由萊斯利·蘭伯特提出的點對點通信中的基本問題。

廣告

1 拜占庭將軍問題 -起源

  拜占庭位於現在土耳其的伊斯坦布爾,是東羅馬帝國的首都。由於當時拜占庭羅馬帝國國土遼闊,為了防禦目的,因此每個軍隊都分隔很遠,將軍與將軍之間只能靠信差傳消息。 在戰爭的時候,拜占庭軍隊內所有將軍和副官必需達成一致的共識,決定是否有贏的機會才去攻打敵人的陣營。但是,在軍隊內有可能存有叛徒和敵軍的間諜,左右將軍們的決定又擾亂整體軍隊的秩序。在進行共識時,結果並不代表大多數人的意見。這時候,在已知有成員謀反的情況下,其餘忠誠的將軍在不受叛徒的影響下如何達成一致的協議,拜占庭問題就此形成。

2 拜占庭將軍問題 -拜占庭將軍問題

  拜占庭將軍問題是一個協議問題,拜占庭帝國軍隊的將軍們必須全體一致的決定是否攻擊某一支敵軍。問題是這些將軍在地理上是分隔開來的,並且將軍中存在叛徒。叛徒可以任意行動以達到以下目標:欺騙某些將軍採取進攻行動;促成一個不是所有將軍都同意的決定,如當將軍們不希望進攻時促成進攻行動;或者迷惑某些將軍,使他們無法做出決定。如果叛徒達到了這些目的之一,則任何攻擊行動的結果都是註定要失敗的,只有完全達成一致的努力才能獲得勝利。
  拜占庭假設是對現實世界的模型化,由於硬體錯誤、網路擁塞或斷開以及遭到惡意攻擊,計算機和網路可能出現不可預料的行為。拜占庭容錯協議必須處理這些失效,並且這些協議還要滿足所要解決的問題要求的規範。這些演算法通常以其彈性t作為特徵,t表示演算法可以應付的錯誤進程數。
  很多經典演算法問題只有在t

3 拜占庭將軍問題 -拜占庭失效

廣告

  所謂拜占庭失效指一方向另一方發送消息,另一方沒有收到,發送方也無法確認消息確實丟失的情形。
  在容錯的分散式計算中,拜占庭失效可以是分散式系統中演算法執行過程中的任意一個錯誤。這些錯誤被統稱為「崩潰失效」和「發送與遺漏是失效」。當拜占庭失效發生時,系統可能會做出任何不可預料的反應。
  這些任意的失效可以粗略地分成以下幾類:
  進行演算法的另一步時失效,即崩潰失效;
  無法正確執行演算法的一個步驟;
  執行了任意一個非演算法指定的步驟
  各個步驟由各進程執行,演算法就是由這些進程執行的。一個錯誤的進程是在某個點出現了上述情況的進程。沒有出現錯誤的進程是正確的進程。

4 拜占庭將軍問題 -拜占庭將軍問題的兩種解決演算法

廣告