FLP不可能定理及其证明

例如，服务器上运行的一些进程是不可靠的。例如，服务器硬件可能出现故障，操作系统可能崩溃，进程可能失败。

再比如进程间的网络通信不可靠。消息可能会丢失、延迟，网络可能会被分割。

除了上面提到的硬件或网络故障，系统进程中甚至可能出现一些任意的或欺诈性的问题，也就是所谓的拜占庭故障。例如，安装在空间仪器上的各种传感器在极端环境下可能会表现出任意行为，例如传输错误的参数。在比特币这样的区块链网络中，黑客会控制一些流程，故意伪造和篡改各种交易，以达到不可告人的目的。因此，对于一个分布式系统来说，失败简直是家常便饭；假设分布式网络系统中的所有进程在任何情况下都能正常运行，这是一个疯狂的想法。

那么问题来了，在一个分布式异步网络中，是否所有可靠的进程都有可能通过通信实现* * *知识？答案很神奇，那是不可能的。

你可能会问，现在的分布式系统怎么可能达不到* * *知识？答案是这里的前提是异步网络。265438+1920s我们已经知道有很多经典算法可以实现* * *知识，但基本都是建立在同步网络模型的基础上。然而，在异步网络模型中，只有关于进程计算和消息传输的最小约束和规则。该算法是基于事件的，例如，一个进程可以向所有其他进程广播和发送信息。在完全异步的网络中，我们无法参考和分析流程处理和消息传输的速度。消息本身可以随意延迟，接收到的消息也可能随意乱序。我们假设进程不能引用同步时钟，也就是说在算法设计过程中不能使用基于超时机制的算法。我们无法检测一个流程是否有故障，因为我们无法判断和区分是流程执行太慢，还是消息传递速度太慢，还是流程已经挂起。

在这个著名的“有一个错误过程的分布式共识的可能性”中，进行了严格的理论证明。本文得出了一个简洁优雅且令人惊讶的结论:在假设网络可靠、计算节点只会因崩溃而失效的最小化异步模型系统中，仍然没有确定性算法可以解决一致性问题。这篇论文发表后，立即得到了广泛的关注和研究。本文提出的证明以论文的三位作者费希尔、林奇和帕特森的名字命名，被称为FLP定理。三位都是分布式计算领域的权威学者。这篇文章奠定了分布式计算的理论基础之一，但它是如此晦涩，以至于大多数计算机理论教材都跳过了这个证明，甚至经典的分布式计算教材《分布式计算笔记》也简化并跳过了文中的一些证明步骤。不过参考了中文社区的一些博文，还是不是特别清楚，所以我在这里花点时间用一些不准确的表述来解释一下主要的证明过程，希望能帮助大家更好的理解。如果您有任何问题或反馈，请随时联系我:)

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

进程:系统中的一个工作单元。(因为这篇论文发表的比较早，所以在一些教材中，用Node node来表达这个概念)。

消息传递:由一组进程组成的分布式系统，每个进程都可以执行本地操作，并向网络中的其他进程发送消息。

消息丢失:在有消息丢失的消息传递模式下，不能保证任何消息安全到达消息接收方。

* * *共识:要达成* * *共识，需要同时满足以下几点:

一致:所有非故障流程都同意相同的值。

终止:所有非故障流程最终会就某个值达成一致。

有效性:最终同意的值必须在有效值的范围内。比如这里我们简化模型，把取值范围缩小到{0，1}的集合；那么值不能取2。同样，如果所有的输入值都是0，那么最终的结果值也只能是0。

本文进一步放宽了证明条件。我们容忍只有一个进程可能崩溃，一旦崩溃，我们将不会处理任何消息。我们排除拜占庭网络，假设网络中的所有参与者都没有恶意，我们假设消息系统是可靠的，所有的消息只会发送一次，并且传输准确。这种网络环境无疑比真实的异步网络环境更加可靠和理想化。此外，如上所述，我们将* * *知识的值降低到{0，1}的集合，以进一步简化整个分析模型。如果连上面的宽松模型都找不到异步网络的有效算法；可想而知，在真实的分布式异步网络中，更不可能找到有效的* * *识别算法。

本文中* * *的协议如下:

