拜占庭问题 口头协议递归算法的思考

第12章 拜占庭容错
这篇文章中，我们大概介绍了拜占庭问题要解决的问题。但是关于口头协议的递归算法本身，之后我产生了很大的困惑。
在经过了一整晚的阅读理解摸索之后，大概明白了这边递归算法是如何运作的。
相关JAVA代码实现在这里：https://github.com/yixuaz/ByzantineProblem

首先，不知道小伙伴可以先看一下李永乐讲拜占庭问题是什么？
https://www.bilibili.com/video/av78588312?from=search&seid=10588730237103569649
但是这边最后他对递归讲解草草结束了。

首先要把口头协议要解决的问题给提出来，如下

IC1：所有忠诚的副官遵守一个命令，即一致性。

IC2：若司令是忠诚的，每一个忠诚的副官遵守他发出的命令，即正确性

如果司令不是忠诚的，忠诚的副官只要遵守一个命令就为满足。

口头协议的假设

A1.每个发送的消息都会被正确的传输

A2.消息的接收者知道是发送者是谁

A3.消息的缺席可以检测出来

假设A1和A2是防止叛徒介入其他两个将军的通信中，根据A1，他无法妨碍其他两位将军发送的消息，根据A2他不能伪造消息来搅乱其他两位将军的交流。假设A3是为了防止一个叛徒通过简单的不发送消息来阻止一次决定。

image.png

一个叛变的发令者可能会决定不发送任何命令。由于下属们必须遵守相同的命令，因此这种情况下他们必须有一个默认的命令。我们使用RETREAT作为该默认命令。

这样就可以在将军是叛徒的时候依然满足上述的IC1。

  口头协议算法OM(m)
   OM(0)算法

   （1）司令将他的命令发送给每个副官。

   （2）每个副官采用从司令发来的命令；如果没有收到命令，则默认为撤退命令。

   OM(m)算法

   （1）司令将他的命令发送给每个副官。

   （2）对于每个i，vi是每个副官i从司令收到的命令，如果没有收到命令，则默认为撤退命令。副官i在OM(m-1) 中作为发令者将之发送给另外n-2 个副官。

   （3）对于每个i，和每个j ≠ i，vj 是副官i 从第2步中的副官j （使用OM(m-1)算法）发送过来的命令，如果没有收到第2步中副官j 的命令，则默认为撤退命令。最后副官i 使用majority(v1,…,vn-1)得到命令。

   其中，majority(v1,…,vn-1)代表了大多数人的命令，若不存在则默认为撤退命令。

在M=1的时候，非常容易理解，李永乐的视频里先分析透彻了。我下面重点讲一下M=2，是怎么一回事。
首先这个算法要发的消息数量应该是n^m

image.png

首先视频里讲到了，5和6 是叛徒的情况。

image.png

当将军给L1发送一个A的时候，L1是无法知道将军是不是叛徒，所以他还需要去问其他人将军给他发了什么（和M=1的时候一样）
这个时候L1 收集到了其他5个节点发来的消息告诉L1，将军给他们发的是什么。 但是这个消息可能也是不准的，因为存在2个叛徒。所以需要再递归一轮，那么下一轮如何发消息呢？

算法步骤里说自己作为发令者将之发送给另外n-2 个副官。
和上述L1去问其他人将军给他发什么 要结合起来思考。（这个就是难点）

其实当有2个叛徒的时候。将军发了一个消息，所有副官会主动告知其余副官将军发的是什么（这个时候，从该副官的角度，他给剩余的N-2个人（除将军和他自己）发了消息，做法和将军给他们发一样，所以这样一个等价）
那么当有2个叛徒的时候，只发一次是不够的。从L1的角度来看，他首先会收到将军发来的指令，其次他会收到其余5个副官发来的将军给他们发的指令是什么的消息。同时他自己会告诉其余5个副官，将军给L1发的是什么。
这个时候，不足以得出结论。因为有2个叛徒。

假设L1告诉其余5个副官，将军给L1发的是什么，这里的L1作为递归函数那层的将军，那么L2 收到了L1的这个消息，还需要去和L3,L4,L5,L6来确认他们收到的L1告诉他们的 ，将军给L1发的是什么的消息，来选MAJORITY作为他们得到的将军给L1的发的指令的真实值。

所以我们看到最大的区别在于，在M=1（叛徒有1个）的时候，L1告诉其他人将军给他发什么，其他人直接就记下来了，不会再去质疑。他们质疑的将军的命令是不是真实值（质疑的方式就是用MAJORITY来综合所有人收到的消息）

但是当M=2时，L1告诉其他人将军给他发什么，他们不能直接相信并记录，他们需要排除L1和将军，在内部在交换一次意见，选出MAJORITY作为这个值的真实值。

所以李永乐最后画的那张表， 他的含义是

image.png

从副官1的角度，他要得出将军的真实目的。首先他自己就是存的将军告诉他的，为A。
其次L2会告诉他将军给他发的是什么，这张图里是A，随后要L3告诉他L1（L2告诉L3的将军发给L2的指令是什么），在这张图里是第三行，第三列的那个A。
随后要L4告诉他L1（L2告诉L4的，将军发给L2的指令是什么），在这张图里是第三行，第4列的那个A。以此类推
所以L1在计算L2的值的时候，要从整个第二行取 MARJORITY来得出L2的将军告诉L2的指令的真实值是A。
递归就是这么一个过程。
所以我们可以看到当N=7,M=2
要发的消息数量是
将军发6个。
L1需要发给另外5个，将军告诉他的命令的消息。同时需要告诉另外5个（Li（i=2,3,4,5,6;排除掉K自己）告诉他的将军告诉Lk的指令）这里是5 * 4=20 条消息

所以是n^m的消息代价。