說起分佈式系統裡的不可能性，大傢第一反應應該是CAP理論。但是我們這篇不談CAP，而是另一個關於共識算法的FLP定理。以後有機會的話再寫寫CAP以及這兩個的關系。

FLP是三位作者的名字首字母。這個定理的內容是，在異步網絡下，如果有一臺機器可能出錯，則沒有任何確定性共識算法保證在有限時間內結束。這是一個相當強的結論，比起更著名的CAP理論，FLP不可能性定理實際上更不顯然，也更有意思。

這裡面有很多定義要首先明確：

• 異步網絡。很不幸“異步”又是一個被濫用的詞，在分佈式系統理論中，異步網絡指的是，系統中每個節點的執行速度不必一致，消息從一個節點傳播到另一個節點的時間不確定，沒有一個全局可見的準確時鐘。在本論文的設定裡，消息不會重復，不會丟失，隻是可能會（有限）延遲。
• 出錯。常見的出錯類型有fail-stop, fail-recovery以及拜占庭錯誤。fail-stop指的是一臺機器一旦出錯就卡住不動瞭，fail-recovery指的是機器出錯後會重啟，從頭開始執行，拜占庭錯誤指的是機器出錯後進入混亂，可能亂給別人發消息，甚至是故意發誤導性的消息（比如被黑客入侵瞭）。本論文裡假定是fail-stop。
• 共識算法。本論文裡討論的是一個相當精簡的共識問題：每個節點有一個初始值為0或1，經過一系列互相發消息溝通之後，每個節點都會做出一個決定，輸出一個0或者一個1，一旦做出決定就不能再改。一個正確的共識算法要滿足如下要求：
• 不同節點不能做出不一致的決定
• 需要在有限步數內完成
• 共識算法需要既有可能決定為0，也有可能決定為1。（最後這一條是為瞭避免一種耍賴的方法，比如不管三七二十一通通決定0值，這樣算法就沒有意義。我後文把這一條稱作“非trivial性”要求。）

下面我們把整個框架形式化一下，這個對於後面的證明是非常必要的：

我們的系統裡有N個進程(N>=2)，每個進程有一個1-bit的初始輸入寄存器，有一個輸出寄存器，取值為{b,0,1}，一開始的時候值為b，表示尚未做出決定，在執行過程中這個輸出值隻可以寫一次，寫成0或1，表示相應的決定。每個進程還有自己的內部狀態（aka內存）。

進程之間通過發消息交互。一條消息是一個(p,m)對，p表示消息的目標進程，m是消息內容。消息會放到一個統一的池子裡，於是有兩種操作：– Send(p,m): 把消息(p,m)放到池子裡– Receive(p): 從池子裡取一條發給p的消息，返回m給進程p，並把這條消息從池子裡刪除；或者返回一個空消息給進程p，註意即使這時池子裡有給p的消息，也有可能不馬上把這個消息給p，即模擬消息出現延遲的情況。但如果Receive(p)重復執行無限多次，所有給p的消息都會被p收到。

一個格局（原文是configuration，我瞎翻譯的）指的是某一時刻所有進程的狀態和消息池的狀態的匯總。初始格局是每個進程隻有輸入寄存器非空，而所有進程內部狀態和消息池都為空。算法執行過程就是連續從一個格局到另一個格局的轉移，每次稱為一步。每一步隻涉及某單個進程p，先是執行Receive(p)得到一條發給p的消息或者空消息，然後進程p根據得到的消息和自己的內部狀態，決定如何操作，包括改變自己的內部狀態，放消息到消息池，和/或作出0/1決定。

註意我們討論的是確定性共識算法，就是說一個格局C轉變成什麼新格局，是由從消息池取到什麼消息唯一決定的。所以我們也把收到消息(p,m)稱為一個事件e，用e(C)表示格局C經過事件e以後變成的新格局。我們把一系列連續的事件稱為一個事件序列（原文是schedule，我又瞎翻的），常用 sigma 表示。

先說一個比較顯然的引理：如果兩個事件序列 sigma_1 , sigma_2 涉及的進程沒有交集，那麼從一個格局C先經過 sigma_1 再經過 sigma_2 ，和先經過 sigma_2 再經過 sigma_1 ，到達的是終點格局是相同的。這一點比較好理解，因為這兩個序列涉及的是互不相關的進程，異步網絡裡不同進程收到消息的先後順序本來就是不確定的，所以誰先誰後不應該對結果有任何影響。後文我把這個稱做“交換律”。

交換律示意圖

下面開始真正的證明。我們用反證法，假設這樣一個共識算法P存在，然後推導出矛盾。

對於一個格局C，如果因為之後發生的事件序列的不同，既有可能決定為0，也有可能決定為1，我們就稱C為雙值(bivalent)的。否則，就是不管後面事件序列怎樣，都隻能決定為0，就稱為0-單值；如果隻能決定為1，就稱為1-單值。

下面我們簡單證明，對於任何一個算法P來說，所有可能的初始格局裡面一定存在雙值格局。也就是說，總有某些初始格局你不能僅根據進程的初始輸入就做出決定（比如在一個事先計算好的對應表裡查，是不行的），而是要在算法的運行過程中根據消息的順序不同而達到不同的最終決定。

