图码并茂一文看懂拜占庭将军问题OM版

如果对区块链技术有所了解，大概对拜占庭问题并不陌生，起码很耳熟。本文只讨论拜占庭问题本身。

问题介绍

该问题最早由Lamport大神于1982年发表的论文。论文描述的是分布式系统里，如何设计通讯协议，使得各节点能最终达成一致，后又被称为“拜占庭容错”。

经典的拜占庭将军问题分两大类，一是只能口头传递信息，二是可以书面下达命令且不可伪造。本文只讨论口头传递信息的情况（Oral Messages）。

问题简化版的描述为：

n个将军各自带兵包围敌军，兵临城下，敌军防守严密，我方必须有足够的兵力同时发动进攻，才能歼灭敌军，否则如果进攻兵力不足，会白白送死，而且会使我方元气大伤而敌军会趁势反扑。据可靠消息，敌军已经策反了m个将军，因此，将军们约定凌晨4点开始军事行动，要么一起进攻，要么一起撤退，命令由主帅决定（主帅已事先选定，大家公认。剧透一下：这个协议的精妙在于，其实无论主帅是谁，所有忠臣都将作出一致的决策）。

1. 将军们无法坐在一起商量，互相通讯只能靠互派信使，假设信使都能保证将信安全送给任意将军，不会被俘虏，且不会篡改信的内容；
2. 信的内容包含“谁”和“命令”，比如“主帅a下令副将c进攻”，“c说：b告诉c说主帅a下令副将b撤退”，等等。
3. 主帅只能通过信使向各副将下达命令；
4. 任意2个将军之间都可以进行任意多次通信；
5. 其中n-m个忠臣一定会严格执行命令和传递命令，所有忠臣一起进攻，依然能获胜；
6. 其中m个内奸会恶意篡改并传递命令，且最后到行动时间，一定不会出兵。

问：如何制定传信的规则，使得最后所有忠臣都根据收到的信息独立决策，并能结果一致（都进攻或都撤退）？规则对内奸数m和总将军数n有什么限制？

这个问题有点绕，第一次看，很可能要么会觉得太简单了，要么觉得条件过于复杂，我们来看些例子，感受一下问题的真实难度：

举个例子1，将军a、b、c三人，c被策反。主帅a向b和c发送attack命令，则a、b会一起进攻，胜！

换个例子2，a、b、c、d、e五人，主帅a被策反。主帅a向b、c发送attack命令进攻，向d、e发送retreat命令撤退，则将只有b，c发动进攻，而其他忠臣会执行retreat命令撤退，最后b和c兵败！

例2中如果b把“a下令b进攻”的消息传给d，则d分别收到“a下令d撤退”和“b说a下令b进攻”的消息，而决定改为进攻。同理，e也因此改为进攻，从而b、c、d、e一起进攻，胜！

Makes sense?

嗯，敝人应该听到了yes！

只有先搞清楚问题本身，才能感受到下面的算法之美！

先扯些故事背景，再上算法详解！

来历与背景

论文可以从 https://www.microsoft.com/en-us/research/publication/byzantine-generals-problem/ 下载

wikipedia上的中文翻译如下：

一组拜占庭将军分别各率领一支军队共同围困一座城市。为了简化问题，将各支军队的行动策略限定为进攻或撤离两种。因为部分军队进攻部分军队撤离可能会造成灾难性后果，因此各位将军必须通过投票来达成一致策略，即所有军队一起进攻或所有军队一起撤离。因为各位将军分处城市不同方向，他们只能通过信使互相联系。在投票过程中每位将军都将自己投票给进攻还是撤退的信息通过信使分别通知其他所有将军，这样一来每位将军根据自己的投票和其他所有将军送来的信息就可以知道共同的投票结果而决定行动策略。

拜占庭是什么？

如果阁下您你和我一样曾经痴迷帝国时代，应该对拜占庭的城堡和抛石机印象深刻吧，拜占庭的建筑和科技在当时是相当先进的。

拜占庭要从罗马帝国说起，后来帝国分成西罗马和东罗马。君士坦丁大帝迁都君士坦丁堡，史称拜占庭帝国（395年～1453年），又名东罗马帝国。君士坦丁大帝是首位信奉基督教的罗马皇帝。西罗马信奉天主教，东罗马信奉东正教。拜占庭后被奥斯曼土耳其帝国所灭。

那这些和这个分布式系统的拜占庭将军问题有什么关系呢？其实是Lamport大神为这个枯燥的计算机问题故意添加了人文色彩！

