拜占庭将军：背后的数学证明

写在前面

上一讲中拜占庭将军：分布式领域的幽灵，我们介绍了著名的拜占庭将军问题的由来及其结论：

1. 在存在 m 个叛徒将军的情况下，将军总数小于等于 3m 时，忠诚将军之间的一致性无法达成；
2. 当将军总是大于等于 3m+1 时，忠诚将军之间可以达成一致。

不知道你是否对这个结论存在疑惑，我们只是讲了一个叛徒存在的情况下三个将军无法达成一致，而四个将军可以达成一致，那到底是怎么推导出 3m 个将军无法达成一致和 3m+1 个将军能够达成一致的呢？

如果你有这个疑问，那么说明你是个治学严谨并且随时独立思考的好同学。上一讲的主要精力集中在对问题进行描述和简化上，这一讲我们就一起进入实打实的数学证明的学习。

为什么要进行数学证明呢？

你可能会有疑问，我知道结论不就好了么，为什么还要去弄明白证明过程？

我想告诉你的是：

一来是知道证明的过程，可以帮助你更好地从本质上去更深层次理解拜占庭将军整个问题和结论。

二来是拜占庭将军问题的证明过程利用到了算法领域中十分常见的解题思路，通过学习证明过程，能让你获得触类旁通的能力，之后可以解决更多的问题。

具体来说，在这一讲的证明过程中，将使用到两种方法：反证法和数学归纳法，它们是普通算法推导中最常用的方法。熟练掌握它们，你将具备自己创造算法的能力。我曾经在一次面试中遇到一道没见过的题，就是用这两种方法现场编了一个面试官都没见过的算法。当面试官质疑我的算法正确性时，我就用反证法和数学归纳当场证明了一下，直接把面试官给征服了。

三来是我希望能够通过我的理解进行证明过程推导，以此来消除之前你对数学证明或多或少所存在的畏难心理，之后，你可以更加从容地面对数学证明相关的问题。

再看拜占庭将军问题

上一讲中，主要是以易懂的方式来讲拜占庭将军问题的，现在到了证明阶段，那么就来看一下拜占庭将军严格的形式化表达形式是到底是怎样的。

拜占庭将军问题：发令将军将指令发送给 n-1 个副官（传递消息的将军），副官之间需要通过协作达成下列两个目标：

IC1：所有忠诚的副官对发令将军发送的指令达成一致。

IC2：如果发令将军是忠诚的，那么所有忠诚副官最终达到一致的指令和发令将军发出的指令相同。

IC2 是对 IC1 的强化，当发令将军是叛徒时，所有的忠诚副官只需要保持一致即可；如果发令将军是忠诚的，那么忠诚副官不仅要保持一致，还要和发令将军一致，也就是说，忠诚发令将军的指令最终要被忠诚副官接受，忠诚副官之间不能达成一个与发令将军不同的一致性。

接下来，我们将解决拜占庭将军问题的方法定义为 BGP，BGP(n, m) 代表解决 m 个叛徒将军的方法，其中 n 代表将军总数。现在，我们需要证明的问题就变成了：

1. 如果将军总数 n 小于等于 3m，BGP(n, m) 不存在
2. 如果将军总数 n 大于 3m，BGP(n, m) 存在

证明 n=3m, BGP(m) 不存在

再来看 n=3m, BGP(m) 不存在这种情况，实质上，不存在这类的证明，初看上去很难找到思路，因为我们日常的逻辑通常是为了证明一件事情的存在去找正确的解决方法，而不存在的情况的证明，是和这种惯常思维相反的。好在这类证明也有一个通用且具有强大功能的解决方案，那就是反证法。

反证法的通常思路是：

1. 假设命题成立；

2. 通过这个成立的命题推导出和已知情况出现了矛盾。

在已知情况正确、推导也正确的情况下，只能是命题不成立。这个思路可能看上去比较简单，但是使用过反证法的人都知道，最难的地方在于：找到一个与已知情况矛盾的推导过程。

下面就让我们通过拜占庭将军问题的证明来看一下如何利用反证法。

我们先来看下 n=3m 的情况：

第一步，假设存在一个 m 在 n=3m 的情况下 BGP(3m, m)存在。

