拜占庭将军问题

拜占庭將軍問題 (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) + 0 是成立，故能得到一致性。

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

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 是不成立，故不能得到一致性。