我們用反證法，假設所有初始格局都是單值格局。因為非trivial性的要求，初始格局裡需要即有0-單值格局又有1-單值格局。不妨設一共有N個進程，每個進程的初始輸入為0或1，則初始格局共有2^N種。我們可以把這2^N個初始格局排成一列，使得相鄰兩個格局之間有且僅有一個進程的初始狀態不同。這個東西叫做格雷碼，總是可以構造出來的（詳見Wiki）。比如三個進程的情況下，我們可以把8個初始格局排成000, 001, 011, 010, 110, 111, 101, 100。因為兩種單值格局都有，那麼序列裡必然能找到相鄰的兩個初始格局屬於不同的單值格局。而這相鄰的兩個格局隻有一個進程的初始輸入不同。如果剛好這個進程一開始就掛掉瞭沒有任何響應，那麼我們的共識算法沒有任何辦法區分這兩種初始格局，也就不可能達成兩種不同的最終決定。於是原引理成立。

下面我們證明最重要的部分：設C是一個雙值格局，事件e=(p,m)是一個可以發生在C上的事件。我們令ℂ表示從C格局出發不經過事件e可以達到的所有可能格局的集合，令D表示ℂ裡面的每個格局都經過事件e得到的格局的集合，則D裡一定仍包含雙值格局。

這個描述有點繞，我們先看看如果它成立，能達成什麼效果。前面引理已經證明瞭初始格局裡一定有雙值格局，我們拿一個這樣的格局出來，再找一個接下來要發生的事件e，那麼我們總可以通過把事件e推後到某個合適的時間發生，使得之後得到的格局仍然可能是雙值格局(i.e.未能做出決定的格局）。從這個新雙值格局繼續同樣操作，那麼就可以永遠留在雙值格局，不做出最終決定。這樣這個共識算法就不能終止瞭。

還是用反證法，假設D裡不包含雙值格局，我們試圖推出矛盾。

若D不包含雙值格局，我們可以得出D裡必須兩種單值格局都存在。(1)

這一步的證明是這樣的：因為初始格局C是雙值的，那麼一個存在一個0-單值格局E0和一個1-單值格局E1可以從C到達。我們先看E0，一種可能是E0屬於ℂ集合，那麼F0=e(E0)就屬於D集合，顯然F0也是0-單值的；另一種可能是E0不屬於ℂ集合，這時一定在D裡存在一個F0使得從F0可以到達E0，因為D裡隻有單值格局，那麼F0一定是0-單值的。綜合兩種情況，D集合裡必然有0-單值格局。同樣的邏輯對E1也成立，所以D集合裡也必然有1-單值格局。故(1)得證。

簡化一點來說就是，對於E0，我們一定能在D裡找到一個單值格局F0，使得要麼能從E0到F0，要麼能從F0到E0。下面這個盜來的圖形象描繪瞭這一部分證明：

7390dc03d629133554f39de4a773662e來源：http://www.the-paper-trail.org/post/2008-08-13-a-brief-tour-of-flp-impossibility/

現在我們知道D裡面兩種單值格局都有瞭，因為D裡的每個格局都是從ℂ裡的某個格局經過一步e得到的，那麼我們一定能在ℂ裡找到相鄰的兩個格局C0,C1，使得D0=e(C0)是0-單值格局，而D1=e(C1)是1-單值格局。不妨設是C0經過一步e’得到C1。（若則C1經過一步到C0下面的討論也同樣成立）

此時對e' =(p', m')有兩種情況，

情況一：若p’不等於p，也就是說e和e’是作用在不同的節點上的。那麼根據交換律，交換e和e’的順序結果應該不變。我們已經知道瞭C0通過e’到達C1再通過e到達D1。還知道C0通過e到達D0，此時如果讓D0接受事件e’，因為滿足交換律我們應該也得到D1。但這是不可能的因為D0已經是單值格局不能變瞭，所以得出矛盾。見下圖：

be48eba4a7e75415fc85510c4451d87b

情況二：若p’等於p，此時從C0出發必存在一個不涉及節點p的事件序列R，能達到一個單值格局A。（因為我們的算法要在有一個節點掛瞭的時候仍能正常運行，現在就好比是p點掛瞭）現在我們讓D0接到序列R，設結果為E0，也就是說E0=R(e(C0))。因為R不涉及p，根據交換律，我們讓A接收事件e後，也應該得到E0，也就是e(A)=e(R(C0))=R(e(c0))=E0。類似地，我們讓D1接受序列得到E1，也就是說E1=R(e(e'(C0)))，同樣根據交換律，A接收事件e和e’後也應該得到E1，e(e'(A)) = e(e'(R(C0))=R(e(e'(C0)))=E1。但是，A已經是單值格局瞭，不可能既能到E0又能到E1，得出矛盾。

綜合以上所有這些矛盾，說明我們一開始的假設“D裡不包含雙值格局”是不正確的。D裡必定包含雙值格局。所以我們前面說的這個構造無限序列的方法就成立瞭：

所以原始的命題得證：在異步網絡中，隻要有一個節點有可能掛，理論上就不存在一定能在有限時間內結束的共識算法。

總結

這個結論是出乎意料的強，所以這篇論文獲得瞭廣泛的贊譽。給人的第一感覺是，這麼一點點小錯誤都不讓發生，分佈式系統還能有個啥卵用。 實際上也並不需要那麼悲觀，因為真正的網絡不可能是完全異步的，這種陷入無限循環可能性微乎其微。後續的很多研究是把“完全異步”這一條件放寬一點點，然後就有很多可以做到的事情瞭。如果以後有時間我可以寫寫後續。

論文原文：http://groups.csail.mit.edu/tds/papers/Lynch/jacm85.pdf參考資料：http://www.the-paper-trail.org/post/2008-08-13-a-brief-tour-of-flp-impossibility/