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

第二，当主将是叛徒的时候，他可以向不同的副官发送不同的命令，怎么可能每个副官仍然能最终获得一致的命令呢？这正是算法需要解决的。其实这也容易解释（我们前面也提到过这个思路），由于主将可能向不同的副官发送不同的命令，所以副官不能直接采用主将发来的命令，而是也要看看其他副官转述来的主将的命令是什么。然后，一个副官综合了由所有副官转述的命令（再加上主将直接发来的命令）之后，就可能得到比较全面的信息，从而做出一致的判断（在实际中是个不断迭代的过程）。

好了，我们用了这么多篇幅，终于把「拜占庭将军问题」本身描述清楚了。这实际上也是最难的部分。我们上一章提到过，理解问题本身比理解问题的答案更重要。只要问题本身分析清楚了，如何设计一个能解决它的算法就只是细节问题了。我们这里不深入算法的细节了，感兴趣的读者可以去查阅下列论文：《The Byzantine Generals Problem》，下载地址：lamport.azurewebsites.net/pubs/byz.pd…《Reaching Agreement in the Presence of Faults》，下载地址：lamport.azurewebsites.net/pubs/reachi…

我们这里只提一下论文给出的算法的结论。

使用不同的消息模型，「拜占庭将军问题」有不同的解法。如果将军之间使用口头消息(oral messages)，也就是说，消息被转述的时候是可能被篡改的，那么要对付m个叛徒，需要至少有3m+1个将军（其中至少2m+1个将军是忠诚的）。如果将军之间使用签名消息(signed messages)，也就是说，消息被发出来之后是无法伪造的，只要被篡改就会被发现，那么对付m个叛徒，只需要至少m+2个将军，也就是说至少2个忠诚的将军（如果只有1个忠诚的将军，显然这个问题没有意义）。这种情况实际相当于对忠诚将军的数目没有限制。

容错性(fault tolerance)

我们前面提到过，以Paxos为代表的分布式一致性协议，是在可信任的环境下运行的。而在「拜占庭将军问题」中，网络中则存在恶意节点。因此我们很容易产生一个想法：Paxos是不是「拜占庭将军问题」在叛徒数为零时的一个特例解？

这样看其实有点问题。在「拜占庭将军问题」中，除了叛徒，剩下的是忠诚的将军。「忠诚」这个词，其实暗含了一个意思：他是能够正常工作的（即你可以随时通过消息跟他进行交互）。为什么这么说呢？我们知道，一个叛徒可以做任何事，包括发送错误消息，也包括不发送任何消息。「不发送任何消息」，相当于不能正常工作，或者说，发生了某种故障。所以，单纯的故障，不仅仅是故意的恶意行为，也应该能归入叛徒的行为。这在其他将军看来没有区别。

按照这种理解，「忠诚」这个词并不是很恰当。叛徒数为零，相当于网络中每个节点都在正常工作。但是Paxos的设计也是能够容错的，就像我们在前面讨论的一样，网络中的少数节点发生故障（比如宕机），Paxos仍然能正常工作。可见，Paxos并不能看成是「拜占庭将军问题」在叛徒数为零时的一个特例解。

那「拜占庭将军问题」和Paxos这类分布式一致性算法的关系应该如何看待呢？我们可以从容错性的强弱程度上来分析。

一般来说，设计一个计算机系统，小到一块芯片，大到一个分布式网络，都需要考虑一定的容错性(fault tolerance)。但根据错误不同的性质，可以分为两大类：拜占庭错误(Byzantine fault)。这种错误，在不同的观察者看来，会有前后不一致的表现。非拜占庭错误(non-Byzantine fault)。从字面意思看，是指那些不属于前一类错误的其它错误。

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