拜占庭将军问题OM算法详解

关于“拜占庭将军问题”的背景以及介绍这里老猫就不提了，前面几篇文章讲的也很详细了。今天这里还是直接开门见山说算法。

下面的这个截图是从Lamport发表的论文中截取的：

对于这个英文算法，老猫知道你们肯定看不懂。知你们者，非老猫是也。接下来给你们详细讲讲。

(1) 在第一轮 将军会把消息发送给所有的副官，第i个副官收到的记为 Vi。如 1(这里代表的是攻击)

(2) 在第二轮里面， Li(即第i个副官)会怀疑将军发来的消息Vi是对还是错 ，于是他会问其余的副官。 这样他就会得到剩下的(n-2)个副官的值 。 i从1到n-1，所以每个副官都会得到剩余的n-2个副官手里的Vi。在这一步骤里，忠诚的副官j会直接将自己的 Vj发送给其它人。叛徒则会发假消息。 

在n=7,m=2的时候 如果将军是忠臣的话， 那么在第二轮忠诚的副官确实已经可以判断出要做的决定 ，因为他们会收到(1 1 1 0 0 )再加上将军发来的1就是 1 1 1 1 0 0 但是这个算法是递归的所有必须要到第三轮。 并且如果将军是个叛徒的话，那么第二轮有情形是做不出决定的 。 

这里对进入第三轮的解释是，如L1收到其它L2~L6发来的Vj, 但是他要怀疑准确性，比如L1会想L2发给自己是否是正确的呢？那么就进入第三轮进行投票。

(3)在第三轮里面，接着(2)中后面的问题。 L1会依次询问L3,L4,L5,L6 ，问他们上一轮L2给他们发了什么 ，然后L1会得到在(2)中 L2->L3, L2->L4,L2->L5, L2->L6的值 这样再结合自己的L2->L1的值， 从这5个里面用majority函数投出决定得到L2发给自己的消息值 。依次再进行L3,L4,L5,L6在第二轮中发给自己的消息的确认。 

这样L1就完成了第二轮的确认。之后L1再从第一步中将军发给自己的vi和第二轮中确定的5个值中投出自己的决定。

其余的L2，L3.等等也进行同样的步骤。

其实算法还是挺复杂的，老猫也是花了很长时间，查了很多资料才搞懂的。知道你们可能还是看不懂。再看看下面的图解吧。

这里需要注意的是：Lamport提出的容错的两个条件。

IC1：即所有的忠诚的副官要遵守同一个命令，即达成一致；

IC2：假如将军是忠诚的，那么每一个忠诚的副官都应该按照将军的意思行事。

这里将军是叛徒，所以只要满足IC1条件即可。同时L6也是叛徒会干扰L1-L5。

Step1 : C给L1~L6 依次发 A R A R A x  （A，R代表攻击和撤退，这里因为C是叛徒，所以可以随便发给L1-L5消息，这里只是一个例子，可以用其他的值，只要最后满足IC1就可以）

step2：以L1为例，L1会怀疑将军发给自己的消息的真假，于是他会问L2-L6的人他们收的消息是什么。所以L1收到：2R  3A   4R   5A   6A（即L2发给L1的是R，L3发给L1的是A以此类推）

同理L2-L6收到消息如下图：

Step3：其实在第三步中 L1会依次确认在step2中, L2~L6发给自己的信息. 例如确认L2时会问L3-L6,在Step2中L2发给你们了什么，最后得到 R,R,R,A（因为L6这时候肯定又说谎）

再结合自己的R,L1确定在Step2中收到L2发来的是R，之后又确认了L3-L6。大家可以自己在草稿纸上画出。

其实因为L1-L5都是忠诚，他们不会在Step2中撒谎，所以只需投票L6即可 ，(A R A R A )是L6发给L1-L5的信息，最后投出发的是A，将A修改到step2中L1-L5收到的，信息中其余的信息可以不用改。

最后得到L1-L5均是4个A，2个R。以L1为例=R  A  R  A  A  A

即L1~L5达成了一致。所以他们最后的行动是A，攻击。

好了，今天的算法讲解就到这里了，后面有时间老猫还会给你们讲讲拜占庭将军问题的签名算法。

大家对今天内容有什么疑问都可以留言提出来，老猫会一一解答。

声明：币圈有风险，投资需谨慎，本文纯属个人观点，不作任何投资意见；