1、Paxos算法
算法中的參與者主要分為三個角色，同時每個參與者又可兼領多個角色:
- proposer 提出提案，提案資訊包括提案編号和提議的value;
- acceptor 收到提案後可以接受(accept)提案;
- learner 隻能"學習"被準許的提案;
一緻性算法需要保證:
- 決議(value)隻有在被proposers提出後才能被準許(未經準許的決議稱為"提案(proposal)");
- 在一次Paxos算法的執行執行個體中，隻準許(chosen)一個value;
- learners隻能獲得被準許(chosen)的value;
2、Proposer生成提案
對于一個Proposer來說，擷取那些已經被通過的提案遠比預測未來可能會被通過的提案來的簡單。是以，Proposer在産生一個編号為Mn的提案時，必須要知道目前某一個将要或已經被半數以上Acceptor準許的編号小于Mn但為最大編号的提案。并且，Proposer會要求所有的Acceptor都不要再準許任何編号小于Mn的提案了–這就引出了如下的提案生成算法。
Proposer選擇一個新的提案編号Mn，然後向某個Acceptor集合的成員發送請求，要求該集合的Acceptor做出如下回應：
- 向Proposer承諾，保證不再準許任何編号小于Mn的提案。
- 如果Acceptor已經準許過任何提案，那麼其就向Proposer回報目前該Acceptor已經準許過的編号小于Mn但為最大編号的那個提案的值。
我們将該請求成為編号為Mn的提案的Prepare請求。
如果Proposer收到了來自半數以上的Acceptor的響應結果，那麼它就可以産生編号為Mn、Value值為Vn的提案，這裡的Vn是所有相應中編号最大的提案的Value值。 當然還存在另一種情況，就是半數以上的Acceptor都沒有準許過任何提案，即相應中不包含任何的提案，那麼此時Vn值就可以由Proposer任意選擇。
在确定提案之後，Proposer就會将該提案再次發送給某個Acceptor集合，并期望獲得它們的準許，我們稱此請求為Accept請求。需要注意的一點是，此時接收Accept請求的Acceptor集合不一定是之前響應Prepare請求的Acceptor集合。
3、Acceptor準許提案
在上文中，我們已經講解了Paxos算法中Proposer的處理邏輯，下面我們來看看Acceptor是如何準許提案的。
根據上面的内容，一個Acceptor可能會收到來自Proposer的兩種請求，分别是Prepare請求和Accept請求，對這兩類請求做出響應的條件分别如下：
- Prepare請求：Acceptor可以在任何時候響應一個Prepare請求。
- Accept請求：在不違背Accept現有承諾的前提下，可以任意相應Accept請求。
是以，對Acceptor邏輯處理的限制條件，大體可以定義如下：
一個Acceptor隻要尚未響應過任何編号大于Mn的Prepare請求，那麼它一定就可以接收這個編号為Mn的提案。
同時，值得一提的是，Paxos算法允許Acceptor忽略任何請求而不用擔心破壞其算法的安全性。
4、算法優化
假設一個acceptor接收到一個編号為n的prepare請求，但是它已經回應了一個編号大于n的prepare請求。于是acceptor就沒有必要回應這個prepare請求了，因為它不會準許這個編号為n的議案。它還可以忽略已經準許過的議案的prepare請求。
有了這些優化，acceptor隻需要儲存它已經準許的最高編号的議案（包括編号和決議），以及它已經回應的所有prepare請求的最高編号。因為任何情況下，都需要保證P2C，acceptor必須記住這些資訊，包括失效并重新開機之後。注意，proposer可以随意的抛棄一個議案——隻要它永遠不會使用相同的編号來提出另一個議案。
P2C：
對于任意的Mn和Vn，如果提案[Mn, Vn]被提出，那麼肯定存在一個由半數以上的Acceptor組成的集合S，滿足以下兩個條件中的任意一個。
1、S中不存在任何準許過編号小于Mn的提案的Acceptor。
2、選取S中所有Acceptor準許的編号小于Mn的提案，其中編号最大的那個提案其Value值是Vn。
5、算法陳述
階段一：
- p選擇一個提案編号m,然後向a的某個超半數自己成員發送編号為m的prepare請求。
- 如果一個a收到一個編号為m的prepare請求，且編号m大于該a已經響應的所有prepare編号，那麼他就會将他已經準許過的最大編号的提案(包含id和value)最為響應回報給p，同時a承諾不會再準許任何編号小于m的提案。
階段二：
-
如果p收到了來自半數以上a對于其發出的編号為m的prepare請求的響應，那麼他就會發送一個針對[m,v]的提案的accept請求給a.
注意，v的值就是收到的響應中編号最大的提案的值（有可能和自己送出的值不一緻，是階段一中a回報給p的accept請求中的v值），如果響應中不包含任何提案，那麼他可以是任意值。
- 如果a收到了這個[m,n]的請求，隻要改a尚未對編号大于m的prepare請求作出響應，他就可以通過這個提案。
6、提案擷取
下圖來自：Paxos算法原理與推導
7、通過選取主Proposer保證算法活性
下圖來自：Paxos算法原理與推導
8、Paxos圖解
一個分布式算法，有兩個最重要的屬性：Safety 和Liveness，簡單來說：
Safety是指那些需要保證永遠都不會發生的事情。
Liveness是指那些最終一定會發生的事情。