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

拜占庭将军问题

叛将先发送消息

• 如果是叛将楚先发送作战消息，干扰作战计划，结果会有所不同吗？
  在第一轮作战信息协商中，楚向苏秦发送作战指令"进攻",向齐、燕发送作战指令"撤退"，如图所示(当然还有其他情况，这里指示选择了其中一种，大家也可以尝试推导其他的情况，看看结果是不是一样).
  

• 然后在第二轮作战信息协商中,苏秦、齐、燕分别作为指挥官，将接收到的作战信息附加上自己的签名，并转发给另外两位，如图所示。为了达到干扰作战计划的目的，叛将楚和燕相互勾结了。比如，燕拿到了楚的私钥，也就是燕可以伪造楚的签名，此时，燕为了干扰作战计划，给苏秦发送作战指令"进攻"，给齐发送作战指令"撤退"
  

• 接着，在第三轮作战信息协商中，苏秦、齐、燕分别作为指挥官，将接收到的作战信息附加上自己的签名，并转发给另外以为，如图所示
  

• 最终，苏秦和齐接收到的作战信息都是"撤退、进攻"，按照"执行盒子最中间的指令"的约定，苏秦、齐和燕一起执行作战指令"撤退"，实现了作战计划的一致性。也就是说，无论叛将楚和燕如何捣乱，苏秦和齐都能执行一致的作战计划，保证作战的胜利。

• 需要注意的是，签名消息的拜占庭问题之解，也是需要进行m+1轮(其中m为叛将数，即如果只有楚、燕是叛变的,那么就进行3轮)协商。我们也可以从另外一个角度理解:n位将军，能容忍(n-2)位叛将(只有一位忠将没有意义，因为此时不需要达成共识)。另外，签名消息型拜占庭问题之解，解决的是忠将们如何就作战计划达成共识的问题，也即只要忠将们执行了
  一致的作战计划就可以了，它不关心这个共识是什么，比如在适合进攻的时候，忠将们可能执行的作战计划是撤退，也就是说这个算法比较理论化。关于这一点，这个算法解决的是共识问题，没有与实际场景结合，是很难在实际场景中落地的。在实际场景中，可以考虑改进后的拜占庭容错算法，比如PBFT算法

拜占庭容错算法和非拜占庭容错算法,应该如何选择呢？

为了帮助大家理解拜占庭将军问题，前面讲了苏秦协商作战的故事，现在让我们跳回到现实世界，回到计算机世界的分布式场景中:

• 1.故事里的各位将军可以理解为计算机节点
• 2.忠诚的将军可以理解为正常运行的计算机节点
• 3.叛变的将军可以理解为出现故障并会发送误导信息的计算机节点
• 4.信使被杀可以理解为通信故障、信息丢失
• 5.信使被间谍替换可以理解为通信被中间人攻击，攻击者在恶意伪造信息和劫持通信

需要注意的是，拜占庭将军问题描述的是最困难，也是最复杂的一种分布式故障场景，该场景除了存在故障行为，还存在恶意行为。在存在恶意行为的场景中(比如在数字货币的区块链技术中)，我们必须使用拜占庭容错算法还有PBFT算法、POW算法。在计算机分布式系统中，最常用的是非拜占庭容错算法，即故障容错(Crash Fault Tolerance, CFT)算法。
CFT算法解决的是分布式系统中存在故障，但不存在恶意节点的场景下的共识问题。也就是说，这个场景可能会丢失消息或者有消息重复，但不存在错误消息或者伪造消息的情况，常见的CFT算法有Paxos算法、Raft算法、ZAB协议。那么，如何在实际场景中选择合适的算法类型呢？如果能确定该环境中各节点是可信赖的，不存在篡改消息或者伪造消息等恶意行为(例如DevOps环境中的分布式寻址系统)，推荐使用非拜占庭容错算法;
反之则推荐使用拜占庭容错算法，例如区块链中使用Pow算法