分布式算法

源头： byzantine generals problem (拜占庭将军问题)
目标：在有内鬼的情况下（内鬼人数?），达成一致的决定!

公理1：决策的依据是少数服务多数；
简化版: 两忠一奸难题

image.png

以齐、燕、楚攻秦为例，各国根据自身侦察到的情报，作出本同的决策-进攻/撤退，例如：齐：撤退，燕：进攻？（哈哈可能是这样子的，齐国有大军50万，发现秦国只有90万，人数不行，想撤退；而燕国有大军 100万，发现秦国只有90万，人数还可以，想进攻）；但各国都不能擅自做决策，需要等各国的决策到了后，再根据各国的决策，以少数服务多数的方式，达成多最终的决策（ps: 奇数一定可以）；

另一种场景：如果没有内奸，肯定是没有问题的，例：楚国说：进攻，则会以进攻：撤退 = 2：1方式，大家一起进攻，返之则1：2，大家一起撤退；但是楚国是内奸，对齐国说：撤退，对燕国说：进攻，则会导致齐国撤退，燕国进攻，这样就有可能导致燕国战败；

另一种场景：如果齐国、燕国都决定进攻，这种场景下楚国这个内奸说啥也没用，最终一定是进攻；

另一种场景：如果楚国迟迟不发送自己的决策给其它国家，这种场景下，齐国、燕国则发起下一轮的决策；如果楚国多在多轮（实际的情况可能是3轮、4轮）的都没有发送自己的决策下，齐燕则应该放弃楚国这个盟友哈哈；

因此根据上面描述这个问题会概率性发生！

如何解决呢？

解决方案1：口信消息型byzantine之解
前提：已知m位内奸、则需要总人数达3m+1
收不到决策的情况，决策约定为“撤退”

挑选出某一个国家x，先给其它同家发送决策; 其它国家收到决策后，再除x国家外进行一次决策通信；随着内奸的人数增加，进行的轮次也需要增加；

解决方案2：签名消息型byzantine之解
任何人可以验证签名的真假，如果签名一但被伪造都可以被发现；
通过对决策签名的方式，

两类算法

拜占庭容错算法（byzantine fault tolerance）BFT;
非拜占庭容错算法（故障容错算法 crash fault tolerance ） CFT;
在计算机分布式领域中常讨论的是CFT,即分布式中存在故障、但不存在恶意节点场景下的共识问题；常见算法有PAXOS,RAFT , ZAB等；