4.2 拜占庭将军问题

拜占庭将军问题

为什么称之为拜占庭将军问题

I have long felt that, because it was posed as a cute problem about philosophers seated around a table, Dijkstra’s dining philosopher’s problem received much more attention than it deserves. (For example, it has probably received more attention in the theory community than the readers/writers problem, which illustrates the same principles and has much more practical importance.) I believed that the problem introduced in [41] was very important and deserved the attention of computer scientists. The popularity of the dining philosophers problem taught me that the best way to attract attention to a problem is to present it in terms of a story.

上文摘自拜占庭将军问题（Byzantine Generals Problem）的作者 Leslie Lamport 的一段说明。

简要概述就是，作者觉得相比于枯燥的问题，给问题加上一个故事性的背景，更能赢得大家对这个问题的关注。

什么是拜占庭将军问题

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

但是在上述的场景中，会出现很严重的问题，军队中会出现叛徒，他们可能会进行错误的投票，或者进行选择性的投票。举个例子，如果有9位将军进行投票，其中有1位叛徒。那么就是8个忠诚和1个奸臣，其中4个忠臣投了进攻，而另外4个忠臣投了撤退，这个时候奸臣可能会进行错误的指引，给4个投了进攻的忠臣发送了进攻的信号，而给4个撤退的忠臣发送了撤退的信号，这样子两边收到的信号都是5人投票，因为进攻票收到5票，撤退票也收到了5票，而我们遵循少数服从多数的原则。结果会有4个忠臣进攻，而4个忠臣撤退，造成军队之间一致性的割裂。

假设所有将军都是忠臣，但是将军的信号传达是需要信使的，我们很难保证说在信使传达口令的过程中被人截胡，从而替换消息。

这就是拜占庭将军问题。

拜占庭将军问题

忠臣 -- 一个简单场景

这个场景是一个很简单case。在一个分布式选举的场景中，至少需要满足大于3个节点，且大多数情况下节点为奇数个，因为要满足我们少数服从多数的场景，如果是偶数个节点的话，容易出现选票相同的情况。上述的场景全部都是忠臣，其中一个忠臣发出了撤退，而另外两个忠臣发出了进攻。所以结果是三个忠臣都收到了2进攻，1撤退的信号。（因为还要节点本身发出的信号类型）所以少数服从多数，大家达成一致，进行进攻。

忠臣与奸臣 -- 场景升级

在这个场景中，我们引入了奸臣这个节点，现在变成了两个忠臣和一个奸臣。可以看到，奸臣给两个忠臣分别发送了不同的信号。其中一个忠臣收到了2个进攻信号，1个撤退信号；另一个收到了2个撤退信号，1个进攻信号（同理，包含了节点本身的信号）。这样子就会造成军队割裂。

如何解决拜占庭将军问题

口信协定方案 -- 简单场景

在这个方案中，我们可以通过增加将军和一些规则来实现。

如图所示，我们增加了一个指挥官节点，我们可以看作指挥官是忠臣，因为所有的信号我们都是依赖指挥官去下发的。首先由我们的指挥官去下发进攻信号给三个节点。但是在那之前，我们有一个约定俗成的规则，如果没有收到信号，会默认接受到撤退信号。因为我们知道，节点通信是不可靠的，所以要先预先达成一个默认的规则。

在第二阶段，我们可以看到，虽然奸臣发送了错误的撤退信号，但是军队的整体作战还是统一的。两个忠臣和一个奸臣都收到了2个进攻1个撤退的信号，所以四位将军可以一起发起进攻。

口信协定方案 -- 场景升级

其实刚刚的场景，我们都是通过依托指挥官发布可靠信号来完成的。那么我们可以换位思考一下，如果指挥官是奸臣呢？

在第一阶段，由奸臣扮演指挥官，分别向两个忠臣发送了进攻信号，向一个忠臣发送了撤退信号。

在第二阶段，因为两个忠臣分别向其他的节点发送进攻信号，而另一个节点分别向其他的节点发送撤退信号。可以看到三个节点，都收到了2个进攻，1个撤退。所以军队收到的指令是一致的。

口信协定方案 -- 定理

Lamport 在论文中有采用归纳法证明口信协定的定理 如果有m个奸臣，则奸臣+忠臣的总数不能少于3m+1，这样子就可以解决拜占庭将军问题。

具体的推理过程，不在这里展开赘述。感兴趣的可以去看一下 paper 原文，具体链接会在文末贴出，paper 写的比较通俗易懂，大家可以花时间去读一下，是个不错的收获。

其实口信协定方案存在很大的弊端，它只能保证最终指令的一致性，但是不能保证指令的准确性。特别是以奸臣为指挥官的场景，我们无法知道指令的可靠性，因为我们不能判别出哪个节点是奸臣。

上文中的场景，其实是一个粒度最小的场景，是基于解决拜占庭将军问题最小粒度的解决方案出发的，即消息一致和少数服从多数。在 paper 中 Lamport 提到，如果奸臣数量是 m，那么需要经历 m + 1轮的消息同步，比如刚刚的场景，我们经历了 step 1 和 step 2 两次同步。其实复杂场景的口信协定方案是一个递归过程，假设我们有 m 个奸臣节点，需要经历 OM(m + 1)、OM(m) ... OM(1) 的计算。在论文中也有详细的推倒过程，其实上述的几个图示已经可以很清晰的表明简单的模型过程了。