在异步系统中，有N个进程(N≥2)，每个进程P有一个一位输入寄存器xp、一个输出寄存器yp和足够的内部存储。输出值可能是0或1，也可能是不确定的(比如在初始阶段，结果不确定，所以值不确定)。如果输出寄存器yp已经有一个结果(即0或1)，它被称为决策状态。yp的每次输出，结果一旦产生，就不能再被篡改。所有过程的初始状态和转换过程构成了整个系统* * *知识协议p。

不同的进程通过发送消息相互通信。我们将消息定义为(p，m)。p代表目标流程，m代表具体的消息内容。每个进程都有一个消息缓冲区，它支持以下两种操作:

Send(p，m)发送一条消息并将其添加到缓冲区中。

Receive(p)接收消息并将其从缓冲区中删除。要么获取并返回消息m并从队列中删除相应的(p，m ),要么不获取消息并返回null。因此，只要缓冲区不为空，就意味着某些消息尚未传递，发生了超时。

如前所述，这里的消息只会被延迟，不会丢失，所有消息最终都会被接收到。但同样，即使缓冲区中有(p，m)，进程仍可能返回null，这是由异步网络的不确定性决定的。

配置:系统的配置包括每个进程的内部状态和消息缓冲区的内容。初始化配置包括所有进程的初始状态和一组空消息缓冲区。

从一个配置移动到另一个配置称为一个步骤。假设定义了配置C，并且一个步骤包括两个阶段:

在C接收(p)，得到消息m。

p得到消息M，进入新的内部状态，然后将消息发送给其他进程。

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

事件调度:从c应用的有限或无限事件序列σ，一系列相关的步骤序列称为run。如果事件序列σ是有限的，我们用σ(C)来表示配置结果，表示配置结果是从配置C可达的，下面我们假设所有配置都是可达的。

单叶性:如果决策值可以独立于后续事件确定，那么配置是单叶性的。

二进制:如果决策值只能是0或1，那么这个配置就是二进制的。(决策值取决于接收消息的顺序或崩溃事件发生的顺序，即尚未决定在该时刻输出哪个值)。

如果所有进程的输入值都是0，那么根据前面的定义，可以肯定配置是0价的。

如果一个进程P执行了有限的几个步骤，就意味着当其中一个步骤被执行时，这个进程将不会被执行，就称为故障；否则，很正常。如上所述，该模型允许一个进程失败，所有正常的进程最终将接收所有消息。

如果一个过程p有一个决定值？v，据说配置c有决定性值v .一个部分正确的* * *知识协议满足以下两个条件:

任何可访问的配置都没有多个决策值；

对于一个可达构形，有些可达构形有一个决定性值V，其中v∈{0，1}。

从以上条件可以看出，条件一满足一致性；条件2满足有效性。

如果一个运行有一个达到决策值的过程，那么这个运行就是决策运行。

完全正确的* * *知识协议P满足以下条件:

这个* * *知识协议P部分正确；

每次跑步都是决定性的。

一个完全正确的* * *知识协议，在一些正确的* * *知识协议的基础上，更具有可终止性。

介绍完上面的主要概念，让我们开始证明，从三个引理开始:

引理1非常直观，容易理解。有点类似于汇率:在配置C中，有两组不相关的事件序列σ1和σ2，所以σ1和σ2的执行顺序不会影响最终得到的配置C3的最终结果。因为在定义中已经解释过，σ1和σ2互不相关，所以无论先执行σ1还是σ2，效果都是一样的。

引理2:协议P有一个二价的初始配置。

证明:这里用归谬法来证明。根据上面协议模型的定义，我们知道P必须同时有0价和1价，也就是说所有初始配置不是0价就是1价。接下来，我们来定义一个配置邻接的概念。如果两个初始构型之间只有一个过程P的初值xp不同，我们就说这两个构型是相邻的。显然，两个相邻的构型是可达的，所以我们可以列出所有可能的初始构型，最后我们可以通过相邻关系将所有可能的初始构型连接起来。那么，一定有相邻的C0和C1，这样C0就是0价，C1就是1价，P就是C0和C1的不同过程。

现在我们假设有一个决定运行，其中P是失败的进程，那么从定义上来说，排除P之后，其他进程是完全一样的。