Leslie Lamport是2013年图灵奖获得者。著名的Paxos算法发明人。Paxos在工业界被广泛使用，比较有名的包括Google Chubby (被用在Big table, Spanner, Megastore), IBM SAN Volume Controller, 微软Bing的Autopilot cluster management service, Neo4j HA graph database。

Paxos也是充满古希腊色彩，当时评审要求把关于古希腊的部分去掉，被Lamport拒绝，因此也大大推迟了算法的发表。有机会下次整一篇Paxos。

如果拜占庭问题出一个中国历史版的，可以是六国伐秦，各路诸侯伐董卓，诸葛亮安居平五路，等等。

OM算法

接下来开始讲算法

论文中关于算法的具体描述如下：

翻译如下：

设n个将军，其中最多m个内奸，如果n > 3m，则执行OM(m)算法能保证作战行动一致。

接收与决策：最终每个将军都会收到各种一手二手的命令信息，然后类似民主多数投票，选出多数(majority)。如果进攻和撤退对半，则选择事先已商量好的默认作战计划（撤退RETREAT）。

下面的OM算法是关于1) 如何制定规则（协议）传递一手二手命令，2) 如何根据收到的一手二手命令作决策。

OM(0)算法

1. 发送：主帅(commander)把命令(ATTACK或RETREAT)发给各副将(lieutenant)。
2. 接收：各副将执行从主帅收到的命令。

OM(m), m>0

1. 发送：主帅把命令发给各副将。
2. 递归发送：设V(i)为副将i从主帅收到的命令，副将i递归执行OM(m-1)，即副将i以下一轮主帅的方式把V(i)发给其他未经手此命令的副将们。
3. 接收：经过步2的操作，如果本轮由p个将军参与，每位副将收到主帅1的一手命令和其他p-2副将的二手命令，决策为majority(V(1), V(2), …, V(p-1))。

乍眼看或许有点绕，先举个简单的例子感受一下。

设n=4, m=1, 4个将军，其中1个内奸。如果主帅是忠臣，那显然一旦发起进攻命令，另外2位忠臣会响应，则最后3支军队出击，胜！

如果主帅a是奸臣，另外3副将b, c, d是忠臣。则OM(1)操作的时候，主帅令b进攻，c和d撤退。可以用如下符号描述：

OM(1) round:

b: [a], Attack // 表示b收到a的命令，Attack；以下同理。

c: [a], Retreat

d: [a], Retreat

然后各副将递归执行OM(0)

OM(0) round:

b: [a], Attack

b: [a c], Retreat // 表示b收到c说收到a的命令，Retreat；以下同理。

b: [a d], Retreat

c: [a], Retreat

c: [a b], Attack

c: [a d], Retreat

d: [a], Retreat

d: [a b], Attack

d: [a c], Retreat

开始接收和决策：(注意关键细节，要把本轮的一手和二手一起做majority)

OM(1) round:

b: majority(Attack, Retreat, Retreat) ==> Retreat

c: majority(Retreat, Attack, Retreat) ==> Retreat

d: majority(Retreat, Attack, Retreat) ==> Retreat

最后，全军一致撤退。

下面图示一下n=7, m=2的情况。

做个gif好累啊…

命令传递路线如下图：

发送

OM(2): 主帅1发送给2, 3, 4, 5, 6, 7;

OM(1): 各副将发送给其他副将，比如2发送给3, 4, 5, 6, 7;

OM(0): 各副将发送给其他副将，比如3把[1, 2]发送给4, 5, 6, 7, 把[1, 4]发送给2, 5, 6, 7.

算法复杂度，(n-1)(n-2)(n-3)。

接收与决策如下：

接收

以2为例，类似树结构层层剪枝向上的过程如下：

OM(1):

[1, 3] = majority([1, 3], [1, 3, 4], [1, 3, 5], [1, 3, 6], [1, 3, 7])

[1, 4] = majority([1, 4], [1, 4, 3], [1, 4, 5], [1, 4, 6], [1, 4, 7])

[1, 5] = majority([1, 5], [1, 5, 3], [1, 5, 4], [1, 5, 6], [1, 5, 7])

[1, 6] = majority([1, 6], [1, 6, 3], [1, 6, 4], [1, 6, 5], [1, 6, 7])

[1, 7] = majority([1, 7], [1, 7, 3], [1, 7, 4], [1, 7, 5], [1, 7, 6])

OM(2):

