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

本篇内容介绍了“白话讲解，拜占庭将军问题”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！

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

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

根据这一结论进一步推导可以得出一个更通用的结论，如果存在 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就完全暴露了。

由此可见，在多了一个忠臣的情况下，叛徒需要处处小心，才能避免被发现。与此同时，忠臣们即便在存在混乱信息的情况下，行动上也依旧达成了一致。根据推理，我们可以推导出一个结论：当忠臣的个数为 2m + 1 时，他们可以容忍 m 个叛徒产生的破坏。