然后，在C0上执行这个判定运行的结果与在C1上的结果相同。如果结果是0价，说明C1一定是二价的；；如果是1价，就说明C0是二价的。这与我们的上述假设相反。因此，协议P的初始配置为二价。

原文引理3的符号看起来有点晕。我们来替换一下这里的相关符号。

引理3: C是协议P中的二价配置，事件e(p，m)可以影响C .我们调用所有从C可达的可达配置集，而不应用E作为A，这样B=e(A)={e(E)| E∈A且E可以应用于E }；那么，B必须包含一个二价构型。

证明:因为E可以应用于C，根据定义我们可以发现A实际上延迟了接收事件E，集合中的任意配置都可以应用E，从C不应用E得出的配置集是A，从A中的任意配置应用E，得到的配置集是b。

我们还是用反证法，假设集合B不含二价构型，那么每个B中的构型都是一价的，也就是要么是0价，要么是1价。

我们定义e i，从C可达，其中i=0，1(因为C属于二价，所以Ei存在)。

如果Ei∈A，那么根据定义，应用e后，有fi = e (ei)和fi ∈ b。

如果e已经应用到到达Ei，则有Fi，Ei从Fi可达，fi ∈ b。

无论哪种情况，fi都属于单叶，因为Fi∈b . Ei和Fi之间一定有可达。在Fi中，i=0，1。既然假设B不是二价的，那么综上所述，我们可以证明B总是包含0价和1价。

如果两个构型之间有一个台阶，我们说这两个构型是相邻的。我们定义两个相邻的构型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价到了1价的D1，这是矛盾的，因为任何确定的单价构型都不能改成其他值，只能从0价改成0价。

情况二:p' = p，即消息e和e '相同。

我们可以继续构造“辅助线”来证明。

假设从C0开始有一个有限步数的决定运行，这个决定运行不包含任何与过程P相关的步骤，即与P无关，这个决定运行的事件序列是什么？这里我们构造一个构型X，使得X=？(C0).(x见红色)

如上图，根据引理1，？不与e和e '相交。因此，无论e->；？，还是？-& gt；e，结果是一样的。同样，e '-& gt；e-& gt；？的结果是什么？-& gt；e '-& gt；e的结果是一样的。所以呢？可以应用于Di使得Ei=？(Di)，i=0，1 .e(X)=E0，e(e'(X))=E1

所以x属于二价。但是C0也是单价的，还有呢？这是一个决定性的运行，这与x是二价的是矛盾的。

所以，假设不成立，B一定含有一个二价的构型。

在证明了上述三个引理之后，让我们来证明FLP不可能定理。

根据引理2，P总是具有二价体的初始化构型。在任何决定从二价到一价运行的构型中，都必须有一个步骤使二价变成一价。这一步决定了最终的决策值。我们可以定义一个关键构型:如果构型C是二价的，但构型C的所有直接子节点都是一价的，我们称C为关键构型。

然而，根据引理3，单个进程的崩溃(延迟事件E的接收)将导致二价的叶节点配置。这个关键步骤总是可能被延迟，从而导致系统无法完成这个最关键的步骤。

因此，我们可以得出最后的结论，当f & gt0 (f为故障过程)，没有确定性算法，在异步模型下总能做到* * *识(P始终正确)。

同时，我们还可以得出另一个定理:假设所有非故障进程都没有失败，大部分进程一开始就存活下来，存在一个部分正确的* * *知识协议，所有非故障进程总能达到* * *知识。也就是说，在异步通信模型下，我们最多只能满足一致性和有效性，而不能保证可终止性。文中还给出了该定理的证明。此处省略证明。有兴趣的同学可以打开论文，按照文章底部的链接阅读。

总结:

我们已经证明，在完全异步的通信模型中，只要有一个故障节点，就不存在确定的* * *知识算法。当然，这个结果更多的是理论上的，实践中无法实现终止的概率很低。这个结论只能说明没有完美的解决方案；在实际工程中，需要理解这个定理，在设计协议时进行有效的权衡；毕竟一个号称在异步网络中实现完全正确* * *识别算法的协议是垃圾。

《一个故障过程下分布式共识的可能性》论文地址:/papers-we-love/papers-we-love/blob/master/distributed _ systems/Possibility-of-consensus-with-one-fault-process . pdf