拜占庭将军问题
拜占庭将军问题(The Byzantine Generals Problem)提供了对分布式共识问题的一种情景化描述, 由Leslie Lamport等人在1982年首次发表。
问题描述
拜占庭将军问题是一个协议问题，拜占庭帝国军队的将军们必须全体一致的决定是否攻击某一支敌军。问题是这些将军在地理上是分隔开来的，并且将军中存在叛徒。叛徒可以任意行动以达到以下目标：欺骗某些将军采取进攻行动；促成一个不是所有将军都同意的决定，如当将军们不希望进攻时促成进攻行动；或者迷惑某些将军，使他们无法做出决定。如果叛徒达到了这些目的之一，则任何攻击行动的结果都是注定要失败的，只有完全达成一致的努力才能获得胜利。
内涵：在缺少可信任的中央节点和可信任的通道的情况下，分布在网络中的各个节点应如何达成共识。
当前研究的结论是：如果叛徒的数量大于或等于1/3，拜占庭问题不可解。
2个将军的情况
当两个将军在攻击同一个敌人的时候，一个人被认为是领导，而另一个被认为是跟随着。单一的将军无法打败敌人，因此，两人必须要合作。
为了两军的沟通和决定作战时间，将军1号必须要派遣一个信使穿过敌人的营地去把攻击时间告诉将军2号。但是，信使可能会被敌人抓住因而信息无法传到友军。那会导致将军1号发起攻击时，将军2号和他的军队还呆在原地。
即使2号收到了信息，也需要派遣一个信使回去告诉1号，这可能重复被抓的情况。这样有可能无限延伸ACK，两位将军无法达成一致。
事实上，两个将军问题已被证实无解。https://en.wikipedia.org/wiki/Two_Generals'_Problem#Proof
4个将军的情况
假设4个将军（ABCD）中最多只有1个背叛者。
（1）假设A将军分别告诉B、C、D将军，下午1点发起进攻。假设B、C、D中有一人是叛徒。那么，到了下午1点，将有三个将军发起进攻，同时他们能发现发现没有参与进攻的将军是叛徒。在这种情况中，对任务执行没有影响。
（2）假设如果A是背叛的，A分别告诉B、C、D将军在下午1点、2点、3点发起进攻。于是，到了下午，B、C、D三个将军分别去进攻，都失败了。这种情况下，对任务是毁灭性打击。
为了防止毁灭性失败的情况，1999年，出现了著名的PBFT算法，拜占庭容错算法，提出：对于每一个收到命令的将军，都要去询问其他人，他们收到的命令是什么。
对于第（1）种情况，假设B,C,D中只有一个叛徒（因为叛徒的数量不能大于1/3），假设B是叛徒。在A告诉B,C,D下午1点的进攻时间后，BCD中会再次有信息交互，将各自收到的信息告诉另外两人。此时不管B发出的时间是多少，C和D两人之中都会得到至少两个是1点的消息。管怎么样，C和D都能放心执行1点进攻的命令。
对于第（2）种情况，A是背叛者的情况，在A告诉B、C、D三个不同的时间之后，B、C、D三人之间会有一次信息交互，它们会分别把自己收到的信息告诉给另外两人。
B会收到【1点（来自A），2点（来自C），3点（来自D）】三个不同的时间
C同样会收到三个不同的时间【1点（来自B），2点（来自A），3点（来自D）】
以及D会收到【1点（来自B），2点（来自C），3点（来自A）】。
此时，叛徒数量不超过1/3，可以判断A是叛徒。
3个将军的情况
此时叛徒数量达到1/3，3个将军A、B、C，其中一人是叛徒。假设将军A发出进攻命令“下午1点进攻”，B或C其中一人是叛徒。假设B是叛徒，他可能告诉C，他收到的是“下午两点进攻”的命令。这时C收到一个“下午一点进攻”，一个“下午两点进攻“，因此C不能判断谁是叛徒，也不能判断真正的进攻时间。 另一种情况是，如果A是叛徒，告诉B“在下午1点进攻”，告诉C“在下午2点进攻”。当B告诉C，他收到“在下午1点进攻”的命令时，C收到的是“在下午两点进攻”的命令，同样无法判断进攻的时间和真正的叛徒。 从上面的例子可以看出，在只有三个将军的系统中，只要有一个是叛徒，也即1/3，拜占庭问题便不可解。
针对拜占庭将军问题的解决办法包括：口头协议算法，书面协议算法
口头协议算法：要求每个被发送的消息都能被正确投递，信息接收者知道消息的发送者身份，知道缺少的消息信息。此时，若叛徒数少于1/3，则拜占庭将军问题可解。但该算法不可追根溯源。
书面协议算法：该算法要求签名不可伪造，一旦被篡改即可发现，同时任何人都可以验证签名的可靠性。该算法没有考虑信息传输时延，其签名体系难以实现且签名消息记录的保存难以摆脱中心化结构。
区块链的一致性
我们可以将每一个比特币交易账号看作一个将军，这些账号分布在世界各地，无法聚在一起，很可能会有恶意账号，账号之间的沟通也很可能因为机器坏了、网络断了、黑客攻击等受到破坏，并且有关账号是不是要支付、具体支付多少的讨论也会浪费很多时间。
为此，区块链引入POW共识算法，通过工作量证明，增加了发送信息的成本，降低节点发送消息速率，使得一次只有一个用户可以发出消息；同时在广播时会附上自己的签名。
A向BCD发起提议，BCD看到A签名后的提议书，在验证过后，就会同意进攻提议，而不会发起自己新的进攻提议；如果其中发现错误，才会发起自己的进攻提议。
从区块链的角度描述：当一个矿工打包出一个区块之后，其他节点会对这个区块进行验证。如果验证通过，则表明已经有节点发布新区块成功，自己就不再竞争当前区块打包，而是选择接受这个区块，记录到自己的账本中，然后进行下一个区块的竞争。
