FLP不可能定理及其证明

我们都知道在任何一个的分布式系统之中可能会存在各种各样的问题。

例如服务器上运行的某些进程不可靠。例如服务器硬件可能会发生故障，操作系统可能会出现崩溃，进程会出现故障等。

再比如进程之间的网络通讯不可靠。消息可能会丢包、延时，网络可能会出现分区。

除了上述硬件或网络的故障外，系统进程甚至会出现一些任意或者欺诈的问题，即所谓的拜占庭故障。例如，在航天仪器上安装的多种传感器，可能会在极端的环境下，呈现出任意的行为，例如传送错误的参数。而在类似比特币等区块链网络，黑客会控制部分进程，故意伪造、篡改各类交易，以达到不可告人的目的。因此，对于一个分布式的系统而言，故障简直就是家常便饭；假定一个分布式网络系统的所有的进程都会在任何场景下运行正常才是一个疯狂的想法。

那么问题来了，在一个分布式的异步网络中，要使得所有可靠的进程能够通过通讯达成共识是否可能呢？答案是惊人的，那就是不可能。

你可能会问，现在的分布式系统怎么可能无法达成共识呢？答案是，这里的前提是异步网络。在21世纪20年代的今天，我们已经知道有很多能够达成共识的经典算法，不过他们基本上都是在同步网络模型的基础上构建的。而在异步网络模型中，只有关于进程计算和消息传输的最少量的约束和规则。算法是基于事件的，例如一个进程可以给所有其他进程广播发送信息。在完全的异步网络中，我们对于进程处理的速度和消息传递的速度都是无法参照和分析的。消息本身可以任意延迟，接收的消息也可能任意乱序。我们假定进程无法参照同步的时钟，这也意味着我们在算法设计过程中无法使用基于超时机制的算法。我们也无法检测一个进程是否故障，因为我们无法判断和区分出这个进程究竟是执行得太慢，还是消息传递速度太慢，亦或是该进程已经挂了。

在这篇著名的《Impossibility of Distributed Consensus with one Faulty Process》中，就进行了严格的理论证明。论文得出了一个简洁优雅，又非常惊人的结论：在假设网络可靠、计算节点只会因崩溃而失效的最小化异步模型系统中，仍然不存在一个可以解决一致性问题的确定性算法。这篇论文发表后，立刻得到了广泛的关注和研究，论文中提出的证明按照论文的三位作者的FISCHER、Lynch和Parterson而命名，被称为FLP定理。这三位都是分布式计算领域的权威学者。这篇文章奠定了分布式计算的理论基础之一，但又是如此的晦涩，以至于大多数计算机理论教材都跳过了这个证明，甚至连经典的分布式计算专业教材《Notes on Distributed computing》中都简化了和跳过了本论文中的部分证明步骤。而参考了中文社区的部分博文，仍然不是特别的清晰，因此，我在这里重新花时间使用一些不太精确的表述来说明其主要的证明过程，希望能帮助大家来更好地理解。如果大家有任何问题或反馈，欢迎与我联系：）

首先，我们来定义一下分布式异步网络的模型中的一些常见的概念：

进程（Process）：系统中的一个工作单元。（由于本论文发表时间较早，在某些教材中，使用节点Node来表述这一概念）。

消息传递（Message Passing）： 一组进程构成的分布式系统，每个进程都能进行本地运算，并可以向网络中的其他进程发送消息。

消息丢失 (Message Loss)：在存在消息丢失的消息传递模式下，任何一条消息都不能保证可以安全到达消息的接收者。

共识（Consensus）：达成共识需要同时满足以下几点：

一致性(agreement)：所有非故障进程同意相同的值。

可终止性(termination)：所有非故障进程最终一定会同意某个值。

有效性(validity)：最终同意的某个值必须在有效值的区间内。例如，在这里我们简化一下模型，将取值范围缩小到{0,1}的集合；那么值不可能取2。同样的，如果所有的输入值都为0，那么最终的结果值只能是0.

在这篇论文中，将证明的条件进行了进一步的放宽。我们容忍只有任意其中一个进程可能出现崩溃，且一旦崩溃后不再处理任何消息，并且我们排除了拜占庭网络，假定网络中所有的参与者都不是恶意的，而且，我们假定消息系统系统是可靠的，所有的消息只会被发送一次，且被准确无误地传输。这样的网络环境无疑比现实的异步网络的环境要靠谱和理想化的多。此外，如上所述，我们将达成共识的值缩小到{0,1}的集合，来进一步简化整个分析的模型。如果连上述放宽的模型中，都无法找到一种异步网络的有效共识算法；那么可想而知，在真实的分布式的异步网络，更加不可能找到一种有效的共识算法。

论文中的共识协议如下：

