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 原理。

注：科學告訴你去賭場是愚蠢的，因為最終總會輸錢；工程則告訴你，如果你願意接受最終輸錢的風險，中間說不定能偶爾小贏幾筆呢！