我們知道，比特幣等區塊鏈是分佈式系統的一個子集，但它和傳統分佈式賬本是有差異的，那這些差異在於哪裡呢？為什麼我們說比特幣是一項重大創新？來自前Coinbase、a16z、高盛的區塊鏈工程師Preethi Kasireddy將在這篇文章中給出她的答案。
你知道分佈式系統是如何工作的嗎？
這可能是一個很難學習的話題，主要是因為圍繞它的知識是很分散的…..
在自我學習分佈式計算這個課題之前，我多次趴到了桌上，但經過多次考驗和磨難，我終於準備好向您解釋分佈式系統的基礎知識。
我還想討論區塊鏈技術對該領域的深遠影響。區塊鏈迫使工程師和科學家們重新審視並質疑分佈式計算中根深蒂固的範式。也許沒有其它技術能夠比區塊鏈更快地促進這一研究領域的進展。
區塊鏈是一種新型的分佈式系統。它的出現始於比特幣，並從此在分佈式計算領域產生了持久的影響。因此，如果你想真正瞭解區塊鏈的工作原理，那麼掌握分佈式系統的原理是至關重要的。
不幸的是，很多關於分佈式計算的文獻，要麼是難以理解的，要麼分散在太多的學術論文當中。而讓問題變得更復雜的是，當前存在著數百種架構，而所有架構都滿足不同的需求。因此，將其歸結為一篇可理解的文章，足以稱得上是一件壯舉。
因為這個領域很廣，我不得不仔細選擇要覆蓋的內容。我還必須進行概括，以掩蓋一些複雜性。請注意，我的目標不是讓你成為該領域的專家。相反，我只是想讓你瞭解一些知識，開啟分佈式系統和共識基礎知識的旅程。
閱讀完這篇文章之後，您將更深入地瞭解到以下這些內容：
- 分佈式系統是什麼？
- 分佈式系統的屬性；
- 在分佈式系統達成共識是什麼意思？
- 理解基礎共識算法（例如DLS和PBFT）；
- 為什麼中本聰共識是一項重大創新？
我希望你準備好了這次學習！
什麼是分佈式系統？
分佈式系統涉及了一組不同的進程（例如，計算機），將消息在彼此之間進行傳遞，並協調以實現共同的目標（即，解決計算問題）。
簡而言之，分佈式系統是一組共同實現統一目標的計算機。雖然這些進程是分開的，但系統對終端用戶而言只是一臺計算機。
正如我所提到的，分佈式系統存在著數百種架構。例如，單個計算機也可以被視為分佈式系統；中央控制單元、存儲器單元和輸入-輸出通道，是協作完成一個目標的單獨進程。
舉飛機的例子，它們的共同努力是讓你從A點到B點：
來源：https：//www.weetech.de/en/news-info/tester-abc/distributed-system-1/在這篇文章中，我們將關注分佈式系統，其中進程是指空間分離的計算機。
注意：我可能會把“節點”、“對等節點”、“計算機”或“組件”這些術語與“進程”互換使用。對於本文而言，它們都意味著相同的事情。同樣地，我可能會使用“網絡”和“系統”這兩個可互換的術語。
分佈式系統的屬性
每個分佈式系統都有一組特定的特徵，這些包括：
A）併發
系統中的進程同時運行，這意味著同時會發生多個事件。換句話說，網絡中的每臺計算機與網絡中的其它計算機，會同時獨立地執行事件。
而這就需要協調。
Lamport, L (1978)：分佈式系統中的時間、時鐘和事件排序
B）缺乏全局時鐘
對於同時運行的計算機集合系統，我們需要某種方法來確定事件的順序。但是，在分佈式計算機系統中，有時不可能明確兩起事件中的哪起事件是先發生的，因為計算機在空間上是分開的。換句話說，沒有一個全局時鐘來確定網絡中所有計算機發生的事件序列。
在《分佈式系統中事件的時間、時鐘和順序》這篇論文當中，Leslie Lamport展示瞭如何通過記住以下因素來推斷出一個事件是否發生在另一個事件之前：
1）消息是在它們被收到之前發送的； 2）每臺計算機都有事件的序列；
通過確定哪個事件是發生在另一個事件之前的，我們可以獲得系統中事件的部分排序。
Lamport的論文描述了一種算法，該算法要求每臺計算機都能夠“聽到”其它每臺計算機。
通過這種方式，事件就可以基於這種偏序進行完全排序。
但是，如果我們完全根據每臺計算機正在聽到的事件進行排序，則可能導致此順序與外部用戶（系統外部）所感知的順序會不同。因此，該論文提到的算法仍然可允許異常行為。
最後，Lamport討論瞭如何通過使用正確同步的物理時鐘來防止這種異常情況。
但是，等等，這裡有一個巨大的警告：協調獨立的時鐘，是一個非常複雜的計算機科學問題。即使你最初準確地設置了一堆時鐘，時鐘也會在一段時間後開始出現差異。這是由“時鐘漂移”問題造成的，這是一種時鐘以稍不同速率計算時間的現象。
本質上，這篇論文證明了，事件的時間和順序，是在空間上分離的分佈式計算機系統的基本障礙。
C）組件的獨立故障
理解分佈式系統的一個關鍵部分，在於承認分佈式系統中的組件會存在故障。這就是它被稱為“容錯分佈式計算”的原因。
擁有一個沒有故障的系統是不可能的。真實的系統會存在很多可能的缺陷或弱點，無論這是一個進程崩潰，消息丟失、扭曲或重複，還是網絡分區延遲或出現丟棄消息的情況，甚至會出現進程完全失控，並根據一些惡意計劃發送消息的情況。
這些失敗大致可分為三類：
- 崩潰失敗：組件在沒有警告的情況下停止工作（例如，計算機崩潰）；
- 遺漏：組件發送了消息，但其它節點並沒有收到消息（例如，消息丟失了）
- 拜占庭：組件的表現是任意的。在受控環境下（例如Google或Amazon數據中心）出現這類故障是無關緊要的，其中可能沒有什麼惡意行為。相反，這類錯誤會發生在所謂的“對抗性環境”下。基本上，當一組分散的獨立行動者充當網絡中的節點時，這些行動者可能選擇以“拜占庭”的方式行事。這意味著他們會惡意選擇更改，阻止或不發送消息。
考慮到這些問題，我們的目標是設計一種協議，它可允許具有故障組件的系統，仍可實現共同目標，並提供有用的服務。
鑑於每個系統都會有故障，我們在構建分佈式系統時必須做出的核心假設是，即使其部件偏離了正常行為，它也能繼續存活，無論是否由於非惡意行為（崩潰失敗或遺漏錯誤）還是因為惡意行為（即拜占庭故障）。
從廣義上講，製作分佈式系統時，需考慮兩種類型的模型：
1）簡單的容錯
在一個簡單的容錯系統中，我們假設系統的所有部分都執行以下兩種操作之一：它們要麼完全遵循協議，要麼失敗。這種類型的系統，應能夠處理脫機或失敗的節點。但它不必擔心節點表現出隨意或惡意行為。
2）拜占庭容錯
簡單的容錯系統在不受控制的環境當中，並不是很有用。在一個去中心化的系統當中，節點是由獨立的參與者控制的，它們之間在開放的、無需許可的互聯網上進行通信，我們還需要為那些選擇惡意或“拜占庭”行為的節點進行設計。因此，在拜占庭容錯系統當中，我們假設節點是可以失敗或惡意的。
2b）BAR容錯
儘管大多數真實系統都被設計為能夠承受拜占庭式的故障，但一些專家認為它過於籠統，並沒有考慮到“理性”故障（其中節點可能出於自身利益的考慮而出現偏差行為）。
換句話說，根據激勵的情況，節點是可以誠實的，也可以是不誠實的。如果激勵措施足夠高，那麼即使是大多數節點也可能會做不誠實的事。更正式地講，這被定義為BAR模型，它同時考慮了拜占庭和理性故障問題。 BAR模型假設有三種類型的成員：
- 拜占庭 ：拜占庭節點是惡意的，它們試圖搞砸你；
- 利他主義者：誠實的節點總是遵循協議。
- 理性節點：理性節點只有在他們認為合適時才會遵循協議。
D）消息傳遞
如上面所述，分佈式系統中的計算機，通過一臺或多臺其他計算機之間的“消息傳遞”進行通信和協調。消息可使用任何消息傳遞協議進行傳遞，無論是HTTP，RPC還是為特定實現構建的自定義協議。
有兩種類型的消息傳遞環境：
1）同步
在同步系統中，假設消息將在某個固定的已知時間內進行傳遞。
同步消息傳遞在概念上並沒有那麼複雜，因為用戶擁有一個保證：當他們發送消息時，接收組件將在特定時間範圍內獲得它。這允許用戶使用固定的時間上限來建模他們的協議，該上限是消息到達那裡所需的時間。
但是，在真實的分佈式系統中，這種類型的環境並不是那麼實用，因為計算機可能會崩潰或脫機，並且可能會丟失、複製、延遲或無序接收消息。 2）異步
在異步消息傳遞系統中，假設網絡可能無限延遲消息，複製消息或無序傳遞消息。換句話說，消息接收的時間長度，沒有設置固定的上限。
在分佈式系統達成共識是什麼意思？
到目前為止，我們已經瞭解了分佈式系統的以下屬性：
- 進程的併發性；
- 缺乏全局時鐘；
- 存在故障進程；
- 消息傳遞
接下來，我們將專注理解在分佈式系統中實現“共識”意味著什麼。但首先，重申我們之前提到的內容會是非常重要的：目前有數百種不同的用於分佈式計算的硬件和軟件架構。
其中最為常見的形式被稱為複製狀態機。
複製狀態機
複製狀態機是一種確定性狀態機，很多計算機會對其進行復制，但它是作為單個狀態機運行的。這些計算機中的任何一臺都可能出現故障，但狀態機仍是可運行的。
在複製狀態機中，如果交易有效，則一組輸入將導致系統狀態轉換到下一個狀態。一筆交易是在一個數據庫中進行的原子操作。這意味著操作要麼完全完成，要麼根本不發生。在複製狀態機中維護的交易集被稱為“交易日誌”。
從一個有效狀態轉換到下一個有效狀態的邏輯，被稱為“狀態轉換邏輯”。
複製狀態機是一組分佈式計算機，它們都以相同的初始值開始。對於每個狀態轉換，每個進程決定下一個值。而達到”共識”，意味著所有計算機必須共同商定該值的輸出。
反過來，這在系統中的每臺計算機上都保持一致的交易日誌（即“實現共同目標”）。
複製狀態機必須不斷地將新交易接收到該日誌當中（即，“提供有用的服務”）。它必須這樣做，儘管存在以下這些因素：
- 有些計算機會出現故障；
- 網絡不可靠，消息可能會出現無法傳遞、延遲或出現故障的現象；
- 沒有全局時鐘來幫助確定事件的順序；
而這些，就是任何共識算法要去實現的基本目標。
確定了共識問題
如果算法滿足以下條件，則我們說該算法達成了共識：
- 協議：所有非故障節點決定相同的輸出值；
- 終止：所有非故障節點最終決定某些輸出值；
（注意：不同的算法具有上述條件的不同變化。例如，有些人將協議屬性劃分為一致性和整體性。有些人則對有效性、完整性或效率會有概念，但是，沒有必要在這篇文章當中探討這樣的細微差別。）
從廣義上講，共識算法通常假設系統中有三種類型的參與者：
- 提議者（Proposers）；
- 接受者（Acceptors）；
- 學習者（Learners）；
提議者通常也被稱為領導者或協調者。接受者是監聽來自提議者的請求，並用值進行響應的進程。學習者是系統中的其它進程，它們學習決定的最終值。
通常，我們可以通過三個步驟定義共識算法：
第1步：選舉
- 進程選擇單個領導者來做出決策。
- 領導者提出下一個有效的輸出值。
第2步：投票
無故障進程會監聽領導者提出的值，對其進行驗證，並將其作為下一個有效值。
第3步：決定
- 無故障進程必須就單個正確的輸出值達成共識。如果它收到滿足某些標準閾值數量的相同投票，則進程將決定該值。
- 否則，步驟重新開始。
重要的是，每個共識算法都會有不同：
- 術語（例如輪次、階段）
- 如何處理投票的進程；
- 如何確定最終值的標準（例如，有效性條件）；
儘管如此，如果我們可使用這個通用進程來構建一個算法，它可保證上面定義的一般條件，那我們就有了一個能夠達成共識的分佈式系統。
聽起來，很簡單，對嗎？
FLP不可能
… 並不是的。但是你很快就會了解到了！
回想一下，我們如何描述同步系統和異步系統之間的區別：
- 同步環境是在固定時間範圍內傳遞消息的地方；
- 異步環境是消息的傳遞無保證的地方；
這種區別很重要。
在同步環境中達成共識是可能的，因為我們可假設消息傳遞所需的最長時間。因此，在這種類型的系統中，我們可允許系統中的不同節點輪流提出新的交易，輪詢多數投票，如果在最長時限內未提供提議，則跳過任何節點。
但如前所述，假設我們在同步環境中操作，在受控環境（其消息延遲可預測）之外進行是不實際的，例如具有同步原子鐘的數據中心。
實際上，大多數環境不允許我們進行同步假設，所以我們必須為異步環境而進行設計。
如果我們不能在異步環境中假設最大的消息傳遞時間，那麼實現終止會困難得多。請記住，達成共識必須滿足的條件之一是“終止”，這意味著每個非故障節點必須決定某些輸出值。
這被稱為“FLP不可能結果”。它是如何得到這個名字的呢？好吧，很高興你能問這個問題！
研究人員Fischer, Lynch和Paterson在1985年撰寫的《在一個錯誤進程中不可能達成分佈式共識》這一論文中提到，即使只是一個錯誤的進程，也無法在確定性異步進程中達成共識。
基本上，由於進程可能在不可預測的時間點失敗，因此它們也可能在阻止達成共識的恰當時機失敗。
這個結果對分佈式計算領域而言是一個巨大的頭疼點。儘管如此，科學家們還是在繼續努力尋找繞過FLP不可能的方法。
在較高的層面上，有兩種方法可以避免FLP不可能：
- 使用同步假設；
- 使用非確定論；
現在，讓我們深入瞭解這兩種方法。
方法1:使用同步假設
好吧，我知道你在想什麼：這到底意味著什麼？
讓我們重新審視我們的不可能結果。這裡有考慮它的另一種方式：FLP不可能結果基本上表明，如果我們不能在系統中取得進展，那麼我們就無法達成共識。換句話說，如果異步傳遞消息，則無法保證終止。回想一下，終止是一個必需條件，這意味著每個非故障節點最終必須決定一些輸出值。
但是，如果我們不知道異步網絡何時會傳遞消息，我們如何才能保證每個非故障進程都能決定一個值？
要明確的是，這一發現並未表明共識無法實現，相反，由於不同步，在固定的時間內無法達成共識。說共識是“不可能的”，只是意味著共識“並非總是可行的”，這是一個微妙但至關重要的細節。
避免這種情況的一種方法是使用超時設定。如果在確定下一個值沒有進展，我們會等待一個時間段，然後再重新開始步驟。
正如我們即將看到的那樣，像Paxos和Raft這些共識算法就是這樣的。
Paxos算法
Paxos算法的提出是在20世紀90年代，這也是第一個真實可用的容錯共識算法。它是首個被廣泛採用的共識算法，並曾被谷歌和亞馬遜等全球互聯網公司用於構建分佈式服務。
Paxos的工作方式如下：
階段1：準備請求
- 提議者選擇新的提案版本號 (n) ，並向接受者發送“準備請求”。
- 如果接受者收到準備請求（“prepare,” n），其n大於他們已經回覆的任何準備請求，接受者發出 (“ack,” n, n’, v’) 或(“ack,” n, ^ , ^)。
- 接受者以承諾回應，表示不再接受編號小於n的任何提案。
- 接受者建議他們已接受的最高數提案的值 (v)（如果有的話），否則，他們會以^回應；
階段2：接受請求
- 如果提議者收到來自大多數接受者的響應，那麼它可以發出一個接受請求（“accept,” n, v），其數量為n，值為v。
- n是準備請求中出現的數字。
- v是響應中編號最高的提議值。
- 如果接受者收到一個接受請求 (“accept,” n, v)，它會接受該提議，除非它經響應了一個數字大於n的準備請求。
階段3：學習階段
- 每當接受者接受提議時，它會響應所有學習者 (“accept,” n, v)
- 學習者從大多數接受者那裡接收 (“accept,” n, v) ，決定v，並向所有其他學習者發送(“decide,” v) ；
- 學習者接受 (“decide,” v)並決定v；
來源： https://www.myassignmenthelp.net/paxos-algorithm-assignment-help嗯！困惑了嗎？我知道這裡有很多信息需要去消化。但是，等等……還有更多的信息！
我們現在知道，每個分佈式系統都是有故障的。在Paxos算法中，如果提議者失敗（例如，因為存在遺漏錯誤），則可延遲決策。 Paxos通過從第1階段的新版本號開始處理此問題，即使之前的嘗試從未結束。
我不會詳細介紹，但在這種情況下，恢復正常運行的進程是非常複雜的。
Paxos難以理解的主要原因，是它的很多實現細節都留給了讀者：例如我們如何知道提議者什麼時候失敗？我們是否使用同步時鐘來設置超時時間，來決定提議者何時失敗？等等。
Paxos在領導者選舉，故障檢測和日誌管理等內容是模糊或完全不明確的。
這種設計選擇最終成為Paxos最大的缺點之一，它不僅難以理解，而且也很難實現。反過來，這使得分佈式系統領域也難以駕馭。
到目前為止，你可能想知道同步假設的來源。
在Paxos中，雖然算法中沒有明確的超時，但在實際實現時，在一些超時時間之後選擇一個新的提議者是實現終止所必須的。否則，我們就無法保證接收者會輸出下一個值，系統可能會因此停止運行。
Raft算法
2013年，Ongaro和Ousterhout發佈了一種名為Raft的複製狀態機共識算法，其核心目標是可理解性（與Paxos的最大不同之處）
我們從Raft算法學到的一個重要新事物，是使用共享超時的概念來處理終止問題。在Raft中，如果你崩潰了並重新啟動，你需要等待至少一個超時時間，才能讓自己被宣佈為領導者，並保證你取得進步。
但等等…拜占庭環境呢？
雖然傳統的共識算法（例如Paxos和Raft）能夠使用某種程度的同步假設（即超時）在異步環境中發展，但它們不是拜占庭容錯的。它們只是崩潰容錯的。
崩潰故障是較容易處理的，因為我們可以將進程建模為工作或崩潰 （0或1），進程不能惡意行事或撒謊。因此，在崩潰容錯系統中，分佈式系統是可構建的，其中簡單的多數參與者就足以達成共識。
而在開放和去中心化的（例如公鏈）系統中，用戶無法控制網絡中的節點。相反，每個節點都會針對其各自的目標做出決策，這可能與其他節點的目標衝突。
在拜占庭系統中，節點具有不同的激勵，它們可以撒謊、協調或任意行動，你不能假設簡單的多數節點就能夠達成共識。一半或更多的誠實節點是可相互協調和欺騙的。
然而，Raft並不是為了容忍這種行為而設計的。例如，如果當選的領導者是拜占庭，並且與其他節點保持強大的網絡連接，則可能會危及系統。
Raft和Paxos是簡單的容錯，但不是拜占庭容錯。拜占庭將軍問題
試圖建立一個可處理衝突信息進程的可靠計算機系統，被稱為“拜占庭將軍問題”。拜占庭容錯協議應該能夠實現其共同目標，即使是遭受來自節點的惡意行為。
Leslie Lamport，Robert Shostak和Marshall Pease撰寫的《拜占庭將軍問題》論文，提供瞭解決拜占庭將軍問題的第一個證明：它表明具有x個拜占庭節點的系統，必須至少有（3x + 1）個總節點，才能達到共識。
原因如下：
如果x節點出現故障，則系統需要與（n-x）節點協調後才能正常運行（因為x節點可能有故障（拜占庭）並且沒有響應）。但是，我們必須為不響應的可能沒有錯誤的X節點做準備，它也可能是做出回應的X節點。如果我們希望非故障節點的數量超過故障節點的數量，我們至少需要（n-x-x）> x，因此，n> 3x + 1是最佳的。
但是，該論文中演示的算法僅適用於同步環境。這不是一個好消息！看起來，我們只能得到一個或另一個（拜占庭vs異步），對嗎？
但為什麼不包括兩個呢？
簡而言之，建立一個能夠承受異步環境和拜占庭環境的共識算法……好吧，這就像創造奇蹟一樣。
像Paxos和Raft這樣的算法，是眾所周知且被廣泛使用的。但也有很多學術工作正在嘗試研究拜占庭+異步的共識算法。
所以繫上你的安全帶……
我們將要實地考察理論學術論文的領域。
你應該感到興奮！還記得我們之前討論過的“創造奇蹟”嗎？
我們將查看兩種算法（DLS和PBFT），這些算法要比以往任何時候都更接近於打破拜占庭+異步的障礙。
DLS算法
由Dwork，Lynch和Stockmeyer共同撰寫的論文《部分同步存在下的共識》引入了拜占庭容錯共識的一項重大進步：它定義瞭如何在一個“部分同步系統”中達成共識，該算法也因三位作者的名字而被稱為“DLS”算法。
你可能還記得，在同步系統中，消息從一個處理者發送到另一個處理者所需的時間有一個已知的固定上限。在異步系統中，則不存在固定的上限。
而部分同步，則位於同步系統和異步系統之間。
該論文解釋了部分同步假設的兩個版本：
- 假設消息傳遞的長短存在固定邊界。但它們不是先驗已知的。無論實際的界限如何，目標都是達成共識。
- 假設消息傳遞的上限是已知的，但它們只能保證在某個未知時間開始（也稱為“全球標準化時間”，GST）。目標是設計一個能夠達成共識的系統，無論何時發生。
以下是DLS算法的工作原理：
一系列round分為“嘗試”和“鎖定釋放”階段。
- 每一輪都有一個提議者，並從每個進程開始，傳達他們認為正確的值。
- 如果至少有（N − x）個進程傳達了一個值，則提議者“提出”該值。
- 當進程從提議者處接收建議值時，它必須鎖定該值，然後廣播該信息。
- 如果提議者從x + 1進程接收到他們鎖定某個值的消息，則將其作為最終值提交。
DLS是一項重大技術突破，因為它創造了一種新的網絡假設類型，即部分同步，其還證明了這種假設的共識是可能的。DLS論文中另一個必要的內容，是將拜占庭和異步設置達成共識的問題分為兩個方面：安全性和活躍性。
安全性
這是我們前面討論過的“協議”屬性的另一個術語，其中所有非故障進程都對同一輸出達成一致。如果我們能夠保證安全性，則我們能夠保證整個系統保持同步。我們希望所有節點同意交易日誌的總順序，儘管會存在失敗和惡意行為者的干擾。而違反安全性，意味著我們最終會得到兩個或更多有效的交易日誌。
活躍性
這是我們早期討論的“終止”屬性的另一個術語，其中每個非故障節點最終決定某些輸出值。在區塊鏈設置當中，活躍性意味著區塊鏈通過添加有效新區塊而不斷增長。活躍性是很重要的，因為它是網絡繼續有用的唯一方式，否則，網絡就會停滯不前。
正如“FLP不可能”告訴我們的，在完全異步的系統中是無法達成共識的。而 DLS論文認為，為實現活躍條件而做出部分同步假設，足以克服FLP不可能性。
因此，這篇論文證明了算法不需要使用任何同步假設來實現安全條件。
很明確，對吧？如果不是，不要擔心。讓我們深入探討這個概念：
請記住，如果節點沒有決定某個輸出值，系統就會暫停。因此，如果我們做出一些同步假設（即超時），以保證終止，並且其中一個會失敗，那麼這也會使系統停止。
但是，如果我們設計一個算法，其中我們假設了超時（以保證安全性），而如果同步假設失敗，則會帶來導致兩個有效交易日誌的風險。
這比前一種選擇會危險得多。如果服務損壞（即沒有安全性），則沒有必要提供有用的服務（即活躍性）。
基本上，擁有兩個不同的區塊鏈，會比整個區塊鏈停止會更糟。
分佈式系統總是需要權衡利弊的，如果你想克服限制（例如FLP不可能），你必須在其它地方做出犧牲。在這種情況下，將關注點分解為安全性和活躍性是非常好的。它允許我們構建一個在異步設置中安全，但仍需要某種形式超時來保持生成新值的系統。
儘管DLS論文提供了所有內容，但DLS算法從未真正被廣泛實施，或用於真實世界的拜占庭式設置。這可能是由於DLS算法的核心假設之一，是使用同步處理器時鐘（以便具有共同的時間概念）。實際上，同步時鐘容易受到大量攻擊，並且它在拜占庭容錯設置中並不是很好。
PBFT算法
另一種由Miguel Castro和Barbara Liskov於1999年發表的拜占庭容錯算法，被稱為“實用拜占庭容錯”（PBFT）。對於展示拜占庭行為的系統而言，它被認為是一種更為“實用”的算法。
從這個意義上來說，“實用”意味著它可以在互聯網等異步環境中運行，此外它也進行了一些優化，使其較以前的共識算法要更快。該論文中提到，以前的算法雖然被證明是“理論上可行的”，但它們要麼太慢，無法被使用，要麼是為了安全性而做了假定同步。
正如我們已經解釋的那樣，在異步設置中，這可能是非常危險的。
簡而言之，PBFT算法表明，假設（n-1）/ 3 個節點出現了故障，它可以提供安全性和活躍性。正如我們之前討論的那樣，這是我們需要容忍拜占庭故障的最小節點數。因此，該算法的抵抗性是最理想的。
無論有多少節點出現故障，該算法都能夠提供安全性。換句話說，它沒有為安全性而假設同步。然而，該算法確實依賴於同步性來實現活躍：
最多的情況下，（n-1）/ 3 個節點可出現故障，並且消息延遲的增長速度不會超出某個時間限制。
因此，PBFT通過使用同步假設來保證活躍性，從而規避了FLP不可能性。
該算法通過一系列“view”，其中每個view都有一個“主要”節點（即領導者），其餘view都是“備份”節點。以下是有關PBFT工作方式的逐個步驟：
- 在客戶端上發生了一筆新的交易，並向主要節點廣播；
- 主要節點將它複製到所有的備份節點；
- 備份節點執行交易，並向客戶端發送回覆；
- 客戶端希望從備份節點處獲得x + 1個與結果相同的回覆。這是最終結果，且狀態轉變發生了。
如果領導者沒有發生錯誤，協議會工作得很好，然而，檢測不良主要節點和重新選擇新主要節點（稱為view變化）的過程是非常低效的。例如，為了達成共識，PBFT需二次數量的消息交換，這意味著每臺計算機都必須與網絡中的每臺其他計算機進行通信。
（注：完整解釋PBFT算法需另起一篇文章，這裡不會詳細解釋。）
雖然PBFT是對以前算法的改進，但對於存在大量參與者的真實世界應用（例如公鏈）而言，它的擴展性是不夠的。但是，嘿，至少在涉及故障檢測和領導者選舉（與Paxos不同）方面，該算法會顯得更明確一些。
承認PBFT算法的貢獻是重要的，它結合了重要的革命思想，而新的共識協議（特別是後區塊鏈世界）可從中學習和進行改進。
例如，Tendermint是一種受PBFT影響很大的新共識算法。在Tendermint的“驗證”階段，其使用了兩個投票步驟（和PBFT一樣）來決定最終值。與PBFT算法的主要區別在於，Tendermint的設計，會更加實用。
例如，Tendermint每輪都會輪換新的領導者。如果當前輪次的領導者在一段時間內沒有響應，其會跳過領導者，並且算法會簡單地移動到帶有新領導者的下一輪。這實際上比每次需要進行view更改和選擇新領導者時使用點對點連接更有意義。
方法2：非確定論
正如你從上面瞭解到的，大多數拜占庭容錯共識協議，最終使用某種形式的同步假設來克服FLP不可能性。然而，還有另一種方法可以克服FLP不可能性，即：
非確定論。進入中本聰共識
正如我們剛剛瞭解到的那樣，在傳統的共識中，f（x）被定義為提議者和一群接受者必須全部協調和通信，以決定下一個值。
這太複雜了，因為它需要知道網絡中的每個節點，以及每個節點與其它節點的通信（即，二次通信開銷）。簡而言之，它不能很好地擴展，並且不能在開放、無需許可的系統中工作（其中任何人都可以隨時加入和離開網絡）。
而中本聰共識的聰明之處，在於概率性地完成了上述的過程。相比每個節點都同意一個值，f(x) 是使所有節點都同意值是正確的可能性。
等等，這意味著什麼？
拜占庭容錯
相比選舉一個領導者，然後與所有節點協調，而是根據哪個節點能夠最快解決計算難題來解決共識。比特幣區塊鏈中的每個區塊，都由解決這個難題的節點添加。擁有最多累積工作量的鏈（即累積難度）即是標準鏈。最長的鏈，不僅可作為區塊序列的證明，而且可以證明它來自最大的CPU功率池。因此，只要大部分CPU功率由誠實節點控制，它們將繼續產生最長鏈，並超過攻擊者。
區塊獎勵
中本聰共識，通過假設節點為爭奪下一個區塊，會擴展計算投入的方式而工作。該算法的聰明之處，在於經濟上激勵節點重複執行這種計算，以獲取隨機獲得區塊獎勵的機會。
抵抗女巫（Sybil）攻擊
解決這個難題所需的工作量證明，使得協議本身具有抵抗女巫攻擊的特性。它不需要PKI或任何其他花哨的身份驗證方案。
對等gossip
中本聰共識的主要貢獻，是使用了gossip協議，它更適合於無法假設非故障節點間通信的對等設置。相反，我們假設節點僅連接到其它節點的子集。然後，我們使用對等協議，其中消息在節點之間互相傳播。
在異步環境中，並不是“技術”安全的
在中本聰共識中，安全保障是概率性的，我們會不斷增長最長鏈，而每個新區塊都會降低惡意節點嘗試構建另一個有效鏈的可能性。
因此，中本聰共識在技術上並不保證異步設置的安全性。讓我們花點時間瞭解下原因。
對於在異步設置中實現安全性條件的系統，我們應該能夠在異步網絡條件下維護一致的交易日誌。考慮它的另一種方式，是節點可隨時脫機然後再返回在線狀態，並使用區塊鏈的初始狀態來確定最新的正確狀態（而不管網絡狀況如何）。任何誠實節點都可以查詢過去的任意狀態，並且惡意節點不能提供誠實節點認為是真實的欺詐性信息。
在本文討論的前幾種算法中，這是可能的，因為我們確定性地在每一步完成一個值。只要我們終止每個值，我們就可以知道過去的狀態。然而，比特幣在“技術上”不是異步安全的，其原因是有可能存在一個網絡分區，其中攻擊者具有足夠強大的算力來創建一條比誠實鏈更快的替代鏈。在這個替代鏈上，攻擊者可嘗試改變他自己的一筆交易來收回他所花的錢。
不可否認的是，這就要求攻擊者獲得大量的算力，而這需要大量的資金。
從本質上講，比特幣區塊鏈的不可更改性來源於這樣一個事實：即大多數礦工實際上並不想採用替代鏈。這是因為，要掌握足夠的算力以使其餘礦工採用替代鏈是很困難的。換句話說，成功創建替代鏈的可能性是非常低的，它幾乎可以忽略不計。
中本聰共識 vs 傳統共識算法
出於實際目的，中本聰共識是拜占庭容錯的。但它顯然沒有達成共識研究人員傳統上所假設的共識。因此，它最初被視為完全脫離拜占庭容錯世界。
感謝你，中本聰！
根據設計，中本聰共識可以讓任意數量的節點以開放式的方式參與系統，而且沒有人必須要知道完整的參與者集。這一突破的重要性不容小覷！
它比以往的共識算法要更簡單，它消除了以前共識算法在點對點連接、領導者選舉、二次通信開銷等方面的複雜性。你只需在任何計算機上啟動比特幣協議軟件，並開始挖礦任務。
這使其可在真實環境中輕鬆部署，它確實是比PBFT更“實用”的共識算法。
結論
現在你應該對分佈式系統共識算法的簡要基礎知識有所瞭解了。對於分佈式計算而言，這是一個漫長而曲折的研究和獨創性之旅。我希望這篇文章能夠有助於你對這個領域有更多的瞭解。
中本聰共識是一項真正的創新，它讓研究人員、科學家、開發者和工程師在共識協議研究中不斷開天闢地。
還有一個全新的協議系列正在不斷開發中，嗯，它就是權益證明（Proof-of-stake），作者在接下來的文章中會談到，敬請關注 ;）
注：為了簡單目的，作者跳過了很多重要的論文和算法。例如Ben Orr的Common Coin也使用了概率方法，但它沒有最佳的抵抗性。其它算法如哈希現金（Hash Cash）也使用PoW，但其是用於限制電子郵件垃圾郵件和拒絕服務攻擊目的的。這篇文章遺漏了很多傳統的共識協議！但作者認為，上述內容足以幫助你瞭解傳統共識算法和中本聰共識算法的不同。
特別感謝Zaki Manian提出的有關分佈式共識的所有問題。
原文：https://medium.com/@preethikasireddy/lets-take-a-crack-at-understanding-distributed-consensus-dad23d0dc95
作者：Preethi Kasireddy
翻譯：灑脫喜
稿源（譯）：巴比特資訊（http://www.8btc.com/distributed-consensus-2)
閱讀更多 以太中文網 的文章
