拜占庭将军问题

维基百科,自由的百科全书
跳转至: 导航搜索

拜占庭將軍問題Byzantine Generals Problem),是由萊斯利蘭伯特提出的點對點通信中的基本問題。 在分佈式計算上,不同的計算機透過訊息交換,嘗試达成共識;但有時候,系統上協調計算機(Coordinator / Commander)或成員計算機 (Member / Lieutanent)可能因系統錯誤並交換錯的訊息,導致影響最終的系統一致性。拜占庭將軍問題就根據錯誤計算機的數量,尋找可能的解決辦法 ,这無法找到一個絕對的答案,但只可以用來驗證一個機制的有效程度)。

起源[编辑]

拜占庭位於現在土耳其伊斯坦堡,是東羅馬帝國首都。由於當時拜占庭羅馬帝國國土遼闊,為了防禦目的,因此每個軍隊都分隔很遠,將軍與將軍之間只能靠信差傳消息。

在戰爭的時候,拜占庭軍隊內所有將軍副官必需達成一致的共識,決定是否有贏的機會才去攻打敵人的陣營。但是,軍隊可能有叛徒和敵軍間諜,左右將軍們的決定,擾亂軍隊整體的秩序。在進行共識時,結果並不代表大多數人的意見。這時候,在已知有成員謀反的情況下,其餘忠誠的將軍在不受叛徒的影響下如何達成一致的協議,拜占庭問題就此形成。

兩軍問題[编辑]

軍隊與軍隊之間分隔很遠,傳訊息的信差可能在途中路上陣亡,或因軍隊距離,不能在得到消息後即時回覆,發送方也無法確認消息確實丟失的情形,導致不可能達到一致性。在分佈式計算上,試圖在非同步系統和不可靠的通道上達到一致性是不可能的。因此對一致性的研究一般假設信道是可靠的,或不存在非同步系統上而行。

可能的解決辦法[來源請求][编辑]

N:計算機總數

F:有問題計算機總數

信息在計算機間互相交換後,各計算機列出所有得到的信息,以大多數的結果作為解決辦法。

條件[编辑]

在 N ≥ 3F + 1 的情況下一致性是可能解決。

例子[编辑]

有四部計算機,全部正常。

N = 4,F = 0:

例子 1
得到的信息 結果
計算機A O O O O O
計算機B O O O O O
計算機C O O O O O
計算機D O O O O O

4 ≥ 3(0) + 1 是成立,故能得到一致性。

有四部計算機,其中一部是有問題的。

N = 4,F = 1

例子 2 (計算機D = X)
得到的信息 結果
計算機A O O O X O
計算機B O O X O O
計算機C O X O O O
計算機D X O O O O

4 ≥ 3(1) + 1 是成立,故仍然能得到一致性。

註:有問題計算機的總數可能在交換訊息時上升:

N = 4,F = 2

例子 3 (計算機C, D = X)
得到的信息 結果
計算機A O O X X ?
計算機B O X X O ?
計算機C X X O O ?
計算機D X O O X ?

4 ≥ 3(2) + 1 是成立,故不能得到一致性。