【拜占庭将军问题】

拜占庭将军问题（Byzantine failures），是由莱斯利·兰伯特提出的点对点通信中的基本问题。含义是在存在消息

丢失的不可靠信道上试图通过消息传递的方式达到一致性是不可能的。因此对一致性的研究一般假设信道是可靠的

，或不存在本问题。

 

故事是这样的，拜占庭帝国想要进攻一个强大的敌人，为此派出了10支军队去包围这个敌人。这个敌人虽不比拜占庭帝国，但也足以抵御5支常规拜占庭军队的同时袭击。基于一些原因，这10支军队不能集合在一起单点突破，必须在分开的包围状态下同时攻击。他们任一支军队单独进攻都毫无胜算，除非有至少6支军队同时袭击才能攻下敌国。他们分散在敌国的四周，依靠通信兵相互通信来协商进攻意向及进攻时间。困扰这些将军的问题是，他们不确定他们中是否有叛徒，叛徒可能擅自变更进攻意向或者进攻时间。在这种状态下，“忠诚”的拜占庭将军们能否找到一种分布式的协议来让他们能够远程协商，达成正确的一致，从而赢取战斗？这就是著名的拜占庭将军问题。

 

一群将军想要实现某一个目标（一致进攻或者一致撤退），但是单独行动行不通，必须合作， 达成共识；由于叛徒的存在，将军们不知道应该如何达到一致。注意，这里“一致性”才是拜占庭将军问题探讨的内容。

 

将军问题

拜占庭将军问题是一个协议问题，拜占庭帝国军队的将军们必须全体一致的决定是否攻击某一支敌军。问题是这些将军在地理上是分隔开来的，并且将军中存在叛徒。叛徒可以任意行动以达到以下目标：欺骗某些将军采取进攻行动；促成一个不是所有将军都同意的决定，如当将军们不希望进攻时促成进攻行动；或者迷惑某些将军，使他们无法做出决定。如果叛徒达到了这些目的之一，则任何攻击行动的结果都是注定要失败的，只有完全达成一致的努力才能获得胜利。

拜占庭假设是对现实世界的模型化，由于硬件错误、网络拥塞或断开以及遭到恶意攻击，计算机和网络可能出现不可预料的行为。拜占庭容错协议必须处理这些失效，并且这些协议还要满足所要解决的问题要求的规范。这些算法通常以其弹性t作为特征，t表示算法可以应付的错误进程数。很多经典算法问题只有在n ≥ 3t+1时才有解，如拜占庭将军问题，其中n是系统中进程的总数。

 

 

失效

所谓拜占庭失效指一方向另一方发送消息，另一方没有收到，或者收到了错误的信息的情形。

在容错的分布式计算中，拜占庭失效可以是分布式系统中算法执行过程中的任意一个错误。这些错误被统称为“崩溃失效”和“发送与遗漏式失效”。当拜占庭失效发生时，系统可能会做出任何不可预料的反应。

这些任意的失效可以粗略地分成以下几类：

进行算法的另一步时失效，即崩溃失效；

无法正确执行算法的一个步骤；

执行了任意一个非算法指定的步骤

各个步骤由各进程执行，算法就是由这些进程执行的。一个错误的进程是在某个点出现了上述情况的进程。没有出现错误的进程是正确的进程。

 

 

解决算法

拜占庭问题的最初描述是：n 个将军被分隔在不同的地方，忠诚的将军希望通过某种协议达成某个命令的一致（比如一起进攻或者一起后退）。但其中一些背叛的将军会通过发送错误的消息阻挠忠诚的将军达成命令上的一致。Lamport 证明了在将军总数大于3m ，背叛者为m 或者更少时，忠诚的将军可以达成命令上的一致。

为了保证上面的需求，必须满足下面两个条件：

1. 每两个忠诚的将军必须收到相同的值 v(i)（v(i)是第i 个将军的命令）

2. 如果第i 个将军是忠诚的，那么他发送的命令和每个忠诚将军收到的v(i)相同

为了简化以上模型，我们使用一个将军发送命令给多个副官的形式来证明，发送命令的将军称为发令者，接收命令的将军为副官，那么上面的两个条件可以表述为：

IC1. 所有忠诚的副官遵守相同的命令

IC2. 如果发出命令的将军是忠诚的，那么所有忠诚的副官遵守司令（发出命令的将军）的命令

特别提示：发送命令的每次只有一个将军，将其命令发送给n-1 个副官。m 代表叛国者的个数，因为将军总数为n，所以副官总数为n-1 个。IC2 中副官遵守实际上是指忠诚的将军能够正确收到忠诚将军的命令消息。