分布式系统与计算机网络 漫谈分布式系统(3)

首先我们考虑一下将军们制定作战计划的过程（先假设没有叛徒）。每一位将军根据自己对战局的观察，给出他建议的作战计划——是进攻还是撤退。然后，每位将军把自己的作战建议通过信差传达给其他每一位将军。现在每一位将军都知道了其他将军的作战建议，再加上他自己的作战建议，他需要根据所有这些信息得到最终的一个作战计划。为了表达上更清晰，我们给每位将军进行编号，分别是1, 2, ..., n，每位将军提出的作战建议记为v(1), v(2), ..., v(n)，一共是n个值，这其中有些代表「进攻」，有些代表「撤退」。经过信差传递消息之后，每位将军都看到了相同的作战提议v(1), v(2), ..., v(n)，当然这其中的一个是当前这位将军自己提出来的。然后只要每位将军采用同样的方法，对所有的v(1), v(2), ..., v(n)这些信息进行汇总，就能得到同样的最终作战计划。比如，容易想到的一个方法是投票法，即对v(1), v(2), ..., v(n)中不同的作战计划进行投票，最后选择得票最多的作战计划。分布式系统与计算机网络

现在我们考虑将军中出现了叛徒。遵循前面的思路，我们仍然希望每位将军能够收到完全相同的作战建议v(1), v(2), ..., v(n)。现在我们仔细审视一下其中的一个值，v(i)，在前面的描述中，它表示来自第i个将军的作战提议。如果第i个将军是忠诚的，那么这个定义没有什么问题。但是，如果第i个将军是叛徒，那么就有问题了。为什么呢？因为叛徒可以为所欲为，他为了扰乱整个作战计划的制定，完全可能向不同的将军给出不同的作战提议。这样的话，不同的忠诚将军收到的来自第i个将军的v(i)可能是不同的值。这样v(i)这个定义就不对了，它需要改一改。

不管怎么样，即使存在叛徒，我们还是希望每位将军最终是基于完全相同的作战提议来做汇总，这些作战提议仍然记为v(1), v(2), ..., v(n)。不过，这里的v(i)不再表示来自第i个将军的作战提议，而是表示经过我们设计的某个一致性算法处理之后，每位将军最终看到的第i个提议。这里需要分两种情况讨论。首先第一种情况，如果第i个将军是忠诚的，那么我们自然希望这个v(i)就是第i个将军发送出来的作战提议。换句话说，我们希望经过一致性算法处理之后，第i个将军如果是忠诚的，那么它的提议能够被如实地传达给其他将军，而不会被叛徒的行为所干扰。分布式系统与计算机网络这是可能制定出「合理」作战计划的前提。第二种情况，如果第i个将军是叛徒，那么他有可能向不同的将军发送不同的提议。这时候我们不能够只听他的一面之词，而是希望经过一致性算法处理之后，各个将军之间充分交换意见，然后根据其他各个将军转述的信息，综合判断得到一个v(i)。这个v(i)是进攻还是撤退，并不太重要，关键是要保证每位将军得到的v(i)是相同的。只有这样，各位将军经过汇总所有的v(1), v(2), ..., v(n)之后才能得到最终的完全一致的作战计划。

一个主将发送命令给n-1个副官，如何才能确保下面两个条件：(IC1) 所有忠诚的副官最终都接受相同的命令。(IC2) 如果主将是忠诚的，那么所有忠诚的副官都接受主将发出的命令。

这其实正好对应了我们前面已经讨论过的两种情况。如果主将是忠诚的，那么条件IC2保证了命令如实地传递，这时候条件IC1自然也满足了；如果主将是叛徒，那么条件IC2没有意义了，而条件IC1保证了，即使叛徒主将对每个副官发出不同的命令，每个副官仍然能最终获得一致的命令。

.

这里有两个地方可能让人产生疑惑。

第一，有些人会问了，难道主将还能是叛徒？主将都是叛徒了，还有啥搞头啊？其实是这样的，这个「拜占庭将军问题」只是原问题的一个子问题。当n个将军通过传递消息来决策作战计划的时候，可以分解成n个「拜占庭将军问题」，即分别以每位将军作为主将，以其余n-1位将军作为副官。如果有一个算法能够解决「拜占庭将军问题」，那么同时运行n个算法实例，就能使得每位将军都获得完全相同的作战建议序列，即前面我们提到的v(1), v(2), ..., v(n)。最后，每位将军将v(1), v(2), ..., v(n)使用相同的方法进行汇总（比如按多数投票），就能得到最终的作战计划。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-65268-3.html