如何淺顯易懂地解說 Paxos 的演算法？

12-27

http://zh.wikipedia.org/wiki/Paxos%E7%AE%97%E6%B3%95

之前的回答本來就覺得一些細節處並不嚴謹，現在回看=/=。我覺得嚴謹是一個討論技術的必要條件，覺得現在也有能力寫的嚴謹，於是想把回答改的盡量嚴謹，最後發現不如重寫，順便補充了我想補充的內容，結果就是更長=.=。Paxos是個精巧，又強大的協議，僅從過程的複雜度來說，確實如作者本人一再說的那樣是個「簡單的協議」，但是可以從非常多的角度來理解它為何正確，而原本的流程也並不適合直接工程化，這也是大概為什麼工程上它存在如此多的變體。希望這個回答的讓人更快的感受paxos的魅力，建立一個初步印象的同時不給人以誤導。最後依然推薦larmport自己寫的和paxos相關的三篇論文：&<&< The Part-Time Parliament&>&>、&<&&>、&<&&>前面關於Paxos的論述。
2016/12/28

上周和一個有真正paxos工程經驗的人討論一下paxos，paxos現在大多是應用於replication的一致性，用來實現一個多節點一致的日誌，和他的討論讓我覺得要想真正的精確掌握paxos和它對應的強一致性領域，也許只有真正的在工程中實現過才行。這個回答只能當做是想要了解原理的入門吧，甚至可能有些微妙的地方還會產生誤導。它介紹了paxos面向的問題，以及為何它的流程要這麼設計，但還是希望對有興趣閱讀這個問題的有所幫助。
2016 10/30

現在看開頭這段話是在是覺得有點羞恥，遂改之。我了解paxos是從找工作開始，比較詳細的了解則是在畢設，自己動手了寫了個類似Zookeeper的系統，paxos本身並不複雜，在&<&

&> Lamport用兩段話就描述清楚了它的流程，他老人家也說paxos其實是個簡單的演算法。但是是我在工程領域見過最為精妙的演算法。我想論述Paxos為什麼難以理解會比描述Paxos的流程長的多的多。我最初學習Paxos是從《從Paxos到Zookeeper:分散式一致性原理與實踐》，現在看來並不是個很好選擇，作者講解的方式是直接翻譯論文，論述ZAB和paxos關係的部分我也覺得不是很嚴謹。如果真心覺得Paxos的原文不知所云，也不知道能拿來幹嘛，可以從閱讀Raft的論文開始，如果真的有興趣，強推Raft作者Diego Ongaro那篇300頁的博士論文《CONSENSUS: BRIDGING THEORY AND PRACTICE》，不只是講解了Raft協議，而且系統的論述Paxos類似的一致性協議，不僅從原理，也從工程角度出發，涉及方方面面，在寫畢設中了就是寫不動就翻翻的良作。我個人覺得閱讀任何號稱淺顯易懂的解說Paxos演算法的描述（比如下文=/=），最多只是讓你更好的入門，要更深的理解Paxos以及所有等同於它的一致性協議，ZAB,Raft,ViewStamp，直接閱讀相關論文，理解證明，理解它們哪裡不同，為何本質上相同，與人探討，在工程上自己實現，或者閱讀開源實現的源代碼才是最好的方式。分散式一致性是個有趣的領域，而Paxos和類似的協議對這個問題的重要性不喻，在過去的十年，Paxos幾乎等價於分散式一致性。
2016 6/20

之前的答案最大的不嚴謹之處在於兩個事件「先後」這種時序關係的處理上。paxos是個分散式一致性協議，它的事件需要多個節點共同參與，一個事件完成是指多個節點上均完成了自身負責的單機子事件(就讓我門把這樣的事件稱為"分散式事件")，這樣的分散式事件可以看作是多個單機子事件的複合，但是即不能從兩個分散式事件的先後推導出某個節點上它們的單機子事件的先後，也不能根據某個節點上兩個單機子事件的先後斷言它們對應的分散式事件的先後。舉一個簡單的例子，兩個節點P1，P2;分散式事件a1設置每節點的本地變數v=1,分散式式事件a2設置每個節點本地變數v=2，如果我們稱a1先於a2完成，那麼對於節點P1而言，v=1發生在v=2之前還是之後都有可能;反之如果P1上v=1發生在v=2之前，a1和a2哪個縣完成也都有可能。

原來的回答有些地方論述分散式事件a1在a2之後(先)時，默認了單節點上，a1會比a2先達成狀態，或者反之。