在一个异步系统中，存在N个进程(N≥2)，每个进程p都有一个一位的输入寄存器xp，和一个输出寄存器yp，和足够的内部存储。输出的值可能是0或1，或者是不确定的（例如在起始阶段，结果并不确定，那么值就是不确定的）。假如输出寄存器yp已经有了结果（即0或1），那么就称为decision states。每次yp的输出,一旦产生了结果，就无法再被篡改。所有进程的初始状态和转换过程组成了整个系统共识协议P。

不同的进程之间彼此通过发送消息来通信。我们定义一个消息为（p,m）。p代表了目标进程，m代表了具体的消息内容。每个进程都有一个消息缓存（message buffer），支持了以下两种操作：

send(p,m) 发送消息并往buffer添加。

receive(p) 接收消息并从buffer移除。要么取到并返回消息m并从队列删除对应的(p,m)，要么没有取到任何消息，返回null。因此，只要buffer不为空，就意味着有部分消息并未送达，出现了超时。

正如之前的定义，这里的消息只会延迟，而不会丢失，所有的消息终将被接收。但同样的，即便buffer中存在(p,m)，进程仍有可能返回null，这是由异步网络的不确定性所决定的。

配置（configuration）： 系统的配置包含了每个进程的内部状态，包含了message buffer里的内容。一个初始化的配置包括了所有进程的初始状态和一组空的message buffer。

从一个配置到另外一个配置被称为一个步骤（step）。假设定义一个配置C，一个step包括两个阶段：

在C receive(p)，获取消息m

p拿到消息m后，进入一个新的内部状态，然后向其他进程发送消息。

step是由(p,m)所决定的，我们定义(p,m)为事件(event)。因为event(p,null)总可能存在，所以p总是能执行一个step。

事件序列（schedule）：从C开始应用的有限或无限的事件序列σ。一系列关联的step序列被称为run。如果事件序列σ是有限的，我们使用σ（C）来表示配置结果，同时表示配置结果从配置C可达。在下文中，我们假定所有的配置都是可达的。

单价（univalent)：如果决策值不依赖于之后的事件可以确定，那么该配置是单价的。

二价（bivalent）：如果决策值只能是0或者1，那么这个配置是二价的。（决策值依赖于消息接收的顺序或崩溃事件发生的顺序，也就是说，在那个时刻还没决定究竟输出的是哪个值）。

假如所有进程的输入值是0，那么根据之前的定义，可以肯定该配置是0-valent的。

如果某个进程p执行了有限的steps，那就意味着在执行到其中某个step的时候进程不再执行，则被称为故障的；否则，则是正常的。正如上文所述，本模型允许一个进程故障，并且所有正常进程最终将收到所有的消息。

如果某个进程p拥有了一个决定值(deciding value) v，则称为配置C有决定值v。一个部分正确（partially correct）的共识协议，满足以下两个条件：

没有一个可达的配置有超过一个决定值；

对于某个可达的配置，某些可达的配置有决定值v，其中v∈{0,1}。

从上述条件可见，条件一满足了一致性；条件二满足了有效性。

如果某个run有一个进程达到了决定值，则该run是一个deciding run。

一个完全正确（totally correct）的共识协议P，满足以下条件：

这个共识协议P是部分正确的；

每个run都是deciding run。

完全正确的共识协议在部分正确的共识协议的基础上，多了可终止性。

以上已经介绍完了主要的概念，接下来，我们开始进入证明，首先是三个引理：

引理1理解起来非常直观，也非常容易；有点类似交换率：在配置C上，存在两组不相关的事件序列σ1和σ2，那么σ1和σ2的执行次序不会影响结果配置C3的最终结果。因为定义里已经说明了σ1和σ2彼此不相关，所以无论是先执行σ1，还是先执行σ2，效果都是一样的。

引理2：协议P有一个bivalent的初始配置。

证明：这里使用反证法来证明。根据上文的协议的模型的定义，我们知道P一定既有0-valent和1-valent，也就是说所有的初始配置不是0-valent就是1-valent。接下来，我们来定义一个配置相邻（adjacent）的概念，如果两个初始的配置之间只有其中一个进程p的初始值xp不同，我们就称这两个配置是相邻的。很明显，两个相邻的配置之间是可达的，故我们可以列举出所有可能的初始配置，最后可以通过相邻关系把所有可能的初始化配置连接起来。那么，一定存在相邻的C0和C1，使得C0是0-valent，C1是1-valent，p是C0和C1之间不同的那个进程。

现在我们假设有一个deciding run，其中p是其中那个故障的进程，那么根据定义，排除了p以后，其他进程是一模一样的。

那么，在C0上执行这个deciding run和C1上执行这个deciding run的结果是一样的。如果结果是0-valent，就意味着C1必须是bivalent；如果是1-valent，就意味着C0是bi-valent。这就和我们上述的假设矛盾。所以，协议P有一个bivalent的初始配置。