第二步，通过BGP(m)找到和已知情况矛盾的推导。那么我们有什么已知的情况呢？

在上一讲中，我们已经看到了三将军问题是无解的，也就是在 n=3, m=1 的情况下 BGP(3, 1) 是不存在的。那么我们就可以尝试通过 BGP(3m, m) 来构造 BGP(3, 1) 的解法，如果构造成功了那么就和 BGP(3, 1) 不存在出现了矛盾，我们就得以证明 BGP(3m, m) 不存在。

有了这个从 BGP(3m,m)—>BGP(3, 1) 的思路，我们构造推论的过程就变得简单些了。为了和拜占庭将军区分，我们将掌握了BGP(3m, m)方法的将军命名为阿尔巴尼亚将军。那么在拜占庭三将军问题里，我们让每个拜占庭将军模拟 m 个阿尔巴尼亚将军的行为：

1. 发令拜占庭将军模拟一个阿尔巴尼亚发令将军和 m-1 个阿尔巴尼亚副官的行为；
2. 忠诚拜占庭将军模拟忠诚阿尔巴尼亚将军的行为；
3. 叛徒拜占庭将军可以做任意的事情。

由于在BGP(3m, m)的存在，也就是 IC1 和 IC2 同时满足，2m 个忠诚阿尔巴尼亚将军之间可以达成一致。那么忠诚的拜占庭将军只需要使用自身模拟的 m 个阿尔巴尼亚将军的决策也就可以获得一致，我们推导出了三将军问题解决方法存在的推论。

由于三将军问题是无解的，我们的推论过程也是正确的，那么错误的只能是存在一个 m 使得 BGP(3m, m) 存在的这个假设。

证明 n>3m,BGP(n, m)存在

接下来，让我们一起来看下当 n>3m,BGP(n, m)存在时应该如何证明。存在类的证明相比较而言直接一些，如果我们能够找到一个解决 BGP(n, m)的策略就可以证明解法存在。此时的难点变成——如何找到这个策略，对于这类策略问题，同样有一个通用的数学证明方法，那就是数学归纳法。

和反证法类似，数学归纳法的证明通常也分为两步：

1. 证明 n=1 的时候命题成立；
2. 假设 n=k-1 时命题成立，证明 n=k 时命题也成立。

可以看出，数学归纳法和反证法比较类似，在上一个证明中我们利用反证法从假设命题推导已知结论，而在数学归纳法里，我们是从已知结论推导假设命题。

在上一讲中，已经讲了在四个将军、一个叛徒的情况下，也就是BGP(4, 1) 是存在解决方法的。那接下来我们就来小试牛刀，证明一下在 n>=4 的情况下， BGP(n, 1) 存在这个命题。n=4 的情况已经是成立的了，现在假设 n=k-1 命题也成立，也就是 BGP(k-1, 1)存在，看一下 n=k 的情况是怎样的。

首先，假设在 n=k 的情况下发令将军是忠诚的，那么剩下的 k-1 个副官里有 1 个叛徒。接下来，k-1 个副官之间同步关于发令将军所发出的命令。这种情况下每个副官都成为了一个发令将军，发的命令是关于自己从最开始的发令将军那里所得到的命令。由于BGP(k-1, 1) 的存在，忠诚副官之间可以通过 BGP 算法对每个副官所发出的命令达成一致，因此每个忠诚副官就会受到 k-2 个忠诚副官的命令、1 个叛徒副官的命令。由于忠诚副官之间的命令都是从忠诚发令将军那里来的命令，他们之间命令也是一致的，因此每个忠诚副官只要对所收到的命令取一个大多数人的意见，彼此之间就可以达成一致。

再来看下发令将军是叛徒的情况，那么剩下 k 个副官都是忠诚的，且他们彼此之间不存在欺骗，我们还是用上一步中用BGP(k-1, 1) 同步消息取大多数的方法，所有忠诚副官之间最终达到的命令，依然是一致的。如此一来，我们用同一套同步消息，且取大多数的方法就完成了从 n=k-1 到 n=k 的推导，也就证明了在 n>=4 的情况下 BGP(n, 1)的存在。而且，你会发现在证明推导的过程中我们也找到了解决这个问题的策略。

