1982 年，兰伯特在其论文 “拜占庭将军问题”中，提出了两种解决拜占庭问题的算法，一种是口头协议，一种是书面协议。书面协议要签名，消息传递过程中无法篡改，而口头协议则无签名，奸细可以随便篡改和传递口信。
这两种协议，都有一个前提：信息的传递是没有问题的。将军们之间可以两两直接通信。
比较后来的种种共识协议，口头协议显得很原始，通信量及运算量都巨大，所以工程实现上很难，也用不起来。但口头协议的思想，是各种共识协议的一个源头。我有一种感觉，其他共识协议，都是基于口头协议的。
口头协议，能够解决奸细数量不超过 m，将军数量为 3m+1 情况下的共识达成问题。
兰伯特的论文中，对口头协议算法的描述，非常简单，只用了几段文字。网上有很多作者进行了解释，但由于涉及到递归的使用，总是难以理解。且网上的例子，只有 m = 1 和 m = 2 两种情况，这两种情况都是特例，算不上一般的情况。
本文用奸细 m = 3， 将军总数为 n = 3x3+1 = 10 来举例解释。大家更容易理会递归算法的原理。
下图是共识达成的运算和通信总体流程，本图只画出每步算法的头一条，但也足见其复杂了。
由于奸细 m = 3，所以共识达成要经历 OM（3）、OM(2)、OM(1)、OM(0) 几轮计算。正是这几轮递归运算，令人一头雾水。
MO(3)
先说 OM（3）算法，在此阶段，作为司令官的将军，这里假设为 C，向其余 9 名将军发送命令，假设命令为 "进攻"，以 A 代表。
此时将军 L1，收到了命令 A。 将军 L1 该如何决策呢？
若是已知司令官 C 并非奸细，那么就简单了，C 会给所有将军一致的命令 A。 L1.......L9 只需遵守即可，其中三位奸细将军 L7， L8，L9 爱干嘛干嘛，忠诚将军不必去管他们三人。很直接就符合了 IC2 和 IC1：
IC1. 所有忠诚副官遵守同一命令；
IC2. 如果司令官是忠诚的，每个忠诚的副官遵守他的命令。
但是，且慢，由于此时将军 L1 并不清楚司令官 C 是不是奸细，他不能冒然用 A 作为行动命令，那也太没脑子了。
将军之间互相问询，然后做简单的多数统计也不行，因为若司令官 C 是奸细，他向 4 位忠诚将军发 A， 向另外 3 位发撤退 R，然后其他两位奸细将军分别给 4 位忠诚将军发 A，3 位发 R，那么结果就是 4 位忠诚将军进攻，3 位忠诚将军撤退。
所以才需要 OM（3）、OM(2)、OM(1)、OM(0) 算法。
好了，此时将军 L1 得到了司令官 C 的命令 A。按照 OM(3) 算法，他给自己该采取的命令取值为：
L1-V = Majority (A, L1:L2-OM(2), L1:L3-OM(2), L1:L4-OM(2), L1:L5-OM(2), L1:L6-OM(2), L1:L7-OM(2), L1:L8-OM(2), L1:L9-OM(2))
他用了 Majority 统计函数，也就是取最多的值。
其中第一个值 A 来自司令官 C。 但第二个值，L1并没有直接用将军 L2 发给他的命令，因为将军 L2 可能是奸细。将军 L1 要求将军 L2 参与 OM（2）算法，并把 L2 在 OM（2）算法的结果发过来，L 1 会用这个结果填入L1:L2-OM(2)，以运行 Majority 函数。
同样的，L1也告诉 L3......L9 将军们，让他们都参与到 OM（2）中。所以，在此时， 将军 L1，并不知道自己该采用什么命令。同样的， 将军 L2.....L9，都不知道怎么该采用什么，但都为自己列出了函数，见下图：
其中 L7，L8，L9 因为是奸细，所以标红，他们压根不会运算，会给出捣乱的任意值。
那么我们看看 OM（2）算法。
OM(2)
在 OM(2) 算法中，将司令官 C 忘掉吧，他不参加。
在 OM(2) 中，首先将军 L1 成为司令官，向 L2......L9 发送命令。而 L2.....L9 则需要统计出自己的命令。
在 L1 作为司令官发号命令，L2 在 OM(2) 中的取值函数记录为：
L1:L2-OM(2) = Majority (A, L2:L1:L3-OM(1), L2:L1:L4-OM(1), L2:L1:L5-OM(1), L2:L1:L6-OM(1), L2:L1:L7-OM(1), L2:L1:L8-OM(1), L2:L1:L9:OM(1))
同样， L3....L9 在 L1 作为司令官发号的 OM(2) 中各自取值如下图：
然而，请注意，这并非 OM(2) 的全部，这只是 OM(2) 运算中，L1作为司令官的部分，是为了计算 OM(3) 中的第一行：
L1-V = Majority (A, L1:L2-OM(2), L1:L3-OM(2), L1:L4-OM(2), L1:L5-OM(2), L1:L6-OM(2), L1:L7-OM(2), L1:L8-OM(2), L1:L9-OM(2))
所以，在 OM(2) 轮中，L1......L9 都要轮流做司令官，分别为 OM(3) 中的 L1-V.....L1-9 计算函数中的值。
让我们回到：
L1:L2-OM(2) = Majority (A, L2:L1:L3-OM(1), L2:L1:L4-OM(1), L2:L1:L5-OM(1), L2:L1:L6-OM(1), L2:L1:L7-OM(1), L2:L1:L8-OM(1), L2:L1:L9:OM(1))
如上一轮 OM(3)，L2 只有一个确定值 A 来自司令官 L1, 其他的值，L2 都不敢相信，于是 L2 告诉 L3......L9，你们跟我进入到 OM(1) 算法中去吧，把你们在 OM(1) 运算结果告诉我，我用来计算 L1:L2-OM(2)。
于是 L3 就要计算在 L1 为司令官这一轮中的 OM(1)，而这个 OM(1)，要忘掉 L1，将 L2 当做司令官。L3的取值记录为 L2:L1:L3-OM(1)。
OM(1)
OM（1）如下图：
此时 L2 为司令官，发送了 A 给 L3......L9。 L3 要执行 OM(1) 运算：
L2:L1:L3-OM(1) = Majority (A, L3:L2:L1:L4-OM(0), L3:L2:L1:L5-OM(1), L3:L2:L1:L6-OM(1), L3:L2:L1:L7-OM(1), L3:L2:L1:L8-OM(1), L3:L2:L1:L9-OM(1))
其中，A 为 L2 发给 L3 的值。而 L4 的值，L3 不能直接相信，继续，让 L 4 的值为 L3:L2:L1:L4-OM(0)，进入 OM(0)，而 OM(0) 非常简单：
OM(0)
OM(0)算法
(1) 司令发送他的值给每个副官；
(2) 如果副官收到司令的值，使用这个值；否则，使用默认值——“撤退”。
这就是说呢，到了 OM(0) 才终于轻松了，司令给你什么值你就用什么好了。
我们还是画出 OM(0)。
所以，L3:L2:L1:L4-OM(0) = A。
钻了这么好几轮，终于有个值是确定的了！
回到 OM（1），则 L2:L1:L3-OM(1) = Majority（A,A,A,A,X,Y,Z）= A
同样，可以算出 L2:L1:L4-OM(1), L2:L1:L5-OM(1), L2:L1:L6-OM(1), L2:L1:L7-OM(1), L2:L1:L8-OM(1), L2:L1:L9:OM(1)。
于是 L1:L2-OM(2) 的值便得出来了。
同样可以得到 L1:L2-OM(2), L1:L3-OM(2), L1:L4-OM(2), L1:L5-OM(2), L1:L6-OM(2), L1:L7-OM(2), L1:L8-OM(2), L1:L9-OM(2) 的值。
于是 L1-V 就得到了。
同样，L1-V，L2-V, L3-V, L4-V, L5-V, L6-V, L7-V, L8-V, L9-V。
9 个将军，除了三个叛徒，能够达成一致。
共计 9 x 8 x 7 x 6 = 3024 次运算。共计 4000 次通信。所以说，用在实际工程中，是不现实的。
至于证明过程，因为涉及到归纳法，所以也是很难懂，数学思维不行，真是无奈的悲哀。
唉，人们总是说自己数学底子不好的，还是脸皮太厚了，听起来好像是年轻时荒废了，实际上是智商不够，怎么学都学不会的。
网友评论