我們都知道在任何一個的分布式系統之中可能會存在各種各樣的問題。

例如服務器上運行的某些進程不可靠。例如服務器硬件可能會發(fā)生故障，操作系統可能會出現崩潰，進程會出現故障等。

再比如進程之間的網絡通訊不可靠。消息可能會丟包、延時，網絡可能會出現分區(qū)。

除了上述硬件或網絡的故障外，系統進程甚至會出現一些任意或者欺詐的問題，即所謂的拜占庭故障。例如，在航天儀器上安裝的多種傳感器，可能會在極端的環(huán)境下，呈現出任意的行為，例如傳送錯誤的參數。而在類似比特幣等區(qū)塊鏈網絡，黑客會控制部分進程，故意偽造、篡改各類交易，以達到不可告人的目的。因此，對于一個分布式的系統而言，故障簡直就是家常便飯；假定一個分布式網絡系統的所有的進程都會在任何場景下運行正常才是一個瘋狂的想法。

那么問題來了，在一個分布式的異步網絡中，要使得所有可靠的進程能夠通過通訊達成共識是否可能呢？答案是驚人的，那就是不可能。

你可能會問，現在的分布式系統怎么可能無法達成共識呢？答案是，這里的前提是異步網絡。在21世紀20年代的今天，我們已經知道有很多能夠達成共識的經典算法，不過他們基本上都是在同步網絡模型的基礎上構建的。而在異步網絡模型中，只有關于進程計算和消息傳輸的最少量的約束和規(guī)則。算法是基于事件的，例如一個進程可以給所有其他進程廣播發(fā)送信息。在完全的異步網絡中，我們對于進程處理的速度和消息傳遞的速度都是無法參照和分析的。消息本身可以任意延遲，接收的消息也可能任意亂序。我們假定進程無法參照同步的時鐘，這也意味著我們在算法設計過程中無法使用基于超時機制的算法。我們也無法檢測一個進程是否故障，因為我們無法判斷和區(qū)分出這個進程究竟是執(zhí)行得太慢，還是消息傳遞速度太慢，亦或是該進程已經掛了。

在這篇著名的《Impossibility of Distributed Consensus with one Faulty Process》中，就進行了嚴格的理論證明。論文得出了一個簡潔優(yōu)雅，又非常驚人的結論：在假設網絡可靠、計算節(jié)點只會因崩潰而失效的最小化異步模型系統中，仍然不存在一個可以解決一致性問題的確定性算法。這篇論文發(fā)表后，立刻得到了廣泛的關注和研究，論文中提出的證明按照論文的三位作者的FISCHER、Lynch和Parterson而命名，被稱為FLP定理。這三位都是分布式計算領域的權威學者。這篇文章奠定了分布式計算的理論基礎之一，但又是如此的晦澀，以至于大多數計算機理論教材都跳過了這個證明，甚至連經典的分布式計算專業(yè)教材《Notes on Distributed computing》中都簡化了和跳過了本論文中的部分證明步驟。而參考了中文社區(qū)的部分博文，仍然不是特別的清晰，因此，我在這里重新花時間使用一些不太精確的表述來說明其主要的證明過程，希望能幫助大家來更好地理解。如果大家有任何問題或反饋，歡迎與我聯系：）

首先，我們來定義一下分布式異步網絡的模型中的一些常見的概念：

進程（Process）：系統中的一個工作單元。（由于本論文發(fā)表時間較早，在某些教材中，使用節(jié)點Node來表述這一概念）。

消息傳遞（Message Passing）： 一組進程構成的分布式系統，每個進程都能進行本地運算，并可以向網絡中的其他進程發(fā)送消息。

消息丟失 (Message Loss)：在存在消息丟失的消息傳遞模式下，任何一條消息都不能保證可以安全到達消息的接收者。

共識（Consensus）：達成共識需要同時滿足以下幾點：

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

可終止性(termination)：所有非故障進程最終一定會同意某個值。

有效性(validity)：最終同意的某個值必須在有效值的區(qū)間內。例如，在這里我們簡化一下模型，將取值范圍縮小到{0,1}的集合；那么值不可能取2。同樣的，如果所有的輸入值都為0，那么最終的結果值只能是0.

在這篇論文中，將證明的條件進行了進一步的放寬。我們容忍只有任意其中一個進程可能出現崩潰，且一旦崩潰后不再處理任何消息，并且我們排除了拜占庭網絡，假定網絡中所有的參與者都不是惡意的，而且，我們假定消息系統系統是可靠的，所有的消息只會被發(fā)送一次，且被準確無誤地傳輸。這樣的網絡環(huán)境無疑比現實的異步網絡的環(huán)境要靠譜和理想化的多。此外，如上所述，我們將達成共識的值縮小到{0,1}的集合，來進一步簡化整個分析的模型。如果連上述放寬的模型中，都無法找到一種異步網絡的有效共識算法；那么可想而知，在真實的分布式的異步網絡，更加不可能找到一種有效的共識算法。

