白话讲解，拜占庭将军问题

关注

发布于: 2021 年 03 月 19 日

作为服务端开发的同学，你可能听说过 Paxos、Raft 这类分布式一致性算法，也在工作中使用过 ZooKeeper、etcd 等工具来解决一致性问题。但你可能不知道，这些算法和工具解决的并不是一致性中最难的问题，要讨论这个最难的问题，这就要追溯到 Leslie Lamport 1982 年发表的著名论文《拜占庭将军问题》（The Byzantine Generals Problem ）上了。

1、拜占庭将军问题是什么？

拜占庭将军问题，其实是一个共识问题。通过比喻的方式来描述分布式一致性中一类最难的问题，这里大致叙述一下：

拜占庭帝国派出多支军队去围攻一个强大的敌人，每支军队有一个将军，但由于彼此距离较远，他们之间只能通过信使传递消息。敌方很强大，必须有超过半数的拜占庭军队一同参与进攻才可能击败敌人。在此期间，将军们彼此之间需要通过信使传递消息并协商一致后，在同一时间点发动进攻。

问题难点：困扰这些将军的问题，是他们不确定他们中是否有叛徒，叛徒可能会擅自变更进攻意向或者进攻时间。在这种状态下，拜占庭的将军们能否找到一种分布式的协议来让他们能够远程协商，从而赢取战斗？

以上，这就是著名的拜占庭将军问题。

2、问题实质推演

回顾上述问题：

一群将军想要实现某一个目标（一致进攻或者一致撤退），但是单独行动行不通，必须合作，达成共识；由于叛徒的存在，将军们不知道应该如何达到一致。

注意，这里“一致性”才是拜占庭将军问题探讨的内容，如果本来叛徒数量就已经多到了问题不可解的地步，这个就是“反叛”的问题了；同时，我们的目标是忠诚的将军能够达成一致，对于这些忠诚的将军来说，进攻或者撤退都是可以的，只要他们能够达成一致就行。

但是，仔细想想：光靠“一致性”就可以解决问题吗？

考虑一下，如果万事俱备，客观上每个忠诚的将军只要进攻了就一定能够胜利，但是却因为叛徒的存在他们都“一致性”没有进攻；反之，条件不利，将军们不应该进攻，但是却因为叛徒的存在所有人都“一致性”进攻了。所以，我们还需要提出一个“正确性”要求。

那我们该如何定义这个“正确性”呢？

我们或许可以简单地说，正确就是每个忠诚的将军都正确的表达了自己的意思，不会因为叛徒让别的将军认为忠诚的将军是叛徒而不采用他传达的消息。最终，所有忠诚的将军都能够让别的将军接收到自己的真实意图，并最终一致行动；而形式化的要求就是：“一致性”与“正确性”。

3、难题细化分析

介绍到现在，想必大家还是比较疑惑，我们以具体案例辅助解释一下：

我们把问题简化一下，假设只有三个拜占庭将军，分别为 A、B、C，他们要决定的只有一件事情：明天是进攻还是撤退。为此，将军们需要依据“少数服从多数”原则投票表决，只要有两个人意见达成一致就可以了。

举例来说，A 和 B 投进攻，C 投撤退：

那么 A 的信使传递给 B 和 C 的消息都是进攻；
B 的信使传递给 A 和 C 的消息都是进攻；
而 C 的信使传给 A 和 B 的消息都是撤退。

如此一来，三个将军就都知道进攻方和撤退方二者占比是 2 : 1 了。显而易见，进攻方胜出，第二天大家都要进攻，三者行动最终达成一致。

目前看来一切比较顺利，理解起来也非常简单。但是，假如三个将军中存在了一个叛徒呢？

叛徒的目的是破坏忠诚将军间一致性的达成，让拜占庭的军队遭受损失。

3.1 问题难点

假设 A 和 B 是忠诚将军，A 投进攻，B 投撤退，如果 C 是这个叛徒将军，那么 C 该做些什么，才能在第二天让两个忠诚的将军做出相反的决定呢？

目前看来，进攻方和撤退方现在是 1 : 1 ，无论 C 投哪一方，都会变成 2 : 1 ，一致性还是会达成。但是，作为叛徒的 C，你必然不会按照常规出牌，于是你让一个信使告诉 A 的内容是你“要进攻”，让另一个信使告诉 B 的则是你“要撤退”。

至此，A 将军看到的投票结果是：

进攻方 ：撤退方 = 2 : 1

复制代码

而 B 将军看到的投票结果是：

进攻方 ：撤退方 = 1 : 2

复制代码

截止目前，你有没有发现，明明大多数将军都是忠诚的（2/3），却被少数的叛徒（1/3）耍得团团转？

实质上，“拜占庭将军”问题的可怕之处，恰恰在此：在一致性达成的过程中，叛徒将军（恶意节点）甚至不需要超过半数，就可以破坏占据多数的正常节点一致性的达成。

3.2 狡猾的叛徒

这时候，会存在你可能不相信甚至无法接受的一种情况：在大多数将军都是忠诚的情况下，却无法抓出这个为所欲为的叛徒。

还是上面的例子，假设 A 与 B 是忠诚的将军，C 是叛徒将军。忠诚的将军经历了上次战役的失败，就已经发觉他们中出现了叛徒，但是并不知道具体是谁。

依旧是上面投票的例子，A 投进攻，B 投撤退，C 传递给 A 和 B 两种不同的消息。

现在，我们从忠诚将军 A 的视角来看一下，他是如何做决策的。

A 现在知道另外两人中可能有一个是叛徒，他收到了 B 的撤退消息和 C 的进攻消息，他应该如何分辨呢？

A 可以问一下 B：“我从 C 那儿收到的是进攻，你从 C 那儿收到的是什么？”

因为 B 是忠诚的将军，不会伪造信息，B 会告诉 A：“收到的是撤退。”

C 发送了两条不同的消息，A 现在也发现了这个问题，但是 A 现在就可以判断 C 是叛徒了么？

可悲的事情发生了，尽管忠诚的 B 说了实话，但是 A 反而对他产生了怀疑。因为从 A 的视角来看，B 和 C 的说法不一致，他无法判断：

到底是第一次发送了两条不同消息的 C 是叛徒呢?
还是明明 C 初次告知了 B 的是进攻，B 却和 A 说 C 告知的是撤退，B 是叛徒呢?

同样的情况，也会出现在 B 身上，两个忠诚的将军无法做正确的判断，而可以任意进行信息造假的叛徒 C，此时只需要再次进行消息伪造：和 A 说“B 告知我的消息是进攻”，和 B 说“A 告知我的消息是撤退”，如此一来，就可以进一步把信息搞混，从而隐藏了自己是叛徒的真相。

综上所述，我们可以得出一个结论：在拜占庭三个将军中出现一个叛徒，并且叛徒可以任意伪造消息的情况下，只要叛徒头脑清醒，他就始终无法被发现，甚至还能造成整个系统的信任危机。

根据这一结论进一步推导可以得出一个更通用的结论，如果存在 m 个叛徒将军，那么当将军总数小于或等于 3m 时（n <= 3m，m 代表叛徒将军个数)，叛徒便无法被发现，整个系统的一致性也就无法达成。

3.3 叛徒是否可被抓？

从上面的结论，可以看出，忠诚将军的人数是叛徒人数 2 倍的时候，依然不能找出叛徒，那么再多一个忠诚的将军呢？

为了简化问题，接下来假设有 4 个拜占庭将军，分别是 A、B、C、D，其中有一个是叛徒。我们依然秉承找出叛徒的关键，即判断哪个将军发送了不一致的消息。

也就是说，接下来就是和其他接收到消息的将军进行信息的同步判断：是否收到的消息不一致。

现在，将问题再进一步简化，暂不需要考虑整个投票的过程，只需要考虑一个将军向其他三个将军各发送了一条命令，忠诚将军能否对这个命令达成一致的情况，为了区分发送命令的将将军和接收消息的将军，我们将发送命令的将军称为发令将军（M），将接收命令的将军称为副官（S）。

考虑下面两个问题：

那么剩下的三个副官能不能通过相互间的信息同步找到叛徒？
或者所有忠臣间达成一致，不让叛徒的分裂想法得逞呢？

这时候就出现了两种情况：

发令将军是叛徒；
副官里有叛徒。

Case1：发令将军是叛徒

假设 D 是叛徒，向 A 和 B 发送了进攻，向 C 发送了撤退。现在，我们切入到 A 的视角。

A 问 B 和 C：“我从 D 那里收到的消息是进攻，你从 D 那里收到的是什么呢？”

B 说是进攻，C 说是撤退。

此时，从 A 的视角来看，C 和 D 对同一条消息的说法是不一致的，那么他们两个人中肯定有一个是叛徒，但是 A 无法判断的是：

D 给不同人发送了不一致的消息；
还是 C 伪造了 D 的消息。

好在，由于 A 知道最多只有一个叛徒存在。

那么根据反证法，如果 B 也是叛徒，就有两个叛徒存在，那么 B 肯定不是叛徒。

那么 A 和 B 至少在 D 发送的是进攻这一消息上，达成了一致，两者选择都是进攻。

B 也是同样的情况，现在 A 和 B 彼此建立了信任，而同样是忠诚副官的 C，最终则和真正的叛徒 D 被一同怀疑。

Case2：副官里有叛徒

假设 C 是叛徒，D 给三个副官都发送了进攻，那么叛徒 C 应该怎样同步 D 的消息，才能分裂忠诚的发令将军和忠诚副官间的关系呢？

如果将 D 的消息原样转发出去，那么这一想法实施后也就无法再去当叛徒了。如果给 A 与 B 均发送和 D 相反的撤退消息，那么就回到了前文所讲的第一种情况，A 和 B 认为 D 发送的是进攻，发送消息的 D 也认为自己发送的消息是进攻，忠臣们行动上又一次达成了一致。

然而，为了给系统增加更多的混乱，叛徒 C 决定再次发送不一致的消息，告诉 B 自己从 D 收到的是进攻，告诉 A 自己从 D 收到的是撤退。这种情况下，B 看到所有人都认为 D 是进攻，会傻傻地认为大家是个团结一致的集体，没有叛徒。而 A 会发现 C 和 D 中出现了一个叛徒，不过 A 也再次可以确认 B 是自己人。此时，A 决定再和 B 同步一轮消息，看看 C 是不是说了两个不一致的消息，这种情况下，叛徒 C 就完全暴露了。