[1] = majority([1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [1])

好，根据上面的例子再回看抽象的算法描述，就很容易懂了。当然，算法的魅力就在于抽象，不抽象怎敢称算法？

讲完了！

附录

以下为程序模拟n=7, m=2, 且主帅是内奸的例子，最后5位忠臣作出一致的进攻决策！

贴代码不太好看，就贴个运行结果算了，反正可以看这个例子里的每一步结果。

##### send #####
====== OM(1) ======
id=[2], isTraitor=[false]
{path=[1], Attack}
{path=[1 3], Attack}
{path=[1 4], Attack}
{path=[1 5], Retreat}
{path=[1 6], Retreat}
{path=[1 7], Attack}
id=[3], isTraitor=[false]
{path=[1], Attack}
{path=[1 2], Attack}
{path=[1 4], Attack}
{path=[1 5], Retreat}
{path=[1 6], Retreat}
{path=[1 7], Attack}
id=[4], isTraitor=[false]
{path=[1], Attack}
{path=[1 2], Attack}
{path=[1 3], Attack}
{path=[1 5], Retreat}
{path=[1 6], Retreat}
{path=[1 7], Retreat}
id=[5], isTraitor=[false]
{path=[1], Retreat}
{path=[1 2], Attack}
{path=[1 3], Attack}
{path=[1 4], Attack}
{path=[1 6], Retreat}
{path=[1 7], Retreat}
id=[6], isTraitor=[false]
{path=[1], Retreat}
{path=[1 2], Attack}
{path=[1 3], Attack}
{path=[1 4], Attack}
{path=[1 5], Retreat}
{path=[1 7], Attack}
id=[7], isTraitor=[true]
{path=[1], Retreat}
{path=[1 2], Attack}
{path=[1 3], Attack}
{path=[1 4], Attack}
{path=[1 5], Retreat}
{path=[1 6], Retreat}
====== OM(0) ======
id=[2], isTraitor=[false]
{path=[1], Attack}
{path=[1 3], Attack}
{path=[1 4], Attack}
{path=[1 5], Retreat}
{path=[1 6], Retreat}
{path=[1 7], Attack}
{path=[1 4 3], Attack}
{path=[1 5 3], Retreat}
{path=[1 6 3], Retreat}
{path=[1 7 3], Attack}
{path=[1 3 4], Attack}
{path=[1 5 4], Retreat}
{path=[1 6 4], Retreat}
{path=[1 7 4], Retreat}
{path=[1 3 5], Attack}
{path=[1 4 5], Attack}
{path=[1 6 5], Retreat}
{path=[1 7 5], Retreat}
{path=[1 3 6], Attack}
{path=[1 4 6], Attack}
{path=[1 5 6], Retreat}
{path=[1 7 6], Attack}
{path=[1 3 7], Retreat}
{path=[1 4 7], Retreat}
{path=[1 5 7], Attack}
{path=[1 6 7], Attack}
id=[3], isTraitor=[false]
{path=[1], Attack}
{path=[1 2], Attack}
{path=[1 4], Attack}
{path=[1 5], Retreat}
{path=[1 6], Retreat}
{path=[1 7], Attack}
{path=[1 4 2], Attack}
{path=[1 5 2], Retreat}
{path=[1 6 2], Retreat}
{path=[1 7 2], Attack}
{path=[1 2 4], Attack}
{path=[1 5 4], Retreat}
{path=[1 6 4], Retreat}
{path=[1 7 4], Retreat}
{path=[1 2 5], Attack}
{path=[1 4 5], Attack}
{path=[1 6 5], Retreat}
{path=[1 7 5], Retreat}
{path=[1 2 6], Attack}
{path=[1 4 6], Attack}
{path=[1 5 6], Retreat}
{path=[1 7 6], Attack}
{path=[1 2 7], Retreat}
{path=[1 4 7], Retreat}
{path=[1 5 7], Attack}
{path=[1 6 7], Retreat}
id=[4], isTraitor=[false]
{path=[1], Attack}
{path=[1 2], Attack}
{path=[1 3], Attack}
{path=[1 5], Retreat}
{path=[1 6], Retreat}
{path=[1 7], Retreat}
{path=[1 3 2], Attack}
{path=[1 5 2], Retreat}
{path=[1 6 2], Retreat}
{path=[1 7 2], Attack}
{path=[1 2 3], Attack}
{path=[1 5 3], Retreat}
{path=[1 6 3], Retreat}
{path=[1 7 3], Attack}
{path=[1 2 5], Attack}
{path=[1 3 5], Attack}
{path=[1 6 5], Retreat}
{path=[1 7 5], Retreat}
{path=[1 2 6], Attack}
{path=[1 3 6], Attack}
{path=[1 5 6], Retreat}
{path=[1 7 6], Attack}
{path=[1 2 7], Attack}
{path=[1 3 7], Retreat}
{path=[1 5 7], Attack}
{path=[1 6 7], Attack}
id=[5], isTraitor=[false]
{path=[1], Retreat}
{path=[1 2], Attack}
{path=[1 3], Attack}
{path=[1 4], Attack}
{path=[1 6], Retreat}
{path=[1 7], Retreat}
{path=[1 3 2], Attack}
{path=[1 4 2], Attack}
{path=[1 6 2], Retreat}
{path=[1 7 2], Attack}
{path=[1 2 3], Attack}
{path=[1 4 3], Attack}
{path=[1 6 3], Retreat}
{path=[1 7 3], Attack}
{path=[1 2 4], Attack}
{path=[1 3 4], Attack}
{path=[1 6 4], Retreat}
{path=[1 7 4], Retreat}
{path=[1 2 6], Attack}
{path=[1 3 6], Attack}
{path=[1 4 6], Attack}
{path=[1 7 6], Attack}
{path=[1 2 7], Retreat}
{path=[1 3 7], Retreat}
{path=[1 4 7], Attack}
{path=[1 6 7], Retreat}
id=[6], isTraitor=[false]
{path=[1], Retreat}
{path=[1 2], Attack}
{path=[1 3], Attack}
{path=[1 4], Attack}
{path=[1 5], Retreat}
{path=[1 7], Attack}
{path=[1 3 2], Attack}
{path=[1 4 2], Attack}
{path=[1 5 2], Retreat}
{path=[1 7 2], Attack}
{path=[1 2 3], Attack}
{path=[1 4 3], Attack}
{path=[1 5 3], Retreat}
{path=[1 7 3], Attack}
{path=[1 2 4], Attack}
{path=[1 3 4], Attack}
{path=[1 5 4], Retreat}
{path=[1 7 4], Retreat}
{path=[1 2 5], Attack}
{path=[1 3 5], Attack}
{path=[1 4 5], Attack}
{path=[1 7 5], Retreat}
{path=[1 2 7], Retreat}
{path=[1 3 7], Retreat}
{path=[1 4 7], Retreat}
{path=[1 5 7], Retreat}
id=[7], isTraitor=[true]
{path=[1], Retreat}
{path=[1 2], Attack}
{path=[1 3], Attack}
{path=[1 4], Attack}
{path=[1 5], Retreat}
{path=[1 6], Retreat}
{path=[1 3 2], Attack}
{path=[1 4 2], Attack}
{path=[1 5 2], Retreat}
{path=[1 6 2], Retreat}
{path=[1 2 3], Attack}
{path=[1 4 3], Attack}
{path=[1 5 3], Retreat}
{path=[1 6 3], Retreat}
{path=[1 2 4], Attack}
{path=[1 3 4], Attack}
{path=[1 5 4], Retreat}
{path=[1 6 4], Retreat}
{path=[1 2 5], Attack}
{path=[1 3 5], Attack}
{path=[1 4 5], Attack}
{path=[1 6 5], Retreat}
{path=[1 2 6], Attack}
{path=[1 3 6], Attack}
{path=[1 4 6], Attack}
{path=[1 5 6], Retreat}
##### decide #####
## decision [id=1] = Retreat
===== printMessageArray =====
{[1] Attack}
{[1 3] Attack}
{[1 4] Attack}
{[1 5] Retreat}
{[1 6] Retreat}
{[1 7] Attack}
{[1 4 3] Attack}
{[1 5 3] Retreat}
{[1 6 3] Retreat}
{[1 7 3] Attack}
{[1 3 4] Attack}
{[1 5 4] Retreat}
{[1 6 4] Retreat}
{[1 7 4] Retreat}
{[1 3 5] Attack}
{[1 4 5] Attack}
{[1 6 5] Retreat}
{[1 7 5] Retreat}
{[1 3 6] Attack}
{[1 4 6] Attack}
{[1 5 6] Retreat}
{[1 7 6] Attack}
{[1 3 7] Retreat}
{[1 4 7] Retreat}
{[1 5 7] Attack}
{[1 6 7] Attack}
===== printMessageArray =====
{[1] Attack}
{[1 3] Attack}
{[1 4] Attack}
{[1 5] Retreat}
{[1 6] Retreat}
{[1 7] Attack}
===== printMessageArray =====
{[1] Attack}
## decision [id=2] = Attack
===== printMessageArray =====
{[1] Attack}
{[1 2] Attack}
{[1 4] Attack}
{[1 5] Retreat}
{[1 6] Retreat}
{[1 7] Attack}
{[1 4 2] Attack}
{[1 5 2] Retreat}
{[1 6 2] Retreat}
{[1 7 2] Attack}
{[1 2 4] Attack}
{[1 5 4] Retreat}
{[1 6 4] Retreat}
{[1 7 4] Retreat}
{[1 2 5] Attack}
{[1 4 5] Attack}
{[1 6 5] Retreat}
{[1 7 5] Retreat}
{[1 2 6] Attack}
{[1 4 6] Attack}
{[1 5 6] Retreat}
{[1 7 6] Attack}
{[1 2 7] Retreat}
{[1 4 7] Retreat}
{[1 5 7] Attack}
{[1 6 7] Retreat}
===== printMessageArray =====
{[1] Attack}
{[1 2] Attack}
{[1 4] Attack}
{[1 5] Retreat}
{[1 6] Retreat}
{[1 7] Attack}
===== printMessageArray =====
{[1] Attack}
## decision [id=3] = Attack
===== printMessageArray =====
{[1] Attack}
{[1 2] Attack}
{[1 3] Attack}
{[1 5] Retreat}
{[1 6] Retreat}
{[1 7] Retreat}
{[1 3 2] Attack}
{[1 5 2] Retreat}
{[1 6 2] Retreat}
{[1 7 2] Attack}
{[1 2 3] Attack}
{[1 5 3] Retreat}
{[1 6 3] Retreat}
{[1 7 3] Attack}
{[1 2 5] Attack}
{[1 3 5] Attack}
{[1 6 5] Retreat}
{[1 7 5] Retreat}
{[1 2 6] Attack}
{[1 3 6] Attack}
{[1 5 6] Retreat}
{[1 7 6] Attack}
{[1 2 7] Attack}
{[1 3 7] Retreat}
{[1 5 7] Attack}
{[1 6 7] Attack}
===== printMessageArray =====
{[1] Attack}
{[1 2] Attack}
{[1 3] Attack}
{[1 5] Retreat}
{[1 6] Retreat}
{[1 7] Attack}
===== printMessageArray =====
{[1] Attack}
## decision [id=4] = Attack
===== printMessageArray =====
{[1] Retreat}
{[1 2] Attack}
{[1 3] Attack}
{[1 4] Attack}
{[1 6] Retreat}
{[1 7] Retreat}
{[1 3 2] Attack}
{[1 4 2] Attack}
{[1 6 2] Retreat}
{[1 7 2] Attack}
{[1 2 3] Attack}
{[1 4 3] Attack}
{[1 6 3] Retreat}
{[1 7 3] Attack}
{[1 2 4] Attack}
{[1 3 4] Attack}
{[1 6 4] Retreat}
{[1 7 4] Retreat}
{[1 2 6] Attack}
{[1 3 6] Attack}
{[1 4 6] Attack}
{[1 7 6] Attack}
{[1 2 7] Retreat}
{[1 3 7] Retreat}
{[1 4 7] Attack}
{[1 6 7] Retreat}
===== printMessageArray =====
{[1] Retreat}
{[1 2] Attack}
{[1 3] Attack}
{[1 4] Attack}
{[1 6] Retreat}
{[1 7] Attack}
===== printMessageArray =====
{[1] Attack}
## decision [id=5] = Attack
===== printMessageArray =====
{[1] Retreat}
{[1 2] Attack}
{[1 3] Attack}
{[1 4] Attack}
{[1 5] Retreat}
{[1 7] Attack}
{[1 3 2] Attack}
{[1 4 2] Attack}
{[1 5 2] Retreat}
{[1 7 2] Attack}
{[1 2 3] Attack}
{[1 4 3] Attack}
{[1 5 3] Retreat}
{[1 7 3] Attack}
{[1 2 4] Attack}
{[1 3 4] Attack}
{[1 5 4] Retreat}
{[1 7 4] Retreat}
{[1 2 5] Attack}
{[1 3 5] Attack}
{[1 4 5] Attack}
{[1 7 5] Retreat}
{[1 2 7] Retreat}
{[1 3 7] Retreat}
{[1 4 7] Retreat}
{[1 5 7] Retreat}
===== printMessageArray =====
{[1] Retreat}
{[1 2] Attack}
{[1 3] Attack}
{[1 4] Attack}
{[1 5] Retreat}
{[1 7] Attack}
===== printMessageArray =====
{[1] Attack}
## decision [id=6] = Attack
## decision [id=7] = Retreat
win = [true] <== num of generals: [7], num of attackers: [5]