“bet韦德官方网站”一文读懂拜占庭将军问题

拜占庭将军问题(The Byzantine Generals Problem)获取了对分布式共识问题的一种情景化叙述，由Leslie Lamport等人在1982年首次公开发表。论文《The Byzantine Generals Problem 》同时获取了两种解决问题拜占庭将军问题的算法：· 口信消息型解决方案(A solution with oral message);· 亲笔签名消息型解决方案(A solution with signed message).论文：https://www-inst.eecs.berkeley.edu/~cs162/sp16/static/readings/Original_Byzantine.pdf本文之后将详尽描写这两种算法。事实上，拜占庭将军问题是分布式系统领域最简单的容错模型， 它叙述了如何在不存在蓄意不道德(如消息伪造或假造)的情况下使分布式系统达成协议完全一致。

是我们解读分布式一致性协议和算法的最重要基础。1. 拜占庭将军问题叙述拜占庭将军问题叙述了这样一个场景：拜占庭帝国(Byzantine Empire)军队的几个师驻守在敌城外，每个师都由各自的将军指挥官。将军们不能通过信使互相交流。

在仔细观察敌情之后，他们必需制订一个联合的行动计划，如反攻(Attack)或者后撤(Retreat)，且只有当半数以上的将军联合发动反攻时才能取得胜利。然而, 其中一些将军有可能是叛徒，企图制止忠心的将军达成协议完全一致的行动计划。

更加差劲的是，负责管理消息传递的信使也有可能是叛徒，他们有可能伪造或假造消息，也有可能使得消息遗失。为了更为了解的解读拜占庭将军问题，我们以三将军问题为事例展开解释。

当三个将军都忠心时，可以通过投票确认完全一致的行动方案，网卓新闻网，图2展出了一种场景， 即General A，B通过观察敌军军情并融合自身情况辨别可以发动反击，而General C通过观察敌军军情并融合自身情况辨别应该后撤。最后三个将军经过投票表决获得结果为反攻：后撤=2:1， 所以将一起发动反攻取得胜利。对于三个将军，每个将军都能继续执行两种决策(反攻或后撤)的情况下, 共计不存在6中有所不同的场景，图2是其中一种，对于其他5中场景可非常简单地求出，通过投票三个将军都将达成协议完全一致的行动计划。当三个将军中不存在一个叛徒时，将有可能妨碍长时间的登陆作战计划。

图3展出了General C为叛徒的一种场景，他给General A和General B发送到了有所不同的消息，在这种场景下General A通过投票获得反攻：后撤=1:2，最后将做出后撤的行动计划；General B通过投票获得反攻：后撤=2:1，最后将做出反攻的行动计划。结果只有General B发动了反攻并战败。

事实上，对于三个将军中不存在一个叛徒的场景，想总能超过完全一致的行动方案是不有可能的。详尽的证明可参见Leslie Lamport的论文。此外，论文中得出了一个更为普适的结论：如果不存在m个叛将，那么最少必须3m+1个将军，才能最后超过完全一致的行动方案。

2. 解决方案Leslie Lamport在论文中得出了两种拜占庭将军问题的解决方案，即口信消息型解决方案(A solution with oral message)和亲笔签名消息型解决方案(A solution with signed message)。1、口信消息型解决方案首先, 对于口信消息(Oral message)的定义如下：A1. 任何早已发送到的消息都将被准确表达;A2. 消息的接收者告诉是谁发送到了消息;A3. 消息的缺席可以被检测。基于口信消息的定义，我们可以闻， 口信消息无法被伪造但是可以被假造。

基于对图3场景的推论，我们告诉不存在一个叛将时，必需再行减少3个忠将才能超过最后的行动完全一致。为加剧解读，我们将利用3个忠将1个叛将的场景对口信消息型解决方案展开推论。

在口信消息型解决方案中，首先发送到消息的将军称作指挥官，其余将军称作副官。对于3忠1叛的场景必须展开两轮登陆作战信息协商，如果没接到登陆作战信息那么配置文件后撤。

图4是指挥官为忠将的场景，在第一轮登陆作战信息协商中，指挥官向3位副官发送到了反攻的消息；在第二轮中，三位副官再度展开登陆作战信息协商，由于General A、B为忠将，因此他们根据指挥官的消息向另外两位副官发送到了反攻的消息，而General C为叛将，为了妨碍登陆作战计划，他向另外两位副官发送到了后撤的消息。最后Commanding General, General A和B达成协议了完全一致的反攻计划，可以取得胜利。

本文来源：bet韦德官方网站-www.bafajgroup.com