FLP 不可能原理

定义

FLP 不可能原理：在网络可靠、但允许节点失效（即便只有一个）的最小化异步模型系统中，不存在一个可以解决一致性问题的确定性共识算法（No completely asynchronous consensus protocol can tolerate even a single unannounced process death）。

提出并证明该定理的论文《Impossibility of Distributed Consensus with One Faulty Process》是由 Fischer、Lynch 和 Patterson 三位科学家于 1985 年发表，该论文后来获得了 Dijkstra（就是发明最短路径算法的那位计算机科学家）奖。

FLP 不可能原理告诉我们，不要浪费时间去试图为异步分布式系统设计面向任意场景的共识算法。

如何理解

要正确理解 FLP 不可能原理，首先要弄清楚“异步”的含义。

在分布式系统中，同步和异步这两个术语存在特殊的含义：

• 同步，是指系统中的各个节点的时钟误差存在上限；并且消息传递必须在一定时间内完成，否则认为失败；同时各个节点完成处理消息的时间是一定的。因此同步系统中可以很容易地判断消息是否丢失；
• 异步，则意味着系统中各个节点可能存在较大的时钟差异；同时消息传输时间是任意长的；各节点对消息进行处理的时间也可能是任意长的。这就造成无法判断某个消息迟迟没有被响应是哪里出了问题（节点故障还是传输故障？）。不幸地是，现实生活中的系统往往都是异步系统。

FLP 不可能原理在论文中以图论的形式进行了严格证明。要理解其基本原理并不复杂，一个不严谨的例子如下。

三个人在不同房间进行投票（投票结果是 0 或者 1），彼此可以通过电话进行沟通，但经常有人会时不时睡着。比如某个时候，A 投票 0，B 投票 1，C 收到了两人的投票，然后 C 睡着了。此时，A 和 B 将永远无法在有限时间内获知最终的结果，究竟是 C 没有应答还是应答的时间过长。如果可以重新投票，则类似情形可以在每次取得结果前发生，这将导致共识过程永远无法完成。

FLP 不可能原理实际上说明对于允许节点失效情况下，纯粹异步系统无法确保共识在有限时间内完成。即便对于非拜占庭错误的前提下，包括 Paxos、Raft 等算法也都存在无法达成共识的极端情况，只是在工程实践中这种情况出现的概率很小。

那么，这是否意味着研究共识算法压根没有意义？

不必如此悲观。学术研究，往往考虑地是数学和物理意义上理想化的情形，很多时候现实世界要稳定得多（感谢这个世界如此鲁棒！）。例如，上面例子中描述的最坏情形，每次都发生的概率其实并没有那么大。工程实现上，若某次共识失败，再尝试几次，很大可能就成功了。

科学告诉你，什么是不可能的；工程则告诉你，付出一些代价，可以把它变成可行。

这就是科学和工程不同的魅力。FLP 不可能原理告诉大家不必浪费时间去追求完美的共识方案，而要根据实际情况设计可行的工程方案。

那么，退一步讲，在付出一些代价的情况下，共识能做到多好？

回答这一问题的是另一个很出名的原理：CAP 原理。

注：科学告诉你去赌场是愚蠢的，因为最终总会输钱；工程则告诉你，如果你愿意接受最终输钱的风险，中间说不定能偶尔小赢几笔呢！