論文中的共識協議如下：

在一個異步系統中，存在N個進程(N≥2)，每個進程p都有一個一位的輸入寄存器xp，和一個輸出寄存器yp，和足夠的內部存儲。輸出的值可能是0或1，或者是不確定的（例如在起始階段，結果并不確定，那么值就是不確定的）。假如輸出寄存器yp已經有了結果（即0或1），那么就稱為decision states。每次yp的輸出,一旦產生了結果，就無法再被篡改。所有進程的初始狀態(tài)和轉換過程組成了整個系統共識協議P。

不同的進程之間彼此通過發(fā)送消息來通信。我們定義一個消息為（p,m）。p代表了目標進程，m代表了具體的消息內容。每個進程都有一個消息緩存（message buffer），支持了以下兩種操作：

send(p,m) 發(fā)送消息并往buffer添加。

receive(p) 接收消息并從buffer移除。要么取到并返回消息m并從隊列刪除對應的(p,m)，要么沒有取到任何消息，返回null。因此，只要buffer不為空，就意味著有部分消息并未送達，出現了超時。

正如之前的定義，這里的消息只會延遲，而不會丟失，所有的消息終將被接收。但同樣的，即便buffer中存在(p,m)，進程仍有可能返回null，這是由異步網絡的不確定性所決定的。

配置（configuration）： 系統的配置包含了每個進程的內部狀態(tài)，包含了message buffer里的內容。一個初始化的配置包括了所有進程的初始狀態(tài)和一組空的message buffer。

從一個配置到另外一個配置被稱為一個步驟（step）。假設定義一個配置C，一個step包括兩個階段：

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

p拿到消息m后，進入一個新的內部狀態(tài)，然后向其他進程發(fā)送消息。

step是由(p,m)所決定的，我們定義(p,m)為事件(event)。因為event(p,null)總可能存在，所以p總是能執(zhí)行一個step。

事件序列（schedule）：從C開始應用的有限或無限的事件序列σ。一系列關聯的step序列被稱為run。如果事件序列σ是有限的，我們使用σ（C）來表示配置結果，同時表示配置結果從配置C可達。在下文中，我們假定所有的配置都是可達的。

單價（univalent)：如果決策值不依賴于之后的事件可以確定，那么該配置是單價的。

二價（bivalent）：如果決策值只能是0或者1，那么這個配置是二價的。（決策值依賴于消息接收的順序或崩潰事件發(fā)生的順序，也就是說，在那個時刻還沒決定究竟輸出的是哪個值）。

假如所有進程的輸入值是0，那么根據之前的定義，可以肯定該配置是0-valent的。

如果某個進程p執(zhí)行了有限的steps，那就意味著在執(zhí)行到其中某個step的時候進程不再執(zhí)行，則被稱為故障的；否則，則是正常的。正如上文所述，本模型允許一個進程故障，并且所有正常進程最終將收到所有的消息。

如果某個進程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的執(zhí)行次序不會影響結果配置C3的最終結果。因為定義里已經說明了σ1和σ2彼此不相關，所以無論是先執(zhí)行σ1，還是先執(zhí)行σ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上執(zhí)行這個deciding run和C1上執(zhí)行這個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，所以根據定義，我們可以發(fā)現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配置不可能變?yōu)槠渌担瑥?-valent只能變?yōu)?-valent。

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

我們可以繼續(xù)構造『輔助線』來進行證明。

假設有一個從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變?yōu)閡nivalent配置。這個步驟決定了最終的決定值。我們可以定義一個關鍵配置：如果配置C是bivalent的，但是配置C的所有直接子節(jié)點的配置都是univalent的，我們稱C為關鍵配置。

但是根據引理3，單個進程的崩潰（延遲事件e的接收），會導致產生一個bivalent的葉子節(jié)點配置。這個關鍵步驟總是有可能會被拖延，因而導致系統無法無法完成這最關鍵的一步。

故我們可以得出最終的結論，當f>0時（f為故障進程），不存在一個確定的算法（Deterministic Algorithm）總能在異步模型下達成共識（P is totally correct）。

同時，我們還可以得出另外一個定理：假設所有非故障進程不發(fā)生故障且初始的時候大多數進程存活，則存在一個部分正確的共識協議，所有非故障進程總能達成共識。也就是說，在異步通訊的模型下，我們最多只能滿足一致性和有效性，但是無法保證可終止性。在論文中，也給出了這個定理的證明，此處證明略，有興趣的同學可以按文章底部的鏈接打開paper一讀。

總結：

我們已經證明了在一個完全異步通訊的模型下，只要存在一個故障節(jié)點，就不存在一種確定的共識算法。當然，這個結果更多的是理論上的，在實際中無法達成終止的概率非常低。這個結論只是表明了，不存在一個完美的解決方案；在實際工程中，需要理解這個定理，并在設計協議的時候做到有效的取舍；畢竟，一個號稱實現了異步網絡下的完全正確的共識算法的協議都是垃圾。

《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