原文中引理3的符号看起来有点眼花，我们在这里替换下相关的符号。

引理3：C是协议P中的一个bivalent配置，事件e(p,m)可以作用到C。我们把从C可达但不应用e的所有的可达的配置集合称为A，使得B=e(A)={e(E)| E∈A 且 e 可应用到E}；然后，B一定包含一个bivalent配置。

证明：因为e可应用到C，所以根据定义，我们可以发现A实际上是延迟接收了事件e，A集合中的任意配置可应用e。从C中不应用e所到达的配置集合就是A。从A中任意一个配置应用e，所得到的配置集合就是B。

我们还是使用反证法，假设集合B不包含bivalent配置，所以每个B中的配置都是univalent的，也就是说不是0-valent就是1-valent。

我们定义Ei，Ei从C可达，其中i=0,1 （因为C是bivalent的，所以Ei存在）。

假如Ei∈A，那么根据定义，在应用了e以后，存在Fi=e(Ei), Fi∈B。

假如e已经应用于到达Ei，则存在Fi，Ei从Fi可达，且Fi∈B。

无论哪种情况，Fi都是univalent的，因为Fi∈B。Ei和Fi之间必有一个可达。Fi中，i=0,1。由于我们假设了B不是bivalent的，综上所述，我们可以证明B总是包含了0-valent和1-valent。

如果两个配置之间，经过一个step可达，我们就称这两个配置相邻。我们定义两个相邻的配置C0和C1，其中C0,C1∈A。根据定义，我们可以得到D0=e(C0)和D1=e(C1)。我们假设这两个相邻的配置之间应用了事件e'，那么可得到C1=e'(C0),e'=(p',m')。 如下图所示：

接下来可以分两种情况来讨论：

情况1：p'≠p，即消息e和e'不同。

那么根据引理1，我们可以构造下图。D0从0-valent到达了1-valent的D1，而这是矛盾的，因为任意一个确定的univalent配置不可能变为其他值，从0-valent只能变为0-valent。

情况2：p'=p，即消息e和e'相同。

我们可以继续构造『辅助线』来进行证明。

假设有一个从C0开始的有限步数的deciding run，这个deciding run中不包含任何与进程p相关的step，也就是说与p没有任何关联。这个deciding run的事件序列为𝞂，在这里我们构造一个配置X，使得X=𝞂(C0)。（x见红色部分）

如上图所示，根据引理1，𝞂与e和e'都不想交。因此，无论是e->𝞂，还是𝞂->e的顺序，结果都是相同的。同理，e'->e->𝞂的结果与𝞂->e'->e的结果是相同的。所以，𝞂可以应用到Di，使得Ei=𝞂(Di),i=0,1。e(X)=E0，e(e'(X))=E1

因此，X是bivalent的。但是C0也是univalent的，而𝞂是一个deciding run，这就和X是bivalent相互矛盾。

所以，假设不成立，B一定包含一个bivalent的配置。

以上三个引理证明完毕，接下来我们来证明FLP不可能定理。

根据引理2，P总是存在bivalent的初始化配置。任意一个deciding run从bivalent到univalent配置，必定存在某个单一步骤使得bivalent变为univalent配置。这个步骤决定了最终的决定值。我们可以定义一个关键配置：如果配置C是bivalent的，但是配置C的所有直接子节点的配置都是univalent的，我们称C为关键配置。

但是根据引理3，单个进程的崩溃（延迟事件e的接收），会导致产生一个bivalent的叶子节点配置。这个关键步骤总是有可能会被拖延，因而导致系统无法无法完成这最关键的一步。

故我们可以得出最终的结论，当f>0时（f为故障进程），不存在一个确定的算法（Deterministic Algorithm）总能在异步模型下达成共识（P is totally correct）。

同时，我们还可以得出另外一个定理：假设所有非故障进程不发生故障且初始的时候大多数进程存活，则存在一个部分正确的共识协议，所有非故障进程总能达成共识。也就是说，在异步通讯的模型下，我们最多只能满足一致性和有效性，但是无法保证可终止性。在论文中，也给出了这个定理的证明，此处证明略，有兴趣的同学可以按文章底部的链接打开paper一读。

总结：

我们已经证明了在一个完全异步通讯的模型下，只要存在一个故障节点，就不存在一种确定的共识算法。当然，这个结果更多的是理论上的，在实际中无法达成终止的概率非常低。这个结论只是表明了，不存在一个完美的解决方案；在实际工程中，需要理解这个定理，并在设计协议的时候做到有效的取舍；毕竟，一个号称实现了异步网络下的完全正确的共识算法的协议都是垃圾。

《Impossibility of Distributed Consensus with one Faulty Process》论文地址：https://github.com/papers-we-love/papers-we-love/blob/master/distributed_systems/impossibility-of-consensus-with-one-faulty-process.pdf