在分布式系統中，達成共識意味着什麼
目前，我們已經知道分布式系統有以下特性：
- 程序的并發性
- 全局時鐘缺失
- 元件可能出錯
- 消息需時傳遞
接下來我們會聚焦分布式系統中，“達成共識”究竟是什麼意思。首先有一件很重要的事情得重申一下，“分布式計算有數百種軟硬體架構”；而最常見的形式稱為複制狀态機。
複制狀态機
複制狀态機是一種确定性狀态機，它在許多計算機上存有副本，但整個系統就像單個狀态機那樣運作。任何一台計算機都有出錯的可能，但狀态機依然能正常運作。
-作者制圖-
在複制狀态機中，如果出現一個有效事務（transaction），則事務的輸入集會使得系統的狀态轉變為下一個狀态。事務對資料庫進行原子性的操作，這意味着操作要麼整個完成，要麼等于完全沒發生。在複制狀态機内維護的事務集合又稱為“事務日志”；從一個有效狀态轉變為下一個有效狀态的邏輯，稱為“狀态轉變邏輯”。
換言之，複制狀态機是一個分布式計算機的集合，這些計算機都有相同初值。每一次狀态的轉變方式、下個狀态是什麼，都由相關的程序決定。所謂“達成共識”，意思是全體計算機都同意某個輸出的值。
反過來說，“達成共識”也意味着讓系統中每一台計算機的事務日志保持一緻（也就是它們“達成了共同目标”）。合格的複制狀态機，即使發生以下情況，仍必須不斷将新的事務接收進日志（即“提供有效服務”）：
- 有些計算機發生故障。
- 網絡不可靠，消息可能出現延遲、傳送失敗，或排序混亂。
- 沒有全局時鐘來确定事務順序。
朋友們，這就是所有共識算法的基本目标。
共識問題的定義
隻要能滿足以下條件，我們就說某算法可以實作分布式共識：
- Agreement（一緻性） ：所有非故障節點，都會選擇相同的輸出值。
- Termination（可終止性）：所有非故障節點，最終都標明了某些輸出值，不再反悔。
注意：不同的算法會滿足上述條件的不同變體。舉例來說，某些算法會将 Agreement 拆分為一緻性和總體性；一些算法還加入了有效性（validity）、完整性（integrity），或效率的概念。這些細微的差別不在本文讨論範圍。
廣義來說，共識算法一般會假設系統中有三種角色：
- 提案者（Proposers）：常被稱為上司者或協調者。
- 接收者（Acceptors）：程序，監聽提案者的請求并給出響應值。
- 學習者（Learners）：系統裡的其他程序，接收最終決定的值。
是以，正常情況下，我們能通過三個步驟定義來共識算法：
第一步：選舉 Elect
- 所有程序推舉出某個程序（上司者）來做決策。
- 上司者提出下一個有效的輸出值。
第二步：投票 Vote
- 非故障程序會監聽上司者程序提出的值，并驗證這個值。然後将它作為下一個有效值提出。
第三步：決定 Decide
- 非故障節點必須就單個正确的值達成共識。如果這個值收到滿足某個門檻值條件的投票數，那麼全體程序就會同意這個值為最終共識值。
- 如果沒有達到條件，則重新進行上面步驟。
值得注意的是，每個共識算法都會有些許不同，比如：
- 術語（如，輪次（round）、階段（phase））
- 投票如何進行的，以及
- 決定最終值的标準（例如：驗證條件）。
盡管如此，如果我們能以通用的過程構造共識算法，并保證滿足上述的基本條件，那我們就有了一個能夠達成共識的分布式系統。
你以為非常簡單，對吧？
FLP 不可能定理
......并非如此，說不定你已經預見到了！
回想一下，我們是如何描述同步系統和異步系統之間的差別的：
- 同步通信情況下，消息會在固定時間範圍内發送。
- 異步通信情況下，無法保證消息的傳遞。
這個差異非常重要。
在同步通信環境下有可能達成共識，因為我們能夠假設消息傳遞需要的最長時間。是以在同步消息系統，我們允許不同的節點輪流成為提案者、進行多數投票，并跳過那些沒有在最長等待時間内送出提案的節點。
但正如我們前面提到的，跳脫出可控（即消息延時可以預測）的環境（比如，具有同步原子鐘的資料中心之類的可控環境），假設操作發生在同步通信環境裡是不切實際的。
事實上，多數時候我們無法假設同步通信，是以我們的設計必須面向異步通信環境。
在異步通信環境中，因為我們無法假設一個最大的消息傳遞時間，想要達成 termination 條件是非常困難的。回憶下，要達成共識的其中一項條件是“可終止性”，也就是說每個非故障節點最終都必須標明某組相同的輸出值，而不能永遠遲疑不決。
這也就是大家熟知的“ FLP 不可能性 ”。它是怎麼得到這個名字的？我很高興你這麼問了。
1985年，研究員 Fischer、Lynch 和 Paterson （FLP）中描述了為什麼在異步通信環境下，單個程序故障也會導緻共識無法達成。
簡單來說，因為程序可能在任何時間出錯，是以也有可能發生在正好會影響共識達成的時間點。
-亮點自尋-
這個結果對分布式計算領域帶來重大打擊，但即使如此，科學家仍在不斷嘗試避開 FLP 不可能性問題的方法。
抽象一點來說，有兩個方法能夠避開 FLP 不可能性問題：
- 使用同步性假設
- 使用非确定性機制
（未完）