拜占庭将军问题描述:
有N位将军一起合作进行军事行动，其中有M位叛将，这N位将军里有一位话事人（有可能由叛将担任话事人），话事人以通信的方式给其他将军发布军事指令，军事指令假设只有进攻和撤退两种，要有一种算法保证在该话事人给其他将军发送不一致的行动指令的情况下（部分将军收到进攻指令，部分将军收到撤退指令），所有的忠将都采取一致的动作，要么一起进攻，要么一起撤退。
翻译成分布式环境下的一致性场景：一个集群有N个节点，其中有M个不稳定节点，在N个节点中有一个leader节点（有可能由不稳定节点担任leader），该leader节点会给其他节点发送0和1两种消息，需要有一种算法保证在leader给其他节点发送的消息不一致的情况下，能保证所有的稳定节点最后认可的消息是一致的，要么都是1，要么都是0。
-
总结下条件：
总将军数：N - 集群总节点：N
总的叛将数：M - 不稳定节点数：M
满足前提：N>=3M+1 - 集群可用前提：N>=3M+1
至于为啥是3*M+1，后续再研究…
如何解“拜占庭将军问题”？
Leslie Lamport等牛人的论文里提到了口头协议(Oral Messages)和Signed messages(书面协议)两个解决方案。今天先来看看口头协议这种方案。
先出结论，如果有m个叛军，必须至少有 3m+1位将军（包括背叛和忠诚的将军）才能保证口头协议算法（以下简称OM算法）能解“拜占庭将军问题”。
口头协议算法有下面几个假设：
- 军队中的通讯兵完全可以相信，所有的消息都能被正确的发送；
- 收到消息的人知道消息是谁发出来的；
- 缺少的消息能被察觉出来；（这里，如果叛军不配合发送消息，算法默认一个值“撤退”的来替代）；
根据场景来讲下算法步骤，假设总将军数有7个，假设叛将数为最大的2个（要保证N>3*M+1）：
总将军数：N=7 ，其中有5个忠将，分别用Z1、Z2、Z3、Z4、Z5标识
叛将数：M=2，分别用P1、P2标识
军事行动：Q表示进攻，T表示撤退，叛将的消息为?，因为叛将可能发送任何伪造的消息，可能是Q也可能是T
场景一 Leader是叛将P1！
* 记住最后的预期是 即使所有的将军得到的指令都不同，但是最后会使用统一的指令（保证一致性）。
P1向其他将军故意发送混乱的消息，如图：
P1给其他将军发送了不同的指令，这时候如何保证忠将能最终执行统一的行动呢？
- Step1：每位将军收到指令后都会将自己收到的指令再次分发给其他的将军，如：Z1收到T的指令，那么他需要将这个信息再次告知其他将军说：我收到的指令是T。这时由于P2也是叛将，所以他可以在这一步造假。
- Step2：在每位将军收到其他将军发送过来的消息后，会做一次check操作，因为其他将军的消息是不可信的，check的逻辑如下，以Z1视角举例:（这里有个前提：忠臣的话始终是真话，所以在整个过程中是一致的，所以忠臣的话在这个流程里是有上下文关系的，在看的时候，注意忠将的话是有上下文的。）
- Step3：Z1视角
P2对Z1说：我收到的消息为T，Z1会去向其他将军求证，会问其他将军，P2给他们发的是什么，如果是忠将，会回复P2他们收到的的真实消息，Z2说：P2跟我说的是Q，Z3说：P2跟我说的是T，Z4说：P2跟我说的是Q，Z5说：P2跟我说的是T，P2跟其他将军说的话统计如下：
| Z1 | Z2 | Z3 | Z4 | Z5 |
|---|---|---|---|---|
| T | Q | T | Q | T |
采用超过一半的答案，得出P2的消息为T
Z2对Z1说：我收到的消息为Q（Z2是忠将，会如实说出收到的指令），同样的，Z1会向其他将军求证Z2的话，会问其他将军：Z2给他们发的是什么 ? P2是叛将，会隐藏Z2告诉他的真实值，所以此处用？来表示，Z3说：Z2跟我说的是Q，Z4说：Z2跟我说的是Q，Z5说：Z2跟我说的是Q，Z2对其他将军说的话统计如下：
| P2 | Z1 | Z3 | Z4 | Z5 |
|---|---|---|---|---|
| ？ | Q | Q | Q | Q |
采用超过一半的答案，得出Z2的消息为Q
Z3对Z1说：我收到的消息是T（Z3是忠将，会如实说出收到的指令），同样的，Z1会向其他将军求证Z3的话，会问其他将军：Z3给他们发的是什么 ?
P2是叛将，可能说出任意值，此处用？来表示，Z2说：Z3跟我说的是T，Z4说：Z3跟我说的是T，Z5说：Z3跟我说的是T，Z3对其他将军说的话统计如下：
| P2 | Z1 | Z2 | Z4 | Z5 |
|---|---|---|---|---|
| ？ | T | T | T | T |
采用超过一半的答案，得出Z3的消息为T
Z4对Z1说：我收到的消息为Q（Z4是忠将，会如实说出收到的指令），同样的，Z1会向其他将军求证Z4的话，会问其他将军Z4告诉他们的是什么 ?
P2是叛将，可能说出任意值，此处用？来表示，Z2说：Z4跟我说的是Q，Z3说：Z4跟我说的是Q，Z5说：Z4跟我说的是Q，Z4对其他将军说的话统计如下：
| P2 | Z1 | Z2 | Z4 | Z5 |
|---|---|---|---|---|
| ？ | Q | Q | Q | Q |
采用超过一半的答案，得出Z4的消息为Q
同样得到Z5对其他将军说的话统计如下：
| P2 | Z1 | Z2 | Z3 | Z4 |
|---|---|---|---|---|
| ？ | T | T | T | T |
采用超过一半的答案，得出Z5的消息为T
最终Z1得出所有将军的指令集合为：T T Q T Q T，得出最终执行T
- Step4：Z2视角，重复这个过程
P2告诉Z2说：他收到的指令为Q，Z2会向其他将军求证P2的话，会问其他将军：P2给他的答案分别是什么？Z1说：P2跟我说的是T（这里有上下文关联关系，忠将的话会与Step3中的一致），Z3说：P2跟我说的是T，Z4说：P2跟我说的是Q，Z5说：P2跟我说的是T，P2跟其他将军说的话统计如下：
| Z1 | Z2 | Z3 | Z4 | Z5 |
|---|---|---|---|---|
| T | Q | T | Q | T |
采用超过一半的答案，得出P2的消息为T
同样得到Z1跟其他将军说的信息如下：
| P1 | Z2 | Z3 | Z4 | Z5 |
|---|---|---|---|---|
| ？ | T | T | T | T |
采用超过一半的答案，得出Z1的消息为T
同样得到Z3跟其他将军说的信息如下：
| P1 | Z1 | Z2 | Z4 | Z5 |
|---|---|---|---|---|
| ？ | T | T | T | T |
采用超过一半的答案，得出Z3的消息为T
同样得到Z4跟其他将军说的信息如下：
| P1 | Z1 | Z2 | Z3 | Z5 |
|---|---|---|---|---|
| ？ | Q | Q | Q | Q |
采用超过一半的答案，得出Z4的消息为Q
同样得到Z5跟其他将军说的信息如下：
| P1 | Z1 | Z2 | Z3 | Z4 |
|---|---|---|---|---|
| ？ | T | T | T | T |
采用超过一半的答案，得出Z5的消息为T
最终Z2得出所有将军的指令集合为：T T Q T Q T，得出最终执行T
- Step5：Z4视角，重复这个过程，得到的指令集合都为：T T Q T Q T ，得出最终执行T
- Step6：Z5视角，重复这个过程，得到的指令集合都为：T T Q T Q T ，得出最终执行T
- Step7：Z6视角，重复这个过程，得到的指令集合都为：T T Q T Q T ，得出最终执行T
这样将军们就能得到一致的结果！
场景二 Leader是忠将Z1！
Z1向其他将军故意发送一致的消息，但是将军之间的通信会遭到叛将的破坏，如图：
还是使用上面的算法：
- Step1：每位将军收到指令后都会将自己的指令再次分发给其他的将军，如：Z2收到T的指令，那么他需要将这个信息再次告知其他将军说：我收到的指令是T。这时由于P1、P2是叛将，所以他们可以在这一步造假。
- Step2：在每位将军收到其他将军发送过来的消息后，会同样做一次check操作，以Z2视角举例:（这里有个前提：忠臣的话始终是真话，所以在整个过程中是一致的，所以忠臣的话在这个流程里是有上下文关系的，在看的时候，注意忠将的话是有上下文的。）
- Step3：Z2视角
P1对Z2说：我收到的消息是Q，Z2会问其他将军求证P1的话，P2说：P1跟我说的是Q，Z3说：P1跟我说的是T，Z4说：P1跟我说的是Q，Z5说：P1跟我说的是T，P1跟其他将军说的话统计如下：
| P2 | Z2 | Z3 | Z4 | Z5 |
|---|---|---|---|---|
| Q | Q | T | Q | T |
采用超过一半的答案，得出P1的消息为Q
P2对Z2说：我收到的消息是Q，Z2会问其他将军求证P2的话，P1说：P2跟我说的是Q，Z3说：P2跟我说的是Q，Z4说：P2跟我说的是Q，Z5说：P2跟我说的是Q，P1跟其他将军说的话统计如下：
| P2 | Z2 | Z3 | Z4 | Z5 |
|---|---|---|---|---|
| Q | Q | Q | Q | Q |
采用超过一半的答案，得出P2的消息为Q
同样得到Z2跟其他将军说的信息如下：
| P1 | P2 | Z3 | Z4 | Z5 |
|---|---|---|---|---|
| ？ | ？ | T | T | T |
采用超过一半的答案，得出Z2的消息为T
同样得到Z3跟其他将军说的信息如下：
| P1 | P2 | Z2 | Z4 | Z5 |
|---|---|---|---|---|
| ？ | ？ | T | T | T |
采用超过一半的答案，得出Z3的消息为T
同样得到Z4跟其他将军说的信息如下：
| P1 | P2 | Z2 | Z3 | Z5 |
|---|---|---|---|---|
| ？ | ？ | T | T | T |
采用超过一半的答案，得出Z4的消息为T
同样得到Z5跟其他将军说的信息如下：
| P1 | P2 | Z2 | Z3 | Z4 |
|---|---|---|---|---|
| ？ | ？ | T | T | T |
采用超过一半的答案，得出Z5的消息为T
最终Z2得出的指令集合为Q Q T T T T，得出最终执行T
- Step4：Z3视角
P1对Z3说：我收到的消息是T，Z3会问其他将军求证P1的话，P2说：P1跟我说的是T；这里有上下文关联关系，忠将的话会与Step3中的一致，Z2说：P1跟我说的是Q，Z4说：P1跟我说的是Q，Z5说：P1跟我说的是T，P1跟其他将军说的话统计如下：
| P2 | Z2 | Z3 | Z4 | Z5 |
|---|---|---|---|---|
| T | Q | T | Q | T |
采用超过一半的答案，得出P1的消息为T
P2对Z3说：我收到的消息是Q，Z2会问其他将军求证P2的话，P1说：P2跟我说的是T，Z2说：P2跟我说的是Q，Z4说：P2跟我说的是Q，Z5说：P2跟我说的是Q，P1跟其他将军说的话统计如下：
| P1 | Z2 | Z3 | Z4 | Z5 |
|---|---|---|---|---|
| T | Q | Q | Q | Q |
采用超过一半的答案，得出P2的消息为Q
同样得到Z2跟其他将军说的信息如下：
| P1 | P2 | Z3 | Z4 | Z5 |
|---|---|---|---|---|
| ？ | ？ | T | T | T |
采用超过一半的答案，得出Z2的消息为T
同样得到Z3跟其他将军说的信息如下：
| P1 | P2 | Z2 | Z4 | Z5 |
|---|---|---|---|---|
| ？ | ？ | T | T | T |
采用超过一半的答案，得出Z3的消息为T
同样得到Z4跟其他将军说的信息如下：
| P1 | P2 | Z2 | Z3 | Z5 |
|---|---|---|---|---|
| ？ | ？ | T | T | T |
采用超过一半的答案，得出Z4的消息为T
同样得到Z5跟其他将军说的信息如下：
| P1 | P2 | Z2 | Z3 | Z4 |
|---|---|---|---|---|
| ？ | ？ | T | T | T |
采用超过一半的答案，得出Z5的消息为T
最终Z2得出的指令集合为T Q T T T T，得出最终执行T
- Step5：Z4视角，重复这个过程，得到的指令集合都为：？？T T T T ，得出最终执行T
- Step6：Z5视角，重复这个过程，得到的指令集合都为：？？T T T T ，得出最终执行T
- Step7：Z6视角，重复这个过程，得到的指令集合都为：？？T T T T ，得出最终执行T
这样将军们就能得到一致的结果！
可以看出，在拜占庭将军问题模型里，leader是不可信的，可能发送虚假消息给其他节点，而在我们大多数的分布式场景下，都是默认leader节点消息是可信的，比如zookeeper的ZAB协议，只会考虑节点是否宕机、网络通道是否稳定等情况。不会考虑leader节点恶意发送混乱消息的情况。但是比特币是会考虑这种情况。
从上面的例子中，大致可以看出口头协议的思路，就是既然所有节点都是不可信的，那么我就不会通过部分信息来判断最终结果，我把全网的所有信息都拿到手里，然后用多数服从少数的原则来分析最终结果，来保证最终一致性，比如最终的计算公式是：
V = function(arg) ,V是最终的结果，function是计算函数，arg是输入的参数，既然局部消息是不可信，那么在以局部消息作为arg来输入到这个函数里，就可能得到不同结果，但是如果我让每个节点都把消息扩散开来，稀释bad节点在整个消息总量中的比例，这样就能减少bad节点的影响，然后收集全网的信息（如上面例子中每个节点收到的所有消息 以及 其他节点收到的所有消息）作为函数的输入arg，然后采用多数服从少数的原则，就会得到一致的结果。