實際上為了論證paxos的正確性，並不需要藉助於分散式事件的時序(起碼無用太在意物理時序），對於paxos流程中的分散式事件，例如提案被通過，值被決定，讓我們忘記它們之間物理時間上的先後關係吧。

下面就開始假裝推導出paxos，作為一種理解協議的流程和協議如何保證正確性的方式。這樣的推導的過程遠比我想像的冗長；相比之下，論文中Lamport自己推導出Paxos的過程簡潔、巧妙、漂亮，但是更抽象。在末尾用自己的語言描述了這種方式，作為補充。補充的版本基本思路來自&<&&>，和原文略有不同；總共不到1500字，卻既說明了Paxos是如何得到的，又嚴謹的論證了Paxos的正確性。

首先我們簡單介紹paxos所保證的一致性的具體含義；達成一致的條件(何時達成一致）；基於的一個基本的數學原理；以及它需要滿足的假設。

什麼是一致性?實際上這個詞在不同地方語義並不那麼一致，Paxos面向的是一個理論的一致問題，這個問題的通俗描述是：

有一個變數v，分布在N個進程中，每個進程都嘗試修改自身v的值，它們的企圖可能各不相同，例如進程A嘗試另v=a,進程B嘗試另v=b，但最終所有的進程會對v就某個值達成一致,即上述例子中如果v=a是v達成一致時的值，那麼B上，最終v也會為a。需要注意的是某個時刻達成一致並不等價於該時刻所有進程的本地的v值都相同，有一個原因是進程可能掛掉，你不能要求掛掉的進程任何事；更像是最終所有存活的進程本地v的值都會相同。

這個一致性需要滿足三個要求：

1.v達成一致時的值是由某個進程提出的。這是為了防止像這樣的作弊方式：無論如何，最終都令每個進程的v為同一個預先設置好的值，例如都令v=2，那麼這樣的一致也太容易了，也沒有任何實際意義。
2.一旦v就某個值達成了一致，那麼v不能對另一個值再次達成一致。這個要求稱為安全性。
3.一致總是能夠達成，即v總會被決定為某個值。這是因為不想無休止的等待，這個要求也稱為活性。

Paxos中變數v達成一致的條件： N個進程中大多數（超過一半）進程都認為v是同一個值，例如c，那麼我們稱v被決定為c。這樣即使少數進程掛掉了，也不會使得一致無法達成。

Paxos保證的一致性如下：不存在這樣的情形，某個時刻v被決定為c，而另一個時刻v又決定為另一個值d。由這個定義我們也看到，當v的值被決定後，Paxos保證了它就像是個單機的不可變變數，不再更改。也因此，對於一個客戶端可以多次改寫值的可讀寫變數在不同的節點上的一致性問題，Paxos並不能直接解決，它需要和狀態機複製結合。

Paxos基於的數學原理：我們稱大多數進程組成的集合為法定集合，兩個法定集合必然存在非空交集，即至少有一個公共進程，稱為法定集合性質。例如A,B,C,D,F進程組成的全集，法定集合Q1包括進程A,B,C，Q2包括進程B,C,D，那麼Q1和Q2的交集必然不在空，C就是Q1，Q2的公共進程。如果要說Paxos最根本的原理是什麼，那麼就是這個簡單性質。同時，可以注意到，這個性質和達成一致的定義相呼應。

Paxos中進程之間是平等的，即不存在一個特殊的進程，這是由於如果協議依賴於某個特殊的進程，那麼這個進程掛掉勢必會影響協議;而對於分散式環境，無法保證單個進程必然必活，能夠容忍一定數量的進程掛掉，是分散式協議的必然要求。這是推導過程所要遵循的一個原則，就稱為平等性原則好了。

消息是進程間通信的唯一手段，對於分散式環境來說，這是顯然的。

Paxos要求滿足的前置假設只有一個：消息內容不會被篡改；更正式的說是無拜占庭將軍問題。

假裝的推導總是先從一些具體的場景開始，既然Paxos的假設僅僅只是消息不會被篡改,保證了這點任意場景下都能保證一致性，那麼對於舉例的場景它必然是能夠保證一致性的；因此不妨先使得協議流程能在當前場景下能保證一致性，然後再舉出另一個場景，當前的協議流程無法再該場景下滿足一致性，接著再豐富協議流程，滿足該場景，如此往複，最終得到完整的paxos協議，最後再不失一般性的論證協議對任意場景都能保證一致性。

進程的平等性假設會帶來如下的問題，考慮如下的場景1：三個進程的場景P1,P2P3（n個進程的場景類似），P1嘗試令v的值被決定為a,P2嘗試令v被決定為b。假設它們都先改寫了自身的v值，然後發送消息嘗試改修P3的v值。顯然如果P3收到兩個消息後都滿足了它們的企圖，那麼v就會兩次被決定為不同的值，這破壞了之前的定義。因此P3必須得拒絕掉其中一個進程的請求，如何拒絕也是我們最先考慮的問題。一個最簡單的拒絕策略是先來後到，P3隻會接受收到的第一個消息，拒絕之後的消息，即只會改寫v一次。按照這個策略，如果P1發送的消息首先到達P3，那麼P3接受該消息令v=a,拒絕掉後到的來自P2的消息。但是這個策略會引入一個另外的問題；在場景1的基礎上考慮這樣的場景1』，P3也嘗試決定v的值，P3嘗試令v被決定為c，那麼P1，P2，P3都嘗試修改v的值，首先P1令v=a,P2令v=b,P3令v=c(相當於自己給自己發消息），按照之前的策略，每個進程只會改寫v的值一次，那麼將永遠不會出現兩個進程的v值相等的情況，即v永遠無法被決定。更正式的說，這樣的協議不滿足活性，活性要求協議總能達成一致。由此我們也得到第一個結論:進程必須能夠多次改寫v的值。同時我們也要意識到：當進程收到第一個消息時，進程是沒有任何理由拒絕這個消息的請求的。

拒絕策略總是需要有一個依據，之前我們的依據是消息到達的先後，只接受第一個到達的消息，但這導致不滿足活性。現在我們需要另一個拒絕策略，也就是需要另一個依據，這個依據至少能夠區分兩個消息。為此我們引入一個ID來描述這個消息，這樣就可以根據ID的大小來作為拒絕或接受的依據；選擇ID更大的消息接受和選擇ID更小的消息接受是兩種完全對稱的策略，不妨選擇前者。這個策略不會導致明顯的活性問題，ID更大的消息總是能被接受，一個節點可以多次更改v的值。例如在場景1"中，只要P1的消息ID比P3發送給自己的消息ID更大，P3就會接受P1的消息，令v=a，從而令v的值被決定為a。再來考慮最初的場景1，不妨假設P1的消息ID大於P2的消息ID，根據P3收到消息的先後可以分為兩種情況：

1. P3先收到P1的消息，記做場景1-2。由於P1的消息是P3收到的第一個消息，P3接受該請求，令v=a；同時為了能對之後收到的消息作出是否接受的判斷，P3需要記錄該消息的ID作為判斷的依據。之後P3又收到P2的消息，該消息的ID小於P3記錄的ID(即P1的消息ID)，因此P3拒絕該消息，這樣我們的目的就達到。

2. P3先收到P2的消息，記作場景1-3。同樣P3接受該消息，令v=b,記錄該消息的ID。之後P3收到P1的消息，由於P1的消息ID大於P3記錄的ID，因此P3無法拒絕該消息，之前的問題依舊存在。

儘管對於場景1-3，目前的策略依舊無法保證一致性，但是起碼我們縮小協議不適用的範圍。先總結下我們目前的策略，並定義一些稱謂以方便後面的論述。我們稱呼進程P發送的嘗試修改另一個進程中變數v的值的消息稱之為提案，記作Proposal；提案的ID記作proposal_id；提案中會附帶一個值，如果一個進程接受一個提案，則修改自身的v值為該提案中的值。如果一個提案被大多數進程所接受，那麼稱提案被通過，此時顯然v被決定為提案中的值。進程P記錄的接受的提案ID記做a_proposal_id。

之前我們尚未清晰定義a_proposal_id，實際上我們也就並未清晰的定義我們的拒絕策略，當P收到一個提案Proposal-i時，可能已經收到過多個提案，Proposal-i.proposal_id該和其中哪個提案的proposal_id比較，我們並未定義。我們定義為其中的最大者，這樣實際上進程P只需維護一個a_proposal_id即可，當收到一個Proposal時，更新a_proposal_id = Max(Proposal.proposal_id，a_proposal_id）。同時在之前的描述中我們應當注意到實際上一個進程存在兩個功能：

1. 進程主動嘗試令v的值被決定為某個值，向進程集合廣播提案。

2. 進程被動收到來自其它進程的提案，判斷是否要接受它。

因此可以把一個進程分為兩個角色，稱負責功能1的角色是提議者，記作Proposer，負責功能2的角色是接受者，記作Acceptor。由於兩者完全沒有耦合，所以並不一定需要在同個進程，但是為了方面描述，我們假定一個進程同時擔任兩種角色，而實際的工程實現也往往如此。

接著我們嘗試解決場景1-3,這看起來很難。P3作為接受者，收到P2的提案之前未收到任何消息，只能接受該提案，而由於P1的提案proposal_id大於P2的提案，我們的拒絕策略也無法讓P3拒絕P2。我們先不急著推導具體可行的策略，先考慮下解決1-3場景可能的角度，有如下三種角度可以入手：

1. P3能夠拒絕掉P2的提案。

2. P3能夠拒絕掉P1的提案。

3. 限制P1提出的提案中的值，如果P1的提案中的值與P2的提案一致，那麼接受P1也不會破壞一致性。

接著我們分析三個角度的可行性：

角度1需要P3有做出拒絕的依據，由於消息是進程間通信唯一手段，這要求P3在收到P2的提案之前必須先收到過其它消息。對於場景1-3，只有P1，P2是主動發送消息的進程，P2當然不可能額外還發送一個消息試圖令P3拒絕自己隨後的提案。那麼唯一的可能是P1在正式發送提案前，還發送了一個消息給P3，這個消息先於P2的提案到達，給了P3拒絕P2提案的理由。如果沿用目前的拒絕策略，那麼P1隻需先發送隨後提案的proposal_id給P3，P3更新a_proposal_id 為該消息附帶的proposal_id，這樣a_proposal_id將大於P2的提案的proposal_id，而導致P2的提案被拒絕，似乎這是一個可行的角度。

對於角度2，我們目前的策略無法做到這一點，因此除了proposal_id外，我們還得給提案附加上額外的信息作為另外的拒絕策略的依據。提案由進程提出，也許我們可以附加進程的信息，但是就算P3得知P1的提案由P1提出，P3又憑什麼歧視P1，這違反進程的平等性假設。似乎這個角度不是一個好角度。

最後我們分析一下角度3，角度3提供了與1,2截然不同的思路，它不再是考慮如何拒絕，而把注意力放在如何對提案的值做出恰當的限制上。對於場景1-3而言，從這個角度，由於P3無法拒絕P1和P2的提案中的任何一個，因此P1的提案的值就必須與P2的提案一致；這也意味著了P1在正式提出提案前，需要有途徑能獲悉P2的提案的值。如我們上面一直強調的，消息是唯一的通信手段，P1必須收到來自其它節點消息才有可能得知P2提出的提案的值。P1可以被動的等待收到消息，也可以主動的去詢問其它節點等待回復。後者顯然是更好的策略，沒有收到想要的消息就一直等待未免也太消極了，這種等待也可能一直持續下去從而導致活性問題。

經過上面的分析，我們暫時排除了從角度2入手（實際上後面也不會再考慮，因為從1,3入手已經足以解決問題）。下面將沿著角度1,3進行更深入的分析，我們先嘗試從角度1出發，畢竟考慮如何拒絕已經有了經驗。先來總結下我們在分析角度1時引入的額外的流程:

進程P在發送提案前，先廣播一輪消息，消息附帶著接下來要發送的提案的proposal_id。由於該消息和接下來發送的提案相關，且在提案被提出之前發送，不妨稱這個消息為預提案，記作PreProposal，預提案中附帶著接下來的提案的proposal_id。當作為接受者的進程Pj收到預提案後，更新Pj. a_proposal_id。還記得我們之前的拒絕策略中a_proposal_id的更新策略嘛：a_proposal_id = max(proposal_id,a_proposal_id)，a_proposal_id是遞增的。因此如果預提案的proposal_id小於Pj.a_proposal_id，Pj完全可以忽略這個預提案，因為這代表了該預提案對應的提案的proposal_id小於Pj.a_proposal_id，必然會被拒絕。我們沿用之前拒絕策略中a_proposal_id的更新策略。這樣當收到預提案或者提案後，a_proposal_id的值均更新為 max(a_proposal_id,proposal_id)。

接著我們來看看引入了預提案後，能否真正解決場景1-3。根據P1和P2的預提案到達P3的先後也存在兩種場景：

1.場景1-3-1：P1的預提案先到達，P3更新a_proposal_id 為該提案的proposal_id，這導致隨後到達的P2的提案的proposal_id小於a_proposal_id，被拒絕。滿足一致性

2.場景1-3-2：P2的提案先到達，P3接受P2的提案，此時和原始的場景1-3存在同樣的問題。歸根結底，預提案階段能否使得P3拒絕該拒絕的，也依賴消息到達的順序，和提案階段的拒絕策略存在相同的問題，但至少又縮小了不能保證安全性的場景範圍。

幸好我們還有角度3可以著手考慮，所以仍有希望完全解決場景1-3。在深入角度3之前，先總結下協議目前為止的流程，現在協議的流程已經分為了兩個階段：預提案階段和提案階段，兩種消息：預提案 和提案，兩種角色：接受者 和 提議者，流程如下：

階段一 提議者Proposer：向接受者Acceptor廣播預提案，附帶接下來提案Proposal的proposal_id 接受者Acceptor：收到預提案後更新a_proposal_id = max(proposal_id,a_proposal_id)

階段二 提議者Proposer：向接受者Acceptor廣播提案，和之前的預提案共享同一個proposal_id 接受者Acceptor：如果收到的提案的proposal_id&>= a.proposal_id，那麼接受這個提案，更新a_proposal_id = max(proposal_id,a_proposal_id)

為了更形象，之前的討論是基於三個進程的場景,實際上對於N進程的場景也是一樣的。N個進程時，與之前場景1對應的場景是：

N個進程，存在兩個進程Pi,Pj，Pi嘗試另v被決定為a,Pj嘗試另v被決定為b，Pi提出的預提案記作PreProposal-i，提案記作Proposal-i；Pj的預提案PreProsal-j，提案Proposal-j。

之拒絕策略的討論都是基於一個關鍵的進程P3，只要P3最終能拒絕Proposal-i和Proposal-j中的一個，兩個提案就不會都被通過，那麼一致性就不會被破壞。Pi的提案被通過代表了存在一個法定集合Q-i，Q-i中的進程都接受了Proposal-i，Pj同理，存在一個Q-j，Q-j中的進程都接受了Proposal-j。由於法定集合的性質，兩個多數集Q-i和Q-j中必然存在一個公共進程Pk。Pk即相當於場景1中的P3，只要Pk能夠拒絕Proposal-i和Proposal-j中的一個，協議依舊是安全的。為了不失一般性，下面我們都以N個進程的場景作為討論的基礎，稱為場景2，由於場景1和場景2可以一一對應，所以接下來順著限制提案的值的角度，我們直接針對場景2-3-2，之前的場景和場景1一樣，我們的拒絕策略已經足以應付。v的值被決定代表有一個提案，它被法定數目的集合接受，我們稱這為提案被通過。

首先我們看下場景2-3-2，Pi對應場景1-3-2中的P1，Pj對應P2，Pk對應P3。Pj的提案Proposal-j最終會被法定集合Q-j接受，即v的值被決定為b，且Proposal-i.proposal-id &> Proposal-j.proposal_id。我們需要限制Pi的提案的值，不能讓Pi自由的給Proposal-i中的v賦值。在2-3-2中，由於拒絕策略失效，所以只能令Proposal-i.v = Proposal-j.v=b。要做到這一點，正如前面的分析所言，Pi需要先主動詢問進程集合，來得知Proposal-j.v =b這一事實。顯然Pi是沒有先驗信息來得知Proposal-j由哪個進程提出，也不知道Q-i和Q-j的公共節點Pk是誰，因此Pi只能廣播它的查詢。由於我們需要允許少數進程失敗，Pi可能只能得到大多數進程的回復，而這之中可能不包括Pj。我們稱這些回復Pi的查詢的進程的集合為Q-i-2,為了描述更簡單，無妨假設Q-i-2=Q-i。儘管Pi的查詢可能得不到Pj的回復，好在作為將會被通過的提案，Proposal-j將會被Q-j內所有進程接受，因此如果進程作為接受者在接受提案時，順便記錄該提案，那麼Q-j內所有進程都將得知Proposal-j.v=b。由於Pk屬於Q-i和Q-j的交集，所以Pk即收到了Pi的查詢，又接受了提案Proposal-j。之前我們已經引入了預提案階段，顯然我們可以為預提案附帶上查詢的意圖，即Pk作為接受者收到Pi的預提案後，會回復它記錄的接受過的提案。有一個問題是Pk此時是否已經記錄了Proposal-j呢?很巧的是在場景2-3-2中，Pj的提案Proposal-j是先於Pi的預提案PreProposal-i先到達，所以Pk已經記錄了Proposal-j.v = b，Pj收到的來自Pk的回復中包含了提案Proposal-j，而2-3-2之外的場景，拒絕策略已經足以應付。這裡依舊還有兩個問題，先討論第一個：

實際上除了Pi和Pj外可能還會有多個進程發起預提案和提案，所以收到 PreProposal-i時Pk可能已經接受過多個提案，並非只有Proposal-j，那麼Pk應該回復PreProposal-i其中哪個提案，或者都回復？Pk並不知道Proposal-j會被通過，它只知道自己接受了該提案。都回復是個效率很低但是穩妥，可以保證Pk不會遺漏Proposal-j，Pk已經回復了它所能知道的全部，我們也無法要求更多。需要注意到的是進程是平等的，所以Q-i中所有進程都和Pk一樣回復了它接受過的所有提案。當Pi收到所有來自Q-i的回復時，隨之而來的是第二個問題：

Pi收到了多個Proposal作為一個Acceptor組成的法定集合Q-i對PreProposal-i的回復，記這些Proposal組成的集合記坐K-i，那麼它應當選擇K-i中哪個一個提案的值作為它接下來的提案Proposal-i的v值？記最終選擇的這個提案為Proposal-m。

在場景2-3-2中，我們第一直覺是希望選擇的Proposal-m 即是 Proposal-j，但是實際上，我們只要保證Proposal-m .v = Proposal-j.v即可。從另一個角度，K-i中很可能存在這樣的提案Proposal-f,Proposal-f.v!=Proposal-j.v，我們要做的是避免選擇到這類提案。我們可以根據一些依據瞎選碰碰運氣，但是這並明智。我們不妨假設存在一個策略cf，cf滿足需求，使得選擇出提案Proposal-m滿足Proposal-m.v= Proposal-j.v。然後讓我們來分析一下此時Proposal-f有什麼特徵。

Proposal-f能夠被提出，代表存在一個多數集合Q-f，Q-f中每個進程都接受了PreProposal-f，同時假設是進程P-f提出了PreProposal-f和Proposal-f。Q-f和Q-j必然存在一個公共節點，記做Ps，Ps即接受了PreProposal-f又接受了Proposal-j。Ps收到PreProposal-f和Proposal-j的順序只有兩種可能：

1.Ps先收到PreProposal-f

2.Ps先收到Proposal-j

PreProposal-f.proposa-id和Proposal-j. proposal_id的大小也只有兩種可能，不妨先假設PreProposal-f.proposal_id &> Proposal-j.proposal_id。

對於情形1，Ps先收到PreProposal-f，接受它，更新Ps.a_proposal_id = PreProposal-f.proposal_id &> Proposal-j.proposal_id，同時之前的a_proposal_id的更新策略又使得Ps.a_proposal_id是遞增的，於是導致收到Proposal-j時,Proposal-j.proposal_id小於Ps.a_proposal_id,被拒絕，而這於Ps的定義矛盾。

對於情形2，Ps將把提案Proposal-j回復給PreProposal-f。由於我們假設了策略cl的存在，於是P-f在收到所有Q-f對PreProposal-f的回復後，將令Proposal-f.v=Proposal-j.v，cl就是干這個的。因此由於Proposal-f.v!=Proposal-j.v矛盾。

於是當假設PreProposal-f.proposal_id &> Proposal-j.proposal_id 時，情形1,2我們都得出了矛盾，同時兩者的proposal_id又不相等(最初的假設），所以必然PreProposal-f.proposal_id &< Proposal-j.proposal_id，即Propsoal-f.proposal_id &< Proposal-j.proposal_id。

於是我們得到的結論是：如果策略cl存在，提案Proposal-j最終會被通過，任意一個proposal_id更大的預提案PreProposal-i，對於它得到的Q-i的回復K-i中的Proposal-f，只要Proposal-f.v!= Proposal-j.v，那麼必然 Proposal-f.proposal_id &< Proposal-j.proposal_id。既然K-i中所有v值不等於Proposal-j.v的提案，proposal_id都比Proposal-j更小，那代表所有proposal_id比Proposal-j更大的提案，v值都等於Proposal-j.v，因此選擇K-i中proprosal_id最大的提案，就能保證Proposal-i.v = Proposal-j.v。於是我們得到了策略cl的具體形式。

我們得到了具體可行的策略cl是建立在策略cl存在這一前提之上，因此反過來，對於這個具體的選值策略cl，結合之前我們得到了協議流程，它是否能保證如下的性質CP1，依舊需要進一步的論證：
如果一個提案Proposal-j最終會被通過，那麼對於任意的一個提案Proposal-i,如果Proposal-i.proposal_id &> Proposal-j.proposal_id，那麼Proposal-i.v = Proposal-j.v。

我們先總結下目前得到的協議流程：

階段一預提案階段 提議者Proposer：向接受者Acceptor廣播預提案，附帶接下來提案Proposal的proposal_id 接受者Acceptor：收到預提案後更新a_proposal_id = max(proposal_id,a_proposal_id)，如果預提案的proposal_id大於a_proposal_id，那麼回復該預提案的提議者改接受者接受過的所有提案。

階段二提案階段 提議者Proposer：等待直到收到大多數接受者對預提案的回復，從所有回復的提案組合成的集合K中挑選proposal_id最大的提案，以該提案的值作為本次提案的值。如果K是空集，那麼可以給提案任意賦值。 向接受者Acceptor廣播提案，和之前的預提案共享同一個proposal_id 接受者Acceptor：如果收到的提案的proposal_id&>= a.proposal_id，那麼接受這個提案，更新a_proposal_id = max(proposal_id,a_proposal_id)

這些流程是為了解決舉例的場景而不斷豐富的，接著就讓我們論證下協議流程是否總是可以確保CP1。

首先假設Proposal-i.v != Proposal-j.v，如果得出矛盾即可證明CP1。在嘗試推出矛盾前，我們先做一些定義，以便後續的推導。

記大多數接受者組成的法定集合為Q，K是提議者在提案階段收到的所有Q回復的提案組成的集合，如果K不為空，記K中proposal_id最大的提案是MaxProposal(K)，本次提案的值即是MaxProposal(K).v；如果K是空集，那麼MaxProposal(K).v = null。特別的，對於提案Proposal-i,回復它預提案接受者的集合為Q-i,回復的提案組成的集合為K-i，Proposal-i.v = MaxProposal(K-i)，Proposal-i.v=null代表可以隨意賦值。為了描述方便，我們令Proposal-i的proposal_id為i，即Proposal-i代表了proposal_id=i的提案，Proposal-j意味著Proposal-j.proposal_id =j。

論證過程如下：

(1) Proposal-i.v!=Proposal-j.v，即MaxProposal(K-i) .v！= Proposal-j.v，即MaxProposal(K-i)!=Proposal-j

(2) Proposal-j最終會被通過，代表最終會存在一個多數集合Q-j，Q-j中每個接受者都接受了Proposal-j。

(3) 兩個多數集必然存在公共成員，故Q-j和Q-i必然存在一個公共的進程Pk，Pk即收到了PreProposal-i又收到了Proposal-j，且都接受了它們；Pk收到消息的先後關係只存在如下兩種可能：

1.Pk先收到了PreProposal-i

2.Pk先收到了Proposal-j

(4) 情形1中Pk先收到了PreProposal-i，那麼Pk收到Proposal-j時，Pk.a_proposal &>= PreProposal-i.proposal_id ＞Proposal-j.proposal_id，Pk會拒絕Proposal-j，與(3)矛盾，因此情況1不可能，Pk必然是先收到Proposal-j。

(5) 情形2中Pk收到PreProposal-i時，已經接受了Proposal-j，因此Pk回復PreProposal-i的提案中包含了Proposal-j，因此K-i中必然包含了Proposal-j。

(6) 由(1)已知MaxProposal(K-i) != Proposal-j，即存在另一個提案Proposal-m = MaxProposal(K-i),而Proposal-j屬於K-i,因此Proposal-m.proposal_id &> Proposal-j.proposal_id，且Proposal-m.v != Proposal-j.v。

(7)由預提案階段，接受者回復預提案的條件可知：Proposal-i.proposal_id大於集合K-i中任意一個提案的Proposal-id，故Proposal-i.proposal_id&>Proposal-m.proposal_id。

(8) 目前我們已經論證如下一點：

在Proposal-j最終會被通過的前提下，如果存在一個提案Proposal-i.v!=Proposal-j.v，且Proposal-i.proposal_id &>Proposal-j.proposal_id,我們一個數學符號來帶表示這個情況，記CF(j,i)；那麼必然存在一個提案Proposal-m, Proposal-m！=Proposal-j.v,且Proposal-m.proposal_id &> Proposal-j.proposal_id，同樣的我們可以記做CF(j,m)。並且Proposal-m.proposal_id &< Proposal-i.proposal_id，m &< i。

即如果CF(i,j)成立，那麼必然CF(m,j)成立，且i&>m，即 CF(i,j) —&> CF(m,j)。這個過程可以繼續往下遞歸，但由於區間[j,i]範圍是有限的，因此一定會遞歸到一個CF(j,e)，此時不可能存在一個提案，它的proposal_id在區間(j,e)內，無法往下遞歸，這與(8)矛盾。這也就意味著CF(e,j)不成立，而如果CF(i,j)成立，那麼CF(e,j)成立,因此CF(i,j)不成立，故假設不成立，即Proposal-i.v 必然等於Proposal-j.v，即證CP1。

通過歸約的方式得出矛盾的方式依舊有些抽象，我們可以通過更好的定義假設來更容易得到的矛盾：

我們加強對Proposal-i的約束;先假設存在一個提案的非空集合KD，KD中的任意一個提案Proposal-k,Proposal-k.v!=Proposal-j.v，且Proposal-k.proposal_id &> Proposal-j.v;再假設Proposal-i是KD中proposal_id最小的提案；由於KD是非空集合，故Proposal-i必然存在。

我們依舊可以從Proposal-i出發，(1)~(7)與上面相同，同理得到：存在一個提案Proposal-m, Proposal-m！=Proposal-v,且Proposal-m.proposal_id &> Proposal-j.proposal_id，且Proposal-m.proposal_id &< Proposal-i.proposal_id。顯然Proposal-m滿足集合KD對提案的要求，故Proposal-m屬於KD，又Proposal-m.proposal_id&Proposal-j.proposal_id，即如果一個提案Proposal-j最終會被通過，對於任意的一個提案Proposal-i,如果Proposal-i.proposal_id &> Proposal-j.proposal_id，那麼必定Proposal-i.v = Proposal-j.v，即CP1。

CP1約束了proposal_id大於Proposal-j的提案的值，保證了如果一個提案Proposal-j最終會被通過，不會存在另一個proposal-id更大且值不同的提案被通過，因為這些提案的值都和Proposal-j相同。那麼對於proposal_id更小的提案呢？我們假設存在一個提案Proposal-o,Proposal-o.proposal_id &< Proposal-j.proposal_id，且Proposal-o.v!=Proposal-j.v,Proposal-o最終會被通過，將CP1應用於Proposal-o,則可知Proposal-j不存在，這矛盾，故Proposal-o不存在。故由CP1我們可知：如果一個提案Proposal-j最終會被通過，那麼不存在另一個提案，它最終會被通過，且它的值與Proposal-j不同。由此協議必然是安全的。

雖然我們得到了一個安全的一致性協議，基本上它就是Paxos，但是真正的Paxos要比我們假裝推導出的協議更簡單一點。

回過頭來看下我們的階段1中接受者Acceptor的行為，它要回復所有的它接受過的提案，從實踐的角度，不論是在本地保存所有它接受過的提案還是通過網路將它們傳輸給提議者，開銷都太大且不可控。再看下階段二中，提議者的選值策略，它只是選擇了收到的多數集接受者回復的提案中proposal_id最大的那一個，因此接受者實際上只需要回復它接受過的proposal_id最大的提案即可，因為其它提案根本不可能會被選值策略選中。因此最終的協議如下，它就是Paxos:

階段一預提案階段： 提議者Proposer：向接受者Acceptor廣播預提案，附帶接下來提案Proposal的proposal_id 接受者Acceptor：收到預提案後更新a_proposal_id = max(proposal_id,a_proposal_id)，如果預提案的proposal_id&>a_proposal_id，Acceptor回復記錄的接受過的proposal_id最大的提案。

階段二提案階段：提議者Proposer：等待直到收到大多數接受者對預提案的回復，從所有回復的提案組成的法定數目的提案集合K中挑選proposal_id最大的提案，以該提案的值作為本次提案的值。如果K是空集，那麼可以給提案任意賦值。然後把該提案廣播給接受者們，提案和預提案共享同一個proposal_id。 接受者Acceptor：如果收到的提案的proposal_id&>= a.proposal_id，那麼接受這個提案，更新a_proposal_id = max(proposal_id,a_proposal_id)，更新記錄的提案。

補充部分：

上面的過程從具體的場景開始推導Paxos，雖然直觀但是繁瑣，如果從抽象的概念和分析入手，那麼過程將會相當簡潔和漂亮，這也是Lamport的原始論文中的方式。這種方式理解起來更困難的地方在於：

1.沒有任何具體的認知下，直接抽象的討論容易讓人摸不著頭腦。

2.大神總是在一些地方覺得顯然而不加以展開論述，而普通讀者如我的內心OS:顯然你mei!

但是原文引出Paxos演算法的過程實在是簡潔、漂亮；而經過上面的輪述，相信有了直觀的印象後，再來看抽象的方式也不那麼困難，所以補充下。

回顧下定理CP1：

如果一個提案Proposal-j最終會被通過，那麼對於任意的一個提案Proposal-i,如果Proposal-i.proposal_id &> Proposal-j.proposal_id，那麼必定Proposal-i.v = Proposal-j.v。

上面我們已經論證了只要協議能夠保證CP1就能夠保證一致性。但是CP1依舊過於寬泛，從CP1引出具體的協議流程依然是一頭霧水，那麼我們是否可以得到一個更加具體的定理CP2，保證CP2即可保證CP1，同時從CP2出發更容易引出協議的具體流程。為了描述方便，我們令Proposal-i的proposal_id為i，即Proposal-i代表了proposal_id=i的提案。

要導出CP2不妨先考慮下如何證明CP1，利用歸納法，只要如能證明如下性質成立，即可證明CP1：
如果proposal_id在區間[j,i）內任意的提案，提案的值均為Proposal-j.v，那麼必定Proposal-i.v=v;這個定理記做CP1_2。

現在我們用高中時簡單而效果神奇的歸納法，利用CP1_2證明下CP1:

假設propsal_id小於i的提案中最大的提案是Proposal-(i-1)。

1.如果對於[j,i-1)內的任意提案，值均為Proposal-j.v，那麼由CP1_2可知Proposal-i.v = Proposal-j.v。

2.由1可知如果對於[j,i-1)內的任意提案，值均為Proposal-j.v，[j,i)內的任意提案，值均為Proposal-j.v

3.假設Proposal-(j+1)是proposal-id大於j的最小提案，由CP1_2可知Proposal-(j+1).v = Proposal-j.v

4.由3,2歸納可知[j, $infty$ )內任意提案Proposal-i，Proposal-i.v = Proposal-j.v，即CP1

來看下CP1_2，相比CP1，它結論不變，但是多了一個前置條件：proposal_id在區間[j,i）內任意的提案值均為Proposal-j.v；這是一個重大的進步。CP1_2相比CP1看起來容易保證很多，但是它們卻是等價的。考慮CP1_2的三個前置條件：

1.i &> j
2.提案Proposal-j最終會被通過。因此由提案被通過的定義可知必然存在一個法定集合Q-j，Q-j中任意一個接受者最終都接受了Proposal-j
3.proposal_id在區間[j,i)內的提案的值均為Proposal-j.v

對於任意的一個法定集合Q，考慮Q最終（包括過去和未來的所有時空）會接受的所有proposal_id小於i的提案組成的集合K。根據法定集合性質，Q和Q-j必然存在一個公共的節點，即Q中必然存在一個節點，該節點最終會接受Proposal-j，因此集合K包含Proposal-j。

由K包含Proposal-j可知K中最大的提案proposal_id &>= j；由CP1_2的前置條件3和K的定義可知如果K中存在proposal-id大於j的提案，那麼該提案的值等於Proposal-j.v，因此K中proposal_id最大的提案的值等於Proposal-j.v。

綜上所述由CP1_2的前置條件可知：對於任意的一個法定集合Q，Q最終會接受的proposal_id小於i的提案組成的集合K，K中proposal_id最大的提案的值必定為Proposal-j.v。如果我們能證明該條件下，Proposal-i.v = Proposal-j.v，即可證明CP1_2。將CP1_2的前置條件替換為該條件，我們可以得到一個如下的性質CP2，保證CP2即可保證CP1_2：
對於任意的一個法定集合Q，Q最終會接受的所有proposal_id小於i的提案組成的集合K，如果K中proposal_id最大的提案的值為Proposal-j.v;那麼Proposal-i.v = Proposal-j.v。

而引出滿足CP2的流程就比較容易了，由於集合K中proposal_id最大的提案的值等於Proposal-j.v，看起來只要令Proposal-i的值為K中proposal-id最大提案的值就可以保證CP2。由於Q是任意一個法定集合，因此獲取K似乎在實現上也不難，提出Proposal-i的提議者只要向Q中所有接受者詢問即可。

然後： CP2 —&> CP1_2—&> CP1 —&>一致性

但是實際上獲取K沒有那麼簡單，K包含的是Q所有最終接受的proposal-id小於i的的提案，不僅包含已經接受過的提案，還包括未來會接受的提案。獲取已經接受過的提案是容易的，Q中的接受者只需記錄它所有接受過的提案，當收到提出Proposal-i的提議者詢問時，回復當中proposal_id小於i的提案即可;但是如何知曉未來？我們可以換個思路，既然無法知曉未來，那麼我們約束未來，收到詢問後，令Q中的接受者都承諾不再接受任何proposal_id小於i的提案，即接受者未來將不接受任何proposal_id小於i的提案;既然未來已不存在，那麼Proposal-i的提議者根據Q的回復獲能得到完整的K。

於是協議的流程如下：

對於提議者，在正式提案前，先向任意的法定集合Q發送一個消息，這個消息即是預提案，消息中要附帶提案的proposal-id，作為接受者承諾和回復的依據。

接受者收到預提案後，承諾：不再接受比預提案中附帶的proposal-id更小的提案；並回復:已經接受的proposal-id比於提案的proposal-id更小的提案，如之前所論述的，回復的所有滿足條件的提案可以優化為只回復一個比預提案proposal_id更小的提案中proposal_id最大的那個提案。

提議者收到所有Q中接受者回復的提案後，挑選其中proposal_id最大的提案的值作為本次提案的值。

這樣我們就得到了Paxos中最為關鍵的幾步，閱讀了之前冗長的假裝推導，相信讀者很容易就能補全它得到完整的Paxos。

相比於之前近萬字的假裝推導，這個推導過程才1500字左右，但是即說清了Paxos是如何得出的，又論證Paxos為何正確，簡潔卻更有力。所以最後還是建議真有興趣的話去看下原文，在我看來它無疑是計算機領域那數不盡的論文中最值得閱讀的那一類。末尾我所描述的版本思路來自&<&&>，基本一致但也並不完全相同；而&<&< The Part-Time Parliament&>&>則別有一番風味。

最後需要注意的是Paxos並不完全滿足開頭解決一致性問題需要滿足的三個條件中的3。理論上，Paxos存在永遠無法達成一致的可能，哪怕是在所有進程都存活的情況下。想像一下這樣的場景，一個提案Proposal-j被提出時，恰好一個proposal-id更大的預提案Proposal-i被提出，導致Proposal-j無法被通過，而Proposal-i同樣的又因為一個proposal_id更大的其它預提案被提出，導致無法被通過。這種情況理論上存在無限遞歸的可能，這個問題也稱為活鎖;FLP早就證明了就算是容忍一個進程的失敗，非同步環境下任何一致性演算法都存在永不終止的可能。但是實際的工程中，很多手段可以來減小兩個提案的衝突概率，使得v被決定的均攤開銷是一個提案，多個提案還無法決定v值的情形是極小概率事件，且概率隨著提案個數增加越來越小。另外的一點，通常認為Paxos可以容忍少數進程掛掉，但這只是為了保證它的活性，對於安全性，實際上Paxos永遠滿足1,2，哪怕進程都掛掉了，此時只是顯然一致無法達成而已。

看了幾篇前面的答案，感覺都是為了邏輯的驗密性，進行了大篇幅的推理，這樣確實非常嚴謹，但是理解起來就要廢一番功夫了。我就不用一步一步的推理來描述了，這樣雖然喪失一些嚴密性，但是會盡量提高可讀性，爭取讓每個人都能理解這個演算法的要點。

Paxos演算法背景介紹：
Paxos演算法是分散式技術大師Lamport提出的，主要目的是通過這個演算法，讓參與分散式處理的每個參與者逐步達成一致意見。用好理解的方式來說，就是在一個選舉過程中，讓不同的選民最終做出一致的決定。
Lamport為了講述這個演算法，假想了一個叫做Paxos的希臘城邦進行選舉的情景，這個演算法也是因此而得名。在他的假想中，這個城邦要採用民主提議和投票的方式選出一個最終的決議，但由於城邦的居民沒有人願意把全部時間和精力放在這種事情上，所以他們只能不定時的來參加提議，不定時來了解提議、投票進展，不定時的表達自己的投票意見。Paxos演算法的目標就是讓他們按照少數服從多數的方式，最終達成一致意見。

Paxos演算法的具體情況：

1、在整個提議和投票過程中，主要的角色就是「提議者」（向「接受者」提出提議）和「接受者」（收到「提議者」的提議後，向「提議者」表達自己的意見）。

2、整個演算法的大致過程為：
第一階段：因為存在多個「提議者」，如果都提意見，那麼「接受者」接受誰的不接受誰的？太混亂了。所以，要先明確哪個「提議者」是意見領袖有權提出提議，未來，「接受者」們就主要處理這個「提議者」的提議了（這樣，也可以在提出提議時就盡量讓意見統一，謀求儘早形成多數派）。
第二階段：由上階段選出的意見領袖提出提議，「接受者」反饋意見。如果多數「接受者」接受了一個提議，那麼提議就通過了。

3、必須要了解的其他相關背景：
1）怎麼明確意見領袖呢？通過編號。每個「提議者」在第一階段先報個號，誰的號大，誰就是意見領袖。如果不好理解，可以想像為賄選。每個提議者先拿著鈔票賄賂一圈「接受者」，誰給的錢多，第二階段「接受者」就聽誰的。（註：這裡和下文提到的「意見領袖」，並不是一個新的角色，而是代表在那一輪賄賂成功的「提議者」。所以，請把意見領袖理解為賄賂中勝出的「提議者」即可）
2）有個跟選舉常識不一樣的地方，就是每個「提議者」不會執著於讓自己的提議通過，而是每個「提議者」會執著於讓提議儘快達成一致意見。所以，為了這個目標，如果「提議者」在賄選的時候，發現「接受者」已經接受過前面意見領袖的提議了，即便「提議者」賄選成功，也會默默的把自己的提議改為前面意見領袖的提議。所以一旦賄賂成功，勝出的「提議者」再提出提議，提議內容也是前面意見領袖的提議（這樣，在謀求儘早形成多數派的路上，又前進了一步）。
3）錢的多少很重要，如果錢少了，無論在第一還是第二階段「接受者」都不會尿你，直接拒絕。
4）上面2）中講到，如果「提議者」在賄選時，發現前面已經有意見領袖的提議，那就將自己的提議默默改成前面意見領袖的提議。這裡有一種情況，如果你是「提議者」，在賄賂的時候，「接受者1」跟你說「他見過的意見領袖的提議是方案1」，而「接受者2」跟你說「他見過的意見領袖提議是方案2」，你該怎麼辦？這時的原則也很簡單，還是：錢的多少很重要！你判斷一下是「接受者1」見過的意見領袖有錢，還是「接受者2」見過的意見領袖有錢？如何判斷呢？因為「接受者」在被「提議者」賄賂的時候，自己會記下賄賂的金額。所以當你賄賂「接受者」時，一旦你給的賄賂多而勝出，「接受者」會告訴你兩件事情：a.前任意見領袖的提議內容（如果有的話），b.前任意見領袖當時賄賂了多少錢。這樣，再面對剛才的情景時，你只需要判斷一下「接受者1」和「接受者2」告訴你的信息中，哪個意見領袖當時給的錢多，那你就默默的把自己的提議，改成那個意見領袖的提議。
5）最後這一部分最有意思，但描述起來有點繞，如果不能一下子就理解可以先看後面的例子。在整個選舉過程中，每個人誰先來誰後到，「接受者」什麼時間能夠接到「提議者」的信息，是完全不可控的。所以很可能一個意見領袖已經產生了，但是由於這個意見領袖的第二階段剛剛開始，絕大部分「接受者」還沒有收到這個意見領袖的提議。結果，這時突然衝進來了一個新的土豪「提議者」，那麼這個土豪「提議者」也是有機會讓自己的提議勝出的！這時就形成了一種博弈：a.上一個意見領袖要趕在土豪「提議者」賄賂到「接受者」前，趕到「接受者」面前讓他接受自己的提議，否則會因為自己的之前賄賂的錢比土豪少而被拒絕。b.土豪「提議者」要趕在上一個意見領袖將提議傳達給「接受者」前，賄賂到「接受者」，否則土豪「提議者」即便賄賂成功，也要默默的將自己的提議改為前任意見領袖的提議。這整個博弈的過程，最終就看這兩個「提議者」誰的進展快了。但最終一定會有一個意見領袖，先得到多數「接受者」的認可，那他的提議就勝出了。

4、總結
好啦，故事到這裡基本講述完了，咱們來總結一下，其實Paxos演算法就下面這麼幾個原則：
1）Paxos演算法包括兩個階段：第一個階段主要是賄選，還沒有提出提議；第二個階段主要根據第一階段的結果，明確接受誰的提議，並明確提議的內容是什麼（這個提議可能是賄選勝出「提議者」自己的提議，也可能是前任意見領袖的提議，具體是哪個提議，見下面第3點原則）。
2）編號（賄賂金額）很重要，無論在哪個階段，編號（賄賂金額）小的，都會被鄙視（被拒絕）。
3）在第一階段中，一旦「接受者」已經接受了之前意見領袖的提議，那後面再來找這個「接受者」的「提議者」，即便在賄賂中勝出，也要被洗腦，默默將自己的提議改為前任意見領袖的提議，然後他會在第二階段提出該提議（也就是之前意見領袖的提議，以力爭讓大家的意見趨同）。如果「接受者」之前沒有接受過任何提議，那賄選勝出的「提議者」就可以提出自己的提議了。

5、舉例

最後舉個例子，加深一下印象：

有兩個「提議者」和三個「接受者」。

1）首先「提議者1」賄賂了3個「接受者」

2）3個「接受者」記錄下賄賂金額，因為目前只有一個「提議者」出價，因此$1就是最高的了，所以「接受者」們返回賄賂成功。此外，因為沒有任何先前的意見領袖提出的提議，因此「接受者」們告訴「提議者1」沒有之前接受過的提議（自然也就沒有上一個意見領袖的賄賂金額了）。

3）「提議者1」向「接受者1」提出了自己的提議：1號提議，並告知自己之前已賄賂$1。

4）「接受者1」檢查了一下，目前記錄的賄賂金額就是$1，於是接受了這一提議，並把1號提議記錄在案。

5）在「提議者1」向「接受者2」「接受者3」發起提議前，土豪「提議者2」出現，他開始用$2賄賂「接受者1」與「接受者2」。

6）「接受者1」與「接受者2」立刻被收買，將賄賂金額改為$2。但是，不同的是：「接受者1」告訴「提議者2」,之前我已經接受過1號提議了，同時1號提議的「提議者」賄賂過$1；而，「接受者2」告訴「提議者2」，之前沒有接受過其他意見領袖的提議，也沒有上一個意見領袖的賄賂金額。

7）這時，「提議者1」回過神來了，他向「接受者2」和「接受者3」發起1號提議，並帶著信息「我前期已經賄賂過$1」。

8）「接受者2」「接受者3」開始答覆：「接受者2」檢查了一下自己記錄的賄賂金額，然後表示，已經有人出價到$2了，而你之前只出到$1，不接受你的提議，再見。但「接受者3」檢查了一下自己記錄的賄賂金額，目前記錄的賄賂金額就是$1，於是接受了這一提議，並把1號提議記錄在案。

9）到這裡，「提議者1」已經得到兩個接受者的贊同，已經得到了多數「接受者」的贊同。於是「提議者1」確定1號提議最終通過。

10）下面，回到「提議者2」。剛才說到，「提議者2」賄賂了「接受者1」和「接受者2」，被「接受者1」告知：「之前已經接受過1號提議了，同時1號提議的『提議者』賄賂過$1」，並被「接受者2」告知：「之前沒有接到過其他意見領袖的提議，也沒有其他意見領袖的賄賂金額」。這時「提議者2」，拿到信息後，判斷一下，目前賄賂過最高金額（即$1）的提議就是1號提議了，所以「提議者2」默默的把自己的提議改為與1號提議一致，然後開始向「接受者1」「接受者2」發起提議（提議內容仍然是1號提議），並帶著信息：之前自己已賄賂過$2。

11）這時「接受者1」「接受者2」收到「提議者2」的提議後，照例先比對一下賄賂金額，比對發現「提議者2」之前已賄賂$2，並且自己記錄的賄賂金額也是$2，所以接受他的提議，也就是都接受1號提議。

12）於是，「提議者2」也拿到了多數派的意見，最終通過的也是1號提議。

這裡再多說一句：

回到上面的第5）步，如果「提議者2」第一次先去賄賂「接受者2」「接受者3」會發生什麼？那很可能1號提議就不會成為最終選出的提議。因為當「提議者2」先賄賂到了「接受者2」「接受者3」，那等「提議者1」帶著議題再去找這兩位的時候，就會因為之前賄賂的錢少（$1&<$2）而被拒絕。所以，這也就是剛才講到可能存在博弈的地方：a.「提議者1」要趕在「提議者2」賄賂到「接受者2」「接受者3」之前，讓「接受者2」「接受者3」接受自己的意見，否則「提議者1」會因為錢少而被拒絕；b.「提議者2」要趕在「提議者1」之前賄賂到「接受者」，否則「提議者2」即便賄賂成功，也要默默的將自己的提議改為「提議者1」的提議。但你往後推演會發現，無論如何，總會有一個「提議者」的提議獲得多數票而勝出。

以上，只是把大致的Paxos演算法的思路介紹了一下，因為情景實在太複雜，比如：「提議者」、「接受者」如果是4個、5個……，比如：「提議者」與「接受者」之間的交互誰先誰後，等等各類情況。但是，其實都是能夠嚴謹的推導出最後能夠選出一個多數派的，不過篇幅就會太長了。大家有興趣可以按照上面的思路，自己再模擬模擬「提議者」「接受者」數量或多或少，交互或先或後的各種情況，結果肯定是最終唯一一個提議會獲得多數票而勝出。

回想當時自己看Paxos演算法時，走過很多的彎路，花了很長時間，這篇文章也是結合自己看Paxos演算法時的一些心得所寫，希望對初學者能有些啟發。

（完）

——2016.5

寫了一篇比特幣與區塊鏈的文章，有興趣的可以來瞅瞅～

GRAYLAMB：比特幣 (Bitcoin) 系統是如何運行的？

——2017.8.4

如果說淺顯易懂的說明paxos演算法的運作過程，我相信網上已經有各式各樣的方法了。
但是我想說的是，理解這些過程是比較局限的。目前paxos有各種各樣的變種，亦或是一些優化，但是萬物不離其宗，都是源自於樸素paxos演算法而來，你理解這些過程並不能理解這些變種或優化是怎麼來的，你只能做的是學習一個又一個。

大家在學習很多經典演算法的時候往往會非常細緻的研究其推導過程和每一步的含義，而到了這個演算法卻想拋棄這些，而尋找其他捷徑，這有點奇怪。所以我覺得理解運作過程的同時要先去理解推導過程，這樣才會使得能對演算法進行舉一反三，不受限。

啃論文是最有效的方法，要掌握這門演算法肯定得付出一些精力的。能耐心去看Lamport的兩篇論文 "The Part-Time Parliament" 和「Paxos Made Simple」，得到的理解程度肯定要比單純閱讀簡化資料高得多。

是的啃論文是最有效的，但卻不是最高效的。理解運作過程也好，推導過程也好，大家的回答都是為了幫助大家更高效的掌握這門演算法。大家的回答已經很好，我這裡作為補充，也是算另一個角度，幫助大家去理解paxos的數學推導過程，寫了這麼一篇文章： Paxos理論介紹(1): 樸素Paxos演算法理論推導與證明 - 分散式一致性與高可用實踐 - 知乎專欄希望能幫到大家。

http://drmingdrmer.github.io/tech/distributed/2015/11/11/paxos-slide.html

這麼說吧，paxos是一個會者不難，難者不會的演算法，門檻高，但一旦明白又感覺很簡單！
總體說來，paxos就是通過兩個階段確定一個決議：
Phase1：確定誰的編號最高，只有編號最高者才有權利提交proposal；
Phase2：編號最高者提交proposal，如果沒有其他節點提出更高編號的proposal，則該提案會被順利通過；否則，整個過程就會重來。
你編號高，我比你更高，反覆如此，演算法永遠無法結束，這叫活鎖。FLP Impossibility已經證明，在非同步通信中不存在任何一致性演算法，活鎖便是Paxos無法解決的硬傷。
Phase1，Phase2非常像2PC中的兩個階段，因此paxos本質上是多個2PC交替執行！
另外，即使你明白了，在實現時會知道有多難，工程實現與理論差距很大！
具體請參考我的博客。

推薦知行學社的分散式系統與Paxos演算法視頻課程，循序漸進，講解地比較淺顯易懂。
視頻封面

paxos和分散式系統視頻

過去9個月帶團隊實現了paxos同步資料庫redolog，下面這個鏈接是基本思路的介紹，後續找時間再寫一個真正的工程實現介紹
http://mp.weixin.qq.com/s?__biz=MzA4MzYxMjEwMg==mid=203432378idx=1sn=34d280eb89d6bad352fdbbf856d86c99#rd

我個人最近把Mit 6.824的分散式系統Lab剛做完，回頭去看，得到兩點經驗：
1.和人討論是非常有幫助的，因為自己在理解問題的時候，尤其是新的內容過多的問題的時候，很容易形成偏見，這些偏見自己是很難自查的，與人討論能很好的克服這一問題。
2.Talk is cheap, show me the code. 像這種演算法，你自己寫一遍，然後用實際問題跑一遍，會非常大的增進你的理解。

Paxos演算法本身其實不複雜，我當初學的時候，問題主要有兩個，一個是不知道它要解決的問題是什麼，solving consensus其實是個很抽象的概念，另一個問題是，不理解這個演算法為什麼可以理論上保證這一點。其實，問題還是在於沒有理解問題本身，可能是自己對抽象問題的理解上能力還是有欠缺。
所以還是自己做一下這個lab吧，真的對你理解這個演算法很有幫助

淺顯易懂是不可能講明白paxos的，尤其是對於小白聽眾，如果真的想透徹的理解paxos，不僅要看《paxos made simple》的論文，還要看懂paxos的證明方法，這樣才能完全理解。

作者：Marchisio
鏈接：https://zhuanlan.zhihu.com/p/25394087
來源：知乎
著作權歸作者所有。商業轉載請聯繫作者獲得授權，非商業轉載請註明出處。

這篇回答假設讀者看過Paxos的論文，這裡不涉及任何數學證明，數學理論部分高票答案講的非常好，這裡只是把步驟說明，然後舉例對應這些步驟

Paxos的角色有coordinator，learner，acceptor，proposer

一般流程是由P發送請求給C，由C告知A開始決策，決策結束後，由A通知L決策結果，在實際實現中P和C常常合一。

Acceptor a的狀態如下:

1、Rnd[a] acceptor a參與過的最高投票輪次，初始為0（0意味著a沒參加過任何一次投票）

2、Vrnd[a] acceptor a 投過票的最高輪次初始值0 [vrnd[a]永遠小於rnd[a]]

3、Vval[a] a在Vrnd[a]中接受的value值

Coordinator的狀態：

Crnd[c] c發起的投票的最高輪次

Cval[c] 在Crnd[c]中，c propose的值（可以為空，表示crnd[c] no value picked）

1、流程

第i輪投票分兩個階段，其中c是coordinator.

1a.若crnd&

1b.若a收到請求中i&> rnd[a]，只rnd[a]為i，並向c發送消息包含Vrnd[a]、Vval[a]。否則忽略請求

2a.若crnd[c]=i(此時c沒有開啟更高輪次的投票)，cval[c]=none（c在本輪中沒有執行2a），並且c在本輪中收到了來自一個quorum 的集合Q的1b消息。則c在1b中反饋的v集合中選擇一個v，並發送請求要求acceptor接受這個v

2b.若a收到消息中i&>=rnd[a]（此處的等於意味著，這裡的a參與1b不是必須的）並且vrnd[a]不等於i。則a在本輪接受v。置vrnd[a]和rnd[a]為i，另置vval[a]為v。並廣播消息給learners annouing第i輪投票

若i&

Learner成功學習的條件是在該輪次中收到來自一個quorum Q的2b消息。

Coordinator 可以在任何時候為新一輪投票j（j大於之前的投票編號）開啟1a。

2、在2a中選值

2a中c需要確定一個v，選擇方法滿足如下選擇條件：

對任意的輪次i和j且j&

（1）第 j輪沒有投票任何值。

（2）第j輪已經確定投票給v

通俗的講就是假設某日上朝，年邁的皇帝（Coordinator）決定選太子，在朝官員，甲乙丙丁戊己庚。皇帝和頒布聖旨的太監（learner）不能直接通信（理論上coordinator可以和acceptor是同一伺服器，可以和learner直接通信，但在Paxos中，但若這個伺服器和learner通信時，一定是以acceptor的角色），需要通過大臣來傳達消息。而大臣們耳朵不好，時靈時不靈。而皇帝本身有立長立賢的想法（Proposer1），也有私心立最寵幸的X貴妃的兒子七皇子為太子的想法（Proposer2）

選擇條件對兩個條件分別對應兩種情況，如下所述

第一種情況就是：

皇帝（c）說：愛卿們，咱們來立太子吧，愛卿們可有推薦人選（第i輪1a）。

聽到消息的大臣甲乙丙丁…（acceptor構成大多數）：好的好的，我們自己沒意見，恭聽陛下聖裁（第i輪1b）

皇帝看到大多數朝臣都聽到了消息，開心地說：皇長子德行端正，宅心仁厚，依朕看，那就皇長子吧（第i輪2a，大臣么沒有意見，皇帝可以任意提議，）

聽到消息的大臣甲乙丙丁….：好的，吾皇萬歲，然後大臣告訴太監，皇長子為太子。若太監聽到大多數大臣都說皇長子，則皇長子正式冊封為太子。（第i輪2b）

第二種情況就是：

皇帝（c）說：愛卿們，咱們來立太子吧，愛卿們可有推薦人選（第i輪1a）。

大臣們…（acceptor）：好的好的，我們自己沒意見，恭聽聖上意見（第i輪1b）

皇帝看到大多數朝臣都同意立太子，開心地說：那就皇長子吧（第i輪2a，大臣么沒有意見，皇帝可以任意提議，）

這時大臣們收到消息，覺得皇長子沒問題，準備轉告太監，突然皇帝想起了自己的寵妃X貴妃，為了討美人歡心，皇帝決定改立X貴妃兒子七皇子。

於是皇帝說，等等，朕突然覺得皇長子過於懦弱，有婦人之仁，不足以承天下，要不咱還是重新決定吧，，愛卿們可有推薦人選（i+1輪1a）

大臣丁戊己庚聽到消息…（acceptor構成大多數）。戊己庚反饋，好的好的，我們自己沒意見，恭聽聖上意見（第i+1輪1b）

這時大臣丁不樂意了：啟奏陛下，君無戲言，況立儲茲事體大，廢長立幼會傷國本，還是皇長子吧（第i+1輪1b）

皇帝收到了大臣們的反饋，覺得大臣丁說的有道理，於是還是決定立皇長子為儲君，並廣播（第i+1輪2a）

大臣們甲乙丙丁戊己庚收到了消息後齊贊萬歲英明，轉達太監皇長子為儲君（第i+1輪2b）。。

paxos分散式一致性演算法--講述諸葛亮的反穿越

這裡有一篇用三國越劇描述的Paxos，我覺得挺不錯。

從個人經驗來說，找到一個合適的隱喻很重要，可以幫助跳過很多障礙，到目前為止想到最合適的隱喻就是計算機網路中的兩軍問題。這裡毛遂自薦一下，寫了一篇《以兩軍問題為背景來演繹BasicPaxos》，鏈接在 http://iunknown.iteye.com/blog/2246484

關於Paxos最好的文章還是Lamport的《The Part-Time Parliament》，這個論文比後來的《Paxos Made Simple》寫的更容易懂。基本上看一半就能讓你徹底明白是怎麼回事了，裡面其實也沒什麼高深的數學知識。
看完論文我的感覺是：第一步作者構建了一個單純的非並發的系統解釋如何達成一致性。然後闡明了其中的邏輯時序關係。然後給出了一個「任意並發和意外」情況下符合這個邏輯時序關係的演算法。

Raft

首先感謝各位答主們提供的乾貨，認真看總是會很有幫助的。
最近在研究這個paxos演算法，偶然見搜到了這樣一篇文章（英文）：
Neat Algorithms
帶有用 Javascript寫的動畫，看起來很直觀，便於理解。

直接上個具體實例，背景、兩階段啥的在後面。
首先，給出proposer和acceptor的消息圖：

針對上面提出的兩個階段，分別解釋：
prepare階段
1.
每個server向proposer發送消息，表示自己要當leader，假設proposer收到消息的時間不一樣，順序是： proposer2 -&> proposer1 -&> proposer3，消息編號依次為1、2、3。
緊接著，proposer將消息發給acceptor中超過半數的子成員(這裡選擇兩個)，如圖所示，proposer2向acceptor2和acceptor3發送編號為1的消息，proposer1向acceptor1和accepto2發送編號為2的消息，proposer3向acceptor2和acceptor3發送編號為3的消息。
2.
假設這時proposer1發送的消息先到達acceptor1和acceptor2，它們都沒有接收過請求，所以接收該請求並返回【2，null】給proposer1，同時承諾不再接受編號小於2的請求；
緊接著，proposer2的消息到達acceptor2和acceptor3，acceptor3沒有接受過請求，所以返回proposer2 【1，null】，並承諾不再接受編號小於1的消息。而acceptor2已經接受proposer1的請求並承諾不再接收編號小於2的請求，所以acceptor2拒絕proposer2的請求；
最後，proposer3的消息到達acceptor2和acceptor3，它們都接受過提議，但編號3的消息大於acceptor2已接受的2和acceptor3已接受的1，所以他們都接受該提議，並返回proposer3 【3，null】；
此時，proposer2沒有收到過半的回復，所以重新取得編號4，並發送給acceptor2和acceptor3，此時編號4大於它們已接受的提案編號3，所以接受該提案，並返回proposer2 【4，null】。
accept階段
1
Proposer3收到半數以上（兩個）的回復，並且返回的value為null，所以，proposer3提交了【3，server3】的提案。
Proposer1也收到過半回復，返回的value為null，所以proposer1提交了【2，server1】的提案。
Proposer2也收到過半回復，返回的value為null，所以proposer2提交了【4，server2】的提案。
2
Acceptor1和acceptor2接收到proposer1的提案【2，server1】，acceptor1通過該請求，acceptor2承諾不再接受編號小於4的提案，所以拒絕；
Acceptor2和acceptor3接收到proposer2的提案【4，server2】，都通過該提案；
Acceptor2和acceptor3接收到proposer3的提案【3，server3】，它們都承諾不再接受編號小於4的提案，所以都拒絕。
此時，過半的acceptor（acceptor2和acceptor3）都接受了提案【4，server2】，learner感知到提案的通過，learner開始學習提案，所以server2成為最終的leader。原文鏈接：通過實例來理解paxos演算法
背景
Paxos演算法是萊斯利·蘭伯特（Leslie Lamport，就是 LaTeX 中的"La"，此人現在在微軟研究院）於1990年提出的一種基於消息傳遞的一致性演算法。由於演算法難以理解起初並沒有引起人們的重視，使Lamport在八年後重新發表到TOCS上[2]。即便如此paxos演算法還是沒有得到重視，2001年Lamport用可讀性比較強的敘述性語言給出演算法描述[3]。可見Lamport對paxos演算法情有獨鍾。近幾年paxos演算法的普遍使用也證明它在分散式一致性演算法中的重要地位。06年google的三篇論文初現「雲」的端倪，其中的chubby鎖服務使用paxos作為chubby cell中的一致性演算法，paxos的人氣從此一路狂飆。
什麼是paxos演算法
Paxos 演算法是分散式一致性演算法用來解決一個分散式系統如何就某個值(決議)達成一致的問題。一個典型的場景是，在一個分散式資料庫系統中，如果各節點的初始狀態一致，每個節點都執行相同的操作序列，那麼他們最後能得到一個一致的狀態[^1]。為保證每個節點執行相同的命令序列，需要在每一條指令上執行一個"一致性演算法"以保證每個節點看到的指令一致。
paxos幹啥的
分散式系統中一般是通過多副本來保證可靠性，而多個副本之間會存在數據不一致的情況。所以必須有一個一致性演算法來保證數據的一致，描述如下：
假如在分散式系統中初始是各個節點的數據是一致的，每個節點都順序執行系列操作，然後每個節點最終的數據還是一致的。
Paxos演算法就是解決這種分散式場景中的一致性問題。對於一般的開發人員來說，只需要知道paxos是一個分散式選舉演算法即可。多個節點之間存在兩種通訊模型：共享內存（Shared memory）、消息傳遞（Messages passing），Paxos是基於消息傳遞的通訊模型的。
paxos演算法介紹
Paxos保證以下三點：
1. 只有被提出提案才能被選定；
2. 只有一個值被選定；
3. 如果某個進程認為某個提案被選定了，那麼這個提案必須是真的被選定的那個。
該一致性演算法中有三個角色，分別是：proposer，acceptor，learner。它們之間通過消息來通訊。
paxos演算法的兩階段
prepare 階段：
1. Proposer 選擇一個提案編號 n，然後向acceptor的某個超過半數的子成員發送編號為n的 prepare 請求；
2. Acceptor 收到 prepare 消息後，如果提案的編號n大於該acceptor已經回復的所有 prepare 請求的編號，則 Acceptor 將自己上次已經批准的最大編號提案回復給 Proposer，並承諾不再回復小於 n 的提案；

acceptor階段：
1. 當一個 Proposer 收到了半數以上的 Acceptors 對 prepare 的回復後，就進入批准階段。它要向回復 prepare 請求的 Acceptors 發送 accept 請求，包括編號 n 和根據 prepare階段決定的 value。這裡的value是所有響應中編號最大的提案的value（如果根據 prepare 沒有已經接受的 value，那麼它可以自由決定 value）。
2. 在不違背自己向其他 Proposer 的承諾的前提下，Acceptor 收到 accept 請求後即接受這個請求。即如果acceptor收到這個針對n提案的accep請求，只要改acceptor尚未對編號大於n的prepare請求做出過響應，它就可以通過這個提案。

要想徹底搞懂Paxos，必須了解Paxos演算法的推導過程。（拷貝到這裡圖片都沒了，懶得弄了）

詳見分散式系列文章——Paxos演算法原理與推導

Paxos演算法在分散式領域具有非常重要的地位。但是Paxos演算法有兩個比較明顯的缺點：1.難以理解 2.工程實現更難。

網上有很多講解Paxos演算法的文章，但是質量參差不齊。看了很多關於Paxos的資料後發現，學習Paxos最好的資料是論文《Paxos Made Simple》，其次是中、英文版維基百科對Paxos的介紹。本文試圖帶大家一步步揭開Paxos神秘的面紗。

Paxos是什麼

Paxos演算法是基於消息傳遞且具有高度容錯特性的一致性演算法，是目前公認的解決分散式一致性問題最有效的演算法之一。

Google Chubby的作者Mike Burrows說過這個世界上只有一種一致性演算法，那就是Paxos，其它的演算法都是殘次品。

雖然Mike Burrows說得有點誇張，但是至少說明了Paxos演算法的地位。然而，Paxos演算法也因為晦澀難懂而臭名昭著。本文的目的就是帶領大家深入淺出理解Paxos演算法，不僅理解它的執行流程，還要理解演算法的推導過程，作者是怎麼一步步想到最終的方案的。只有理解了推導過程，才能深刻掌握該演算法的精髓。而且理解推導過程對於我們的思維也是非常有幫助的，可能會給我們帶來一些解決問題的思路，對我們有所啟發。

問題產生的背景

在常見的分散式系統中，總會發生諸如機器宕機或網路異常（包括消息的延遲、丟失、重複、亂序，還有網路分區）等情況。Paxos演算法需要解決的問題就是如何在一個可能發生上述異常的分散式系統中，快速且正確地在集群內部對某個數據的值達成一致，並且保證不論發生以上任何異常，都不會破壞整個系統的一致性。

註：這裡某個數據的值並不只是狹義上的某個數，它可以是一條日誌，也可以是一條命令（command）。。。根據應用場景不同，某個數據的值有不同的含義。

問題描述

假設有一組可以提出（propose）value（value在提案Proposal里）的進程集合。一個一致性演算法需要保證提出的這麼多value中，只有一個value被選定（chosen）。如果沒有value被提出，就不應該有value被選定。如果一個value被選定，那麼所有進程都應該能學習（learn）到這個被選定的value。對於一致性演算法，安全性（safaty）要求如下：

只有被提出的value才能被選定。
只有一個value被選定，並且
如果某個進程認為某個value被選定了，那麼這個value必須是真的被選定的那個。

我們不去精確地定義其活性（liveness）要求。我們的目標是保證最終有一個提出的value被選定。當一個value被選定後，進程最終也能學習到這個value。

Paxos的目標：保證最終有一個value會被選定，當value被選定後，進程最終也能獲取到被選定的value。

假設不同角色之間可以通過發送消息來進行通信，那麼：

每個角色以任意的速度執行，可能因出錯而停止，也可能會重啟。一個value被選定後，所有的角色可能失敗然後重啟，除非那些失敗後重啟的角色能記錄某些信息，否則等他們重啟後無法確定被選定的值。
消息在傳遞過程中可能出現任意時長的延遲，可能會重複，也可能丟失。但是消息不會被損壞，即消息內容不會被篡改（拜占庭將軍問題）。

推導過程

最簡單的方案——只有一個Acceptor

假設只有一個Acceptor（可以有多個Proposer），只要Acceptor接受它收到的第一個提案，則該提案被選定，該提案里的value就是被選定的value。這樣就保證只有一個value會被選定。

但是，如果這個唯一的Acceptor宕機了，那麼整個系統就無法工作了！

因此，必須要有多個Acceptor！

多個Acceptor

多個Acceptor的情況如下圖。那麼，如何保證在多個Proposer和多個Acceptor的情況下選定一個value呢？

下面開始尋找解決方案。

如果我們希望即使只有一個Proposer提出了一個value，該value也最終被選定。

那麼，就得到下面的約束：

P1：一個Acceptor必須接受它收到的第一個提案。

但是，這又會引出另一個問題：如果每個Proposer分別提出不同的value，發給不同的Acceptor。根據P1，Acceptor分別接受自己收到的value，就導致不同的value被選定。出現了不一致。如下圖：

剛剛是因為『一個提案只要被一個Acceptor接受，則該提案的value就被選定了』才導致了出現上面不一致的問題。因此，我們需要加一個規定：

規定：一個提案被選定需要被半數以上的Acceptor接受

這個規定又暗示了：『一個Acceptor必須能夠接受不止一個提案！』不然可能導致最終沒有value被選定。比如上圖的情況。v1、v2、v3都沒有被選定，因為它們都只被一個Acceptor的接受。

最開始講的『提案=value』已經不能滿足需求了，於是重新設計提案，給每個提案加上一個提案編號，表示提案被提出的順序。令『提案=提案編號+value』。

雖然允許多個提案被選定，但必須保證所有被選定的提案都具有相同的value值。否則又會出現不一致。

於是有了下面的約束：

P2：如果某個value為v的提案被選定了，那麼每個編號更高的被選定提案的value必須也是v。

一個提案只有被Acceptor接受才可能被選定，因此我們可以把P2約束改寫成對Acceptor接受的提案的約束P2a。

P2a：如果某個value為v的提案被選定了，那麼每個編號更高的被Acceptor接受的提案的value必須也是v。

只要滿足了P2a，就能滿足P2。

但是，考慮如下的情況：假設總的有5個Acceptor。Proposer2提出[M1,V1]的提案，Acceptor2~5（半數以上）均接受了該提案，於是對於Acceptor2~5和Proposer2來講，它們都認為V1被選定。Acceptor1剛剛從宕機狀態恢復過來（之前Acceptor1沒有收到過任何提案），此時Proposer1向Acceptor1發送了[M2,V2]的提案（V2≠V1且M2&>M1），對於Acceptor1來講，這是它收到的第一個提案。根據P1（一個Acceptor必須接受它收到的第一個提案。）,Acceptor1必須接受該提案！同時Acceptor1認為V2被選定。這就出現了兩個問題：

Acceptor1認為V2被選定，Acceptor2~5和Proposer2認為V1被選定。出現了不一致。
V1被選定了，但是編號更高的被Acceptor1接受的提案[M2,V2]的value為V2，且V2≠V1。這就跟P2a（如果某個value為v的提案被選定了，那麼每個編號更高的被Acceptor接受的提案的value必須也是v）矛盾了。

所以我們要對P2a約束進行強化！

P2a是對Acceptor接受的提案約束，但其實提案是Proposer提出來的，所有我們可以對Proposer提出的提案進行約束。得到P2b：

P2b：如果某個value為v的提案被選定了，那麼之後任何Proposer提出的編號更高的提案的value必須也是v。

由P2b可以推出P2a進而推出P2。

那麼，如何確保在某個value為v的提案被選定後，Proposer提出的編號更高的提案的value都是v呢？

只要滿足P2c即可：

P2c：對於任意的N和V，如果提案[N, V]被提出，那麼存在一個半數以上的Acceptor組成的集合S，滿足以下兩個條件中的任意一個： - S中每個Acceptor都沒有接受過編號小於N的提案。 - S中Acceptor接受過的最大編號的提案的value為V。

Proposer生成提案

為了滿足P2b，這裡有個比較重要的思想：Proposer生成提案之前，應該先去『學習』已經被選定或者可能被選定的value，然後以該value作為自己提出的提案的value。如果沒有value被選定，Proposer才可以自己決定value的值。這樣才能達成一致。這個學習的階段是通過一個『Prepare請求』實現的。

於是我們得到了如下的提案生成演算法：

Proposer選擇一個新的提案編號N，然後向某個Acceptor集合（半數以上）發送請求，要求該集合中的每個Acceptor做出如下響應（response）。 (a) 向Proposer承諾保證不再接受任何編號小於N的提案。 (b) 如果Acceptor已經接受過提案，那麼就向Proposer響應已經接受過的編號小於N的最大編號的提案。

我們將該請求稱為編號為N的Prepare請求。

如果Proposer收到了半數以上的Acceptor的響應，那麼它就可以生成編號為N，Value為V的提案[N,V]。這裡的V是所有的響應中編號最大的提案的Value。如果所有的響應中都沒有提案，那么此時V就可以由Proposer自己選擇。生成提案後，Proposer將該提案發送給半數以上的Acceptor集合，並期望這些Acceptor能接受該提案。我們稱該請求為Accept請求。（注意：此時接受Accept請求的Acceptor集合不一定是之前響應Prepare請求的Acceptor集合）

Acceptor接受提案

Acceptor可以忽略任何請求（包括Prepare請求和Accept請求）而不用擔心破壞演算法的安全性。因此，我們這裡要討論的是什麼時候Acceptor可以響應一個請求。

我們對Acceptor接受提案給出如下約束：

P1a：一個Acceptor只要尚未響應過任何編號大於N的Prepare請求，那麼他就可以接受這個編號為N的提案。

如果Acceptor收到一個編號為N的Prepare請求，在此之前它已經響應過編號大於N的Prepare請求。根據P1a，該Acceptor不可能接受編號為N的提案。因此，該Acceptor可以忽略編號為N的Prepare請求。當然，也可以回復一個error，讓Proposer儘早知道自己的提案不會被接受。

因此，一個Acceptor只需記住：1. 已接受的編號最大的提案 2. 已響應的請求的最大編號。

Paxos演算法描述

經過上面的推導，我們總結下Paxos演算法的流程。

Paxos演算法分為兩個階段。具體如下：

階段一：

(a) Proposer選擇一個提案編號N，然後向半數以上的Acceptor發送編號為N的Prepare請求。

(b) 如果一個Acceptor收到一個編號為N的Prepare請求，且N大於該Acceptor已經響應過的所有Prepare請求的編號，那麼它就會將它已經接受過的編號最大的提案（如果有的話）作為響應反饋給Proposer，同時該Acceptor承諾不再接受任何編號小於N的提案。

階段二：

(a) 如果Proposer收到半數以上Acceptor對其發出的編號為N的Prepare請求的響應，那麼它就會發送一個針對[N,V]提案的Accept請求給半數以上的Acceptor。注意：V就是收到的響應中編號最大的提案的value，如果響應中不包含任何提案，那麼V就由Proposer自己決定。

(b) 如果Acceptor收到一個針對編號為N的提案的Accept請求，只要該Acceptor沒有對編號大於N的Prepare請求做出過響應，它就接受該提案。

Learner學習被選定的value

Learner學習（獲取）被選定的value有如下三種方案：

如何保證Paxos演算法的活性

通過選取主Proposer，就可以保證Paxos演算法的活性。至此，我們得到一個既能保證安全性，又能保證活性的分散式一致性演算法——Paxos演算法。

參考資料

論文《Paxos Made Simple》
論文《The Part-Time Parliament》
英文版維基百科的Paxos
中文版維基百科的Paxos
書籍《從Paxos到ZooKeeper》

這幾天把lamport的paxos論文「The Part-Time Parliament」，zab的論文「A simple totally ordered broadcast protocol」，raft的論文「In Search of an Understandable Consensus Algorithm
(Extended Version)」，還有Oki和Liskov的那篇「Viewstamped Replication (VR) 」，說實在的，lamport的原版論文不難理解，如果題主為了力求準確，最好將這幾篇論文對照看下。雖然大多數說法是lamport用了paxos的隱喻導致原版論文難以理解，但是每個人看問題的角度不一樣，而且，原版論文其實比多數翻譯要讀起來順暢多了，總體花費的時間更少才是。

如果題主想看原版論文，又擔心遇到什麼不可理解的問題耽誤時間，可以留郵箱，我這裡有直接在原版論文上做的筆記，有對單個問題點的解析，也有橫向演算法的比較，應該對你有實際的幫助。

如果選擇自己看，那有幾個坑需要注意：

1. paxos的論文剛開始隱喻了paxos，其實在single-decree parliament之前，根據對paxos的parliament策略敘述的時候，就已經交代了整個paxos的大格局。原文在提出三個約束條件的後面會有一段證明，不用害怕，這段證明也沒那麼難，看懂了，對於理解paxos演算法還是很有幫助的。如果single-decree parliament之前的理解不了，最好跟會的人討論下。

paxos是每個點（除了觀察者之類特殊點）都可以提議，也就是多點提議，同時進行；而且每個點同時提出的提議也可以是多個，比如點A提出了1，2兩個提議，那麼提議2可以在提議1之前被通過，然後提議1才通過，這個在paxos里是可以的，至於為何這樣都不會破壞不一致，還是去看原版論文。

2. zab的論文比paxos的偏實際一些，畢竟zab演算法本身就偏實際一些，選主以後，leader進行提議。看懂了paxos，看zab就是小菜一碟了。看zab的時候側重於實現，所以最好結合zookeeper的源碼看，zookeeper選主部分的代碼還是比較容易跟進去的，但是進行提議的時候（write操作）會有多個processor，這幾個processor是級聯的，這兒看代碼可能會有些暈（有點多級回調的意思），但是多看幾遍還是可以的。

需要注意的是，zab這種簡化的演算法，即使是leader，同時也只能有一個提議已經發出，而沒有得到確定，也就是in-flight的提議只有一個（對於paxos的單點也可以同時發出多個提議）。

3. 看懂zab以後，raft簡直就是不能再簡答了，只是把zab很多實現（沒有寫到zab論文的）用論文的方式表現出來了（畫了很多圖，結構等），幫助你理解。

之所以前面要看zab的源碼實現，就是因為raft跟zab很像。raft論文里基本是跟paxos在對比，與zab比較起來，也有一些細微的不同，但個人覺得，zab更優秀，看完這些論文就能體會出來，raft為了使得演算法容易理解，犧牲了一些zab里的優化。

4. Viewstamped Replication (VR) 這篇可以稍微看看，zab和raft里都提到了這個演算法。

個人郵箱：zheolong@126.com

博客地址（包含資料鏈接）：Consensus Algorithms，打開後搜「中文註解版」

Paxos並不是很容易理解，而且最初版本的Paxos也不能實現，相對而言一些變種演算法更加容易理解，而且在工程實現上也比較簡單。
例如
Raft：Raft Consensus Algorithm
Oeanbase的一致性協議：OceanBase高可用方案

Paxos 的論文描述的是一個抽象的協議，一開始看會有點懵。

以我的心得，可以先看一下 Raft。Raft 描述的是分散式一致性 log 協議，相對來說更針對具體場景，理解比較容易。

理解了 Raft 之後，再回頭理解 Paxos，你會發現 Raft 很大程度上是 Paxos 的一個具體場景的應用。

某種意義上來說，Raft 不能算一個新的協議，而是 Paxos 的一個具體化、簡單化。

另外，Raft 只是理解相對容易，實現的複雜度跟 Paxos 差不多。

我們雲巴最近在基於 Raft 實現一個分散式 key value 資料庫，有興趣可以多交流。