一、概念
首先一個很重要的概念叫提案（Proposal）。最終要達成一緻的value就在提案裡。
提案 (Proposal)：Proposal資訊包括提案編号 (Proposal ID) 和提議的值 (Value)。
在Paxos算法中，有如下角色：
- Client：用戶端用戶端向分布式系統送出請求，并等待響應。例如，對分布式檔案伺服器中檔案的寫請求。
- Proposer：提案發起者提案者提倡客戶請求，試圖說服Acceptor對此達成一緻，并在發生沖突時充當協調者以推動協定向前發展
- Acceptor：決策者，可以準許提案Acceptor可以接受（accept）提案；如果某個提案被標明（chosen），那麼該提案裡的value就被標明了
- Learners：最終決策的學習者，學習者充當該協定的複制因素
二、問題描述
假設有一組可以提出提案的程序集合，那麼對于一個一緻性算法需要保證以下幾點：
- 在這些被提出的提案中，隻有一個會被標明
- 如果沒有提案被提出，就不應該有被標明的提案。
- 當一個提案被標明後，那麼所有程序都應該能學習（learn）到這個被標明的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被標明。出現了不一緻。如下圖：
剛剛是因為『一個提案隻要被一個Acceptor接受，則該提案的value就被標明了』才導緻了出現上面不一緻的問題。是以，我們需要加一個規定：
規定：一個提案被標明需要被半數以上的Acceptor接受
這個規定又暗示了：『一個Acceptor必須能夠接受不止一個提案！』不然可能導緻最終沒有value被標明。比如上圖的情況。v1、v2、v3都沒有被標明，因為它們都隻被一個Acceptor的接受。是以在這種情況下，我們使用一個全局的編号來辨別每一個Acceptor準許的提案，當一個具有某value值的提案被半數以上的Acceptor準許後，我們就認為該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：對于任意的Mn和Vn,如果提案[Mn,Vn]被提出，那麼肯定存在一個由半數以上的Acceptor組成的集合S，滿足以下兩個條件中的任意一個： * 要麼S中每個Acceptor都沒有接受過編号小于Mn的提案。 * 要麼S中所有Acceptor準許的所有編号小于Mn的提案中，編号最大的那個提案的value值為Vn
從上面的内容，可以看出，從P1到P2c的過程其實是對一系列條件的逐漸增強，如果需要證明這些條件可以保證一緻性，那麼就可以進行反向推導：P2c =>P2b=>P2a=>P2,然後通過P2和P1來保證一緻性。