4.3　FLP不可能原理

1.定義

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不可能原理告訴我們，不要浪費時間去試圖為異步分布式系統設計面向任意場景的共識算法。

2.如何理解

要正確理解FLP不可能原理，首先要弄清楚“異步”的含義。

在分布式系統中，同步和異步這兩個術語存在特殊的含義。

●同步，是指系統中的各個節點的時鐘誤差存在上限；并且消息傳遞必須在一定時間內完成，否則認為失敗；同時各個節點處理消息的時間是一定的。因此同步系統中可以很容易地判斷消息是否丟失。

●異步，是指系統中各個節點可能存在較大的時鐘差異；同時消息傳輸時間是任意長的；各節點對消息進行處理的時間也可能是任意長的。這就造成無法判斷某個消息遲遲沒有被響應是哪里出了問題。（節點故障還是傳輸故障？）遺憾的是，現實生活中的系統往往都是異步系統。

FLP不可能原理在論文中以圖論的形式進行了嚴格證明。要理解其基本原理并不復雜，一個不嚴謹的例子如下。

三個人在不同房間進行投票（投票結果是0或者1），彼此可以通過電話進行溝通，但經常有人會時不時睡著。比如某個時候，A投票0，B投票1，C收到了兩人的投票，然后C睡著了。此時，A和B將永遠無法在有限時間內獲知最終的結果，究竟是C沒有應答還是應答的時間過長。如果可以重新投票，則類似情形可以在每次取得結果前發生，這將導致共識過程永遠無法完成。

FLP不可能原理實際上說明，對于允許節點失效的情況，純粹異步系統無法確保共識在有限時間內完成。即便對于非拜占庭錯誤的情況，包括Paxos、Raft等算法也都存在無法達成共識的極端場景，只是在工程實踐中這種情況出現的概率很小。

那么，這是否意味著研究共識算法壓根沒有意義？

不必如此悲觀。學術研究往往考慮的是數學和物理意義上理想化的情形，很多時候現實世界要穩定得多。（感謝這個世界如此魯棒！）例如，上面例子中描述的最壞情形，每次都發生的概率其實并沒有那么大。工程實踐中，若某次共識失敗，再嘗試幾次，很可能就成功了。

科學告訴你，什么是不可能的；工程則告訴你，付出一些代價，可以把它變得可行。

這就是科學和工程不同的魅力。FLP不可能原理告訴大家，不必浪費時間去追求完美的共識方案，而要根據實際情況設計可行的工程方案。

那么，退一步講，在付出一些代價的情況下，共識能做到多好？

回答這一問題的是另一個很出名的原理——CAP原理。