什么是拜占庭将军问题，跟拜占庭算法有什么关系？

拜占庭将军问题是Leslie Lamport（2013年的图灵讲得住）用来为描述分布式系统一致性问题（Distributed Consensus）在论文中抽象出来一个著名的例子。

这个例子大意是这样的：

拜占庭帝国想要进攻一个强大的敌人，为此派出了10支军队去包围这个敌人。这个敌人虽不比拜占庭帝国，但也足以抵御5支常规拜占庭军队的同时袭击。这10支军队在分开的包围状态下同时攻击。他们任一支军队单独进攻都毫无胜算，除非有至少6支军队（一半以上）同时袭击才能攻下敌国。他们分散在敌国的四周，依靠通信兵骑马相互通信来协商进攻意向及进攻时间。困扰这些将军的问题是，他们不确定他们中是否有叛徒，叛徒可能擅自变更进攻意向或者进攻时间。在这种状态下，拜占庭将军们才能保证有多于6支军队在同一时间一起发起进攻，从而赢取战斗？　

单从上面的说明可能无法理解这个问题的复杂性，我们来简单分析一下：

先看在没有叛徒情况下，假如一个将军A提一个进攻提议（如：明日下午1点进攻，你愿意加入吗？）由通信兵通信分别告诉其他的将军，如果幸运中的幸运，他收到了其他6位将军以上的同意，发起进攻。如果不幸，其他的将军也在此时发出不同的进攻提议（如：明日下午2点、3点进攻，你愿意加入吗？），由于时间上的差异，不同的将军收到（并认可）的进攻提议可能是不一样的，这是可能出现A提议有3个支持者，B提议有4个支持者，C提议有2个支持者等等。

再加一点复杂性，在有叛徒情况下，一个叛徒会向不同的将军发出不同的进攻提议（通知A明日下午1点进攻， 通知B明日下午2点进攻等等），一个叛徒也会可能同意多个进攻提议（即同意下午1点进攻又同意下午2点进攻）。

叛徒发送前后不一致的进攻提议，被称为“拜占庭错误”，而能够处理拜占庭错误的这种容错性称为「Byzantine fault tolerance」，简称为BFT。

1）每个忠诚的将军必须收到相同的命令值vi（vi是第i个将军的命令）。

2）如果第i个将军是忠诚的，那么他发送的命令和每个忠诚将军收到的vi相同。

于是，拜占庭将军问题的可以描述为：一个发送命令的将军要发送一个命令给其余n-1个将军，使得：

IC1.所有忠诚的接收命令的将军遵守相同的命令；

IC2.如果发送命令的将军是忠诚的，那么所有忠诚的接收命令的将军遵守所接收的命令。

Lamport对拜占庭将军问题的研究表明，当n>3m时，即叛徒的个数m小于将军总数n的1/3时，通过口头同步通信（假设通信是可靠的），可以构造同时满足IC1和IC2的解决方案，即将军们可以达成一致的命令。但如果通信是可认证、防篡改伪造的（如采用PKI认证，消息签名等），则在任意多的叛徒（至少得有两个忠诚将军）的情况下都可以找到解决方案。

而在异步通信情况下，情况就没有这么乐观。Fischer-Lynch-Paterson定理证明了，只要有一个叛徒存在，拜占庭将军问题就无解。翻译成分布式计算语言，在一个多进程异步系统中，只要有一个进程不可靠，那么就不存在一个协议，此协议能保证有限时间内使所有进程达成一致。

由此可见，拜占庭将军问题在一个分布式系统中，是一个非常有挑战性的问题。因为分布式系统不能依靠同步通信，否则性能和效率将非常低。因此寻找一种实用的解决拜占庭将军问题的算法一直是分布式计算领域中的一个重要问题。