拜占庭将军问题

拜占庭将军问题 (Byzantine Generals Problem)，是由莱斯利兰伯特提出的点对点通信中的基本问题。 在分布式计算上，不同的计算机透过讯息交换，尝试达成共识；但有时候，系统上协调计算机 (Coordinator / Commander) 或成员计算机 (Member / Lieutanent) 可能因系统错误并交换错的讯息，导致影响最终的系统一致性。拜占庭将军问题就根据错误计算机的数量，寻找可能的解决办法 (但无法找到一个绝对的答案，只可以用来验证一个机制的有效程度)。

起源

拜占庭位于现在土耳其的伊斯坦布尔，是东罗马帝国的首都。由于当时拜占庭罗马帝国国土辽阔，为了防御目的，因此每个军队都分隔很远，将军与将军之间只能靠信差传消息。 在战争的时候，拜占庭军队内所有将军和副官必需达成一致的共识，决定是否有赢的机会才去攻打敌人的阵营。但是，军队可能有叛徒和敌军间谍，左右将军们的决定，扰乱军队整体的秩序。在进行共识时，结果并不代表大多数人的意见。这时候，在已知有成员谋反的情况下，其余忠诚的将军在不受叛徒的影响下如何达成一致的协议，拜占庭问题就此形成。

两军问题

军队与军队之间分隔很远，传讯息的信差可能在途中路上阵亡，或因军队距离，不能在得到消息后即时回复，发送方也无法确认消息确实丢失的情形，导致不可能达到一致性。在分布式计算上，试图在异步系统和不可靠的通道上达到一致性是不可能的。因此对一致性的研究一般假设信道是可靠的，或不存在异步系统上而行。

可能的解决办法

N：计算机总数
F：有问题计算机总数
信息在计算机间互相交换后，各计算机列出所有得到的信息，以大多数的结果作为解决办法。

条件

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

例子

有四部计算机，全部正常。

N = 4，F = 0：

例子 1   得到的信息 结果 计算机A 计算机B 计算机C 计算机D

O O O O	O
O O O O	O
O O O O	O
O O O O	O

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

有四部计算机，其中一部是有问题的。

N = 4，F = 1：

例子 2 (计算机D = X)   得到的信息 结果 计算机A 计算机B 计算机C 计算机D

O O O X	O
O O X O	O
O X O O	O
X O O O	O

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

注：有问题计算机的总数可能在交换讯息时上升：

N = 4，F = 2：

例子 3 (计算机C, D = X)   得到的信息 结果 计算机A 计算机B 计算机C 计算机D

O O X X	?
O X X O	?
X X O O	?
X O O X	?

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

 

 

源自：http://zh.wikipedia.org/wiki/%E6%8B%9C%E5%8D%A0%E5%BA%AD%E5%B0%86%E5%86%9B%E9%97%AE%E9%A2%98