分布式与一致性协议之拜占庭将军问题(一)

拜占庭将军问题

概述

拜占庭将军问题其实是借拜占庭将军故事展现了分布式共识问题，探讨和论证了解决的办法。实际上，拜占庭将军问题是分布式领域最复杂的一个容错模型，一旦搞懂了它，久能掌握分布式共识问题的解决思路，还能更深刻地理解常用的共识算法，这样在设计分布式系统的时候，就能根据场景特点，更好地选择或者设计合适的算法

什么是拜占庭将军问题?

以战国时期六国抗秦的故事为主线串联

苏秦的困境

战国时期，齐、楚、燕、赵、魏、秦七雄并立，后来秦国的势力不断强大，成为东方六国的共同威胁。于是这六个国家决定联合起来，全力抗秦，以免被秦国各个击破。一天，苏秦作为合纵长，挂六国相应，带着六国的军队叩关函谷，驻军在秦国边境，为围攻秦国做准备。但是，因为各国军队分别驻扎在秦国边境的不同地方，所以军队之间只能通过信使互相联系，这时，苏秦面临一个很严峻的
问题:如何同意作战计划?

万一一些诸侯国暗通秦国，发送误导性的作战信息，怎么办?如果心事被敌人截杀,甚至被间谍替换了，又该怎么办?这些都会导致自己的作战计划被扰乱，出现有的诸侯国在进攻，有的诸侯国在撤退的情况，这时，秦国一定会趁机出兵，把它们逐一击破。

所以，如果达成公式，指定统一的作战计划呢?
这个问题其实是拜占庭将军问题的一个简化表述，也即一个典型的公式难题:如果在可能有误导信息的情况下，采用合适的通信机制，让多个将军达成公式，制订一致的作战计划呢?

二忠一叛难题

为了便于理解和层层深入，先假设只有3个国家要攻打秦国，这3个国家的三位将军，分别叫齐、楚、燕。同时因为很强大，所以只有3个国家半数以上的将军都参与进攻，才能击败敌人(假设)，且在这个期间，将军们彼此之间需要通过信使传递消息，待协商一致之后，才能在同一是按点发动进攻。

例子

• 举个例子。这3位将军各自一脸严肃地决定明天是进攻还是撤退，并让信使传递消息，按照"少数服从多数"的原则投票决定，两个人意见一致就可以了:
  1.齐根据侦察情况决定撤退
  2.楚和燕根据侦察信息，决定进攻

可是，问题来了:一旦有人暗通秦国，就会出现作战计划不一致的情况。比如齐向楚、燕分别发送"撤退"的消息，燕向齐和楚发送"进攻"的消息。撤退:进攻 = 1：1，无论楚投进攻还是撤退，都会成为2:1，这时候还是会形成一个一致的作战方案。

但是，楚这个叛将在暗中配合秦国，让信使向齐发送了"撤退",向燕发送了"进攻",那么:
1.燕看到的是,撤退:进攻=1:2
2.齐看到的是，撤退:进攻=2:1
如图所示，按照少数服从多数的原则，燕单独进攻秦军，最后的结果当然是燕寡不敌众,被秦军打败了。在这里可以看到，叛将通过发送误导信息，非常轻松地干扰了齐和燕的作战计划，导致两位终程将军被秦军逐一击破。这也是常说的二忠一叛难题

口信消息。该如何处理呢？

先来说第一个解决办法。首先，3位将军都分拨一部分军队，由苏秦率领，苏秦参与作战计划讨论并执行作战指令。这样，3位将军的作战讨论就变为了4位将军的作战计划，这能够增加讨论中忠诚将军的数量。然后，4位将军约定了，如果没有受到命令，就执行预设的命令，比如
“撤退”。除此之外，它们还约定一些流程来发送作战信息、执行作战指令，比如，进行两轮作战信息协商。为什么要进行两轮协商呢?后面再解释。

• 第一轮:
  1.先发送作战信息的将军作为指挥官，其他将军作为副官
  2.指挥官将他的作战信息发送给每位副官
  3.每位副官将从指挥官处收到的作战信息作为他的作战指令;如果没有收到作战信息，则把默认的"撤退"作为
  作战指令
• 第二轮:
  1.除了第一轮的指挥官外，剩余的3位将军将分别作为指挥官，向另外两位将军发送作战信息。
  2.然后，这3位将军按照少数服从多数的原则，执行收到的作战指令

为了更直观地理解苏秦地整个解决方案，接下来将演示作战信息的协商过程。会分别以忠将和叛将先发送作战信息为例来完整地演示叛将对作战计划干扰破坏的可能性

• 首先是3位忠将先发送作战信息的情况。
  为了演示方便，假设苏秦先发起作战信息，作战指令是"进攻"。那么在第一轮作战信息协商中，苏秦向齐、楚、燕发送作战指令"进攻",如图所示
  
• 在第二轮作战信息协商中，齐、楚、燕分别作为指挥官，向另外两位将军发送作战信息"进攻",因为楚已经叛变了，所以，为了干扰作战计划，它会发送"撤退"作战指令，如图所示
• 最终，齐和燕收到的作战信息都是"进攻、进攻、撤退"，按照烧出服从多数的原则，齐、燕和苏秦一起执行作战指令"进攻",实现了作战计划的一致性，保证了作战的胜利。那么如果是叛将楚先发送作战信息，干扰作战计划，结果是否会有所不同?在第一轮作战信息协商中，楚向苏秦发送指令"进攻",向齐、燕发送作战指令"撤退",如图所示
  
• 然后在第二轮作战信息协商中，苏秦、齐、燕分别作为指挥官，向另外两位将军发送作战信息，如图所示最终，苏秦、齐和燕收到的作战信息都是"撤退、撤退、进攻"，按照少数服从多数的原则，苏秦、齐和燕执行作战指令"撤退"，实现了作战计划的一致性。也就是说，无论叛将楚如何捣乱，苏秦、齐、和燕都会执行一致的作战计划，从而保证作战的胜利。
  
• 这个解决办法其实是在兰伯特在论文"The Byzantine Generals Problem"中提到的口信问题型拜占庭问题之解(A Solution with Oral Message):如果叛将认数位m,将军任务不能少于3m+1,那么拜占庭将军问题就能解决了，不过，作者在论文中没有讲清除一些细节:

这个算法有个前提，也就是叛将认数m,或者说能容忍的叛将数m是已知晓的。在这个算法中，叛将数m决定了递归循环的次数(也就是说，叛将数m决定了将军们要在多少轮作战信息协商)，既m+1轮(例如这里只有楚是叛将，所以进行了两轮),从另一个角度理解:n位将军，最多能容忍(n-1)/3位叛将

该算法虽然能解决拜占庭将军问题，但它有一个限制，如果叛将认数为m，那么将军总人数必须不小于3m+1.在二忠一叛欸度问题中，在存在1位叛将的情况下，必须增加1位将军，将3位将军的协商共识转换位4位将军的协商共识，这样才能实现忠诚将军的一致性作战计划，那么，有没有什么办法可以在不增加将军认数的情况下之解解决二忠一叛的难题呢?