好了，现在让我们进入正餐，证明 n>3m 时，BGP(n, m) 存在的命题。由于我们上一步证明了 BGP(n, 1)，因此 BGP(n, 1) 也就变成了一个已知条件。我在这里对 m 进行一下归纳：假设 m=k-1 命题成立，也就是BGP(n, k-1) 存在，证明 m=k 时命题也成立。这一命题和上一个命题的证明过程，非常类似。

首先，假设在 m=k 时发令将军是叛徒， 剩下的 n-1 个副官之间进行信息同步，由于剩下的副官里有 k-1 个叛徒，在 n>3k 的情况下 n-1>3k-1>3k-3，因此剩下的忠诚副官之间可以通过 BGP(n, k-1) 算法来对每个副官发出的命令达成一致。这样一来，我们依然可以用取大多数的方法来让忠诚副官之间达到一致。

这里我们可以总结出数学归纳法的一个套路，就是想方设法在 n=k 的情况下削减掉一个将军，这样就可以复用 n=k-1 的假设，然后再削减掉一个到 n=k-2 的假设，一直递归下去到 n=1 的已知情况。之后在使用 n=1 的结论一路向上来解决 n=2,n=3 一直到 n=k。

再来看发令将军是忠臣的情况。你会发现少了一个忠臣，副官里叛徒数量占比变大了，固而没办法再用之前的假设了。如果我们还是用上一步的方法不断地削减一个将军进行递归的话，叛徒的比例可能会越来越大，当削减到 BGP(n-m+1, 1) 时，剩余的副官里最多可能有 m 个叛徒和 m+1个忠臣。表面看上去问题似乎是无法解决了，但是你回过头来仔细再想一下，该假设的前提是发令将军是忠臣，因此 m+1 个忠臣收到的命令是一致的。由于同步信息后所有的 2m+1 个命令中与发令将军一致的占据了多数，因此用同样取大多数的方法我们依然得到了正确且一致的结果。

综合上面两个推导，不难看出：

• 无论发令将军忠诚与否，BGP 算法都可以达成一致；
• 我们既证明了在 n>3m 时，BGP(n, m) 存在的命题，同时又在推导的过程中得出了 BGP 算法的解决策略，可谓是一举两得。

总结

在这一讲里，我们使用反证法和数学归纳法，对拜占庭将军问题进行了证明。在证明的推导过程中，你也应该明白了如何根据拜占庭将军问题去解决算法问题。实质上，掌握了以上这两种方法，会极大提升你之后解决算法类问题的能力。

话说回来，反证法只是数学证明中众多方法的一种，还有很多方法可以解决相同的问题。关于拜占庭将军问题，Easy impossibility proofs for distributed consensus problems 这篇论文提出了一种十分巧妙的证明方式，推荐你也阅读一下，你一定会被作者的奇思妙想征服的。（相关内容链接：https://link.springer.com/article/10.1007%2FBF01843568）

数学归纳法在证明过程中通常能得到一个解决策略，但是这一策略的质量取决于推导过程中的方法，而且数学归纳法常见做法是从 n 递归到 1 复杂度通常都是指数级别的，很多时候不一定是复杂度最低的策略。关于拜占庭将军的另一个解决算法，你可以参考 Practical Byzantine Fault Tolerance 这篇论文，其中介绍了一个多项式复杂度的解决方案。

拜占庭将军问题论文的作者 Lamport 是分布式领域开山祖师级的任务，这个专栏里你还会多次遇到他。而拜占庭将军问题通过比喻的方式形象的描述了分布式系统中如何在消息不可靠的场景下取得一致这个一致性领域内最为困难的一个问题，这个比喻也成为了分布式一致性理论中最著名的比喻。几年后，尝到比喻甜头的 Lamport 又一次使用比喻来描述一个分布式一致性算法，却遭到了失败，这个一致性算法也因为难以理解而名声远扬——这就是 Paxos。看来即使是大神在炫技的时候也会失误呀。

思考题

这一讲中，我们通过反证法证明了当 n=3m 时，BGP(n, m) 不存在的命题，那么你能用类似的方法证明在 n<3m 时，BGP(n, m) 不存在这一命题么？