自從lamport在1998年發表paxos算法後，對paxos的各種改進工作就從未停止，其中動作最大的莫過于2005年發表的fast paxos。無論何種改進，其重點依然是在消息延遲與性能、吞吐量之間作出各種權衡。為了容易地從概念上區分二者，稱前者classic paxos，改進後的後者為fast paxos。
lamport在40多頁的論文中不僅提出了fast paxos算法，并且還從工程實踐的角度重新描述了paxos，使其更貼近應用場景。從一般的client/server來考慮，client其實承擔了proposer和learner的作用，而server則扮演acceptor的角色，是以下面重新描述了paxos算法中的幾個角色：
client/proposer/learner：負責提案并執行提案
coordinator：proposer協調者，可為多個，client通過coordinator進行提案
leader：在衆多的coordinator中指定一個作為leader
acceptor：負責對proposal進行投票表決
就是client的提案由coordinator進行，coordinator存在多個，但隻能通過其中被標明leader進行；提案由leader交由server進行表決，之後client作為learner學習決議的結果。
這種方式更多地考慮了client/server這種通用架構，更清楚地注意到了client既作為proposer又作為learner這一事實。
同樣要注意到的是，如果leader當機了，為了保證算法的正确性需要一個leader的選舉算法，但與之前一樣，lamport并不關心這個leader選舉算法，他認為可以簡單地通過随機或逾時機制實作。
另外在classic paxos中，從每次proposer提案到決議被學習，需要三個通信步驟：
proposer-----leader-----acceptor-----learner
從直覺上來說，proposer其實更“知道”送出那個value，如果能讓proposer直接送出value到acceptor，則可以把通信步驟減少到2個。fast paxos便是基于此而産生。
我們再回顧下classic paxos的幾個階段：
phase1a：leader送出proposal到acceptor
phase2b：acceptor回應已經參與投票的最大proposer編号和選擇的value
phase2a：leader收集acceptor的傳回值
phase2a.1：如果acceptor無傳回值，則自由決定一個
phase2a.2： 如果有傳回值，則選擇proposer編号最大的一個
phase2b：acceptor把表決結果發送到learner
很明顯，在phase2a.1中，如果leader可以自由決定一個value，則可以讓proposer送出這個value，自己則退出通信過程。隻要之後的過程運作正常，leader始終不參與通信，一直有proposer直接送出value到acceptor，進而把classic paxos的三階段通信減少為兩階段，這便是fast paxos的由來。是以，我們更加形式化下fast paxos的幾個階段：
phase1a：與之前相同
phase1b：與之前相同
phase2a.1：如果acceptor無傳回值，則發送一個any消息給acceptor，之後acceptor便等待proposer送出value
phase2a.2：如果有傳回值，則根據規則選取一個
phase2b：acceptor把表決結果發送到learner（包括leader）
算法主要變化在phase2a階段，即：
若leader可以自由決定一個value，則發送一條any消息，acceptor便等待proposer送出value
若acceptor有傳回值，則acceptor需選擇某個value
先不考慮實作，從形式上消息僅需在proposer-----acceptor-----learner之間傳遞即可，也即僅需2個通信步驟。下面我們詳細說明算法過程：
quorum
在classic paxos中一直通過多數派（majority）來保證算法的正确性，對多數派再進一步抽象化，稱為“quorum”，要求任意兩個quorum之間有交集（進而間接表達了majority的含義）
round
在classic paxos中，proposer每次提案都用一個全序的編号表示，如果執行順利，該編号的proposal在經曆phase1，phase2後最終會執行成功。
在fast paxos稱這個帶編号的proposal的執行過程為“round”
i-quorum
在classic paxos執行過程中，一般不會明确區分每次round執行的quorum，雖然也可以為每個round指定一個quorum。在fast paxos中會通過i-quorum明确指定round i需要的quorum
classic round
執行classic paxos的round稱為classic round
fast round
如果leader發送了any消息，則認為後續通信是一個fast round；若leader未發送any消息，還是跟之前一樣通信，則後續行為仍然是classic round。
根據lamport描述，classic round和fast round可通過round number進行加以區分。
在正常情況下，leader若可以自由決定一個value，應該發生一條phase2a消息，其中包含了選擇的value，但此時卻發送了一條無value的any消息。acceptor在接收到any消息後可做一些開始fast round的初始化工作，等待proposer送出真正的value。any消息的意思是acceptor可以做任意的處理。
是以，一個fast round包括兩個階段：由any消息開始的階段，和由proposer送出value的結束階段，而leader隻是起到一個初始化過程的作用，如果沒有錯誤發生，leader将退出之後的通信中過程。
下面是classic paxos互動圖：
下面是fast paxos的互動圖：
在classic paxos中，acceptor投票的value都是leader選擇好的，是以不存在同一round中投票多個value的場景，進而保證了一緻性。但在fast round中因為允許多個proposer同時送出不同的value到acceptor，這将導緻在fast round中沒有任何value被作為最終決議，這也稱為“沖突”（collision）
proposer送出的round是全序的，不同的proposer送出的round肯定不一樣，同一proposer不可能在同一round中送出不同的value，那為什麼還會有同一fast round中有多個value的情況？原因在于fast round與round差別，當fast round開始後，會被配置設定一個唯一的round number，之後無論多少個proposer送出value都是基于這個round number，而不管proposer送出的round是否全序。
比如，fast round number為10，proposer1送出了（11，1），proposer2送出了（12，2），但對fast round來說存在（10，1，2）兩個value。
因為沖突的存在，會導緻phase2a.2的選擇非常困難，原因是：
在classic paxos中，如果acceptor傳回多個value，隻要排序，選擇最高的編号對應的value即可，因為classic paxos中的value都是有leader選擇後在phase2a中發送的，是以最高編号的value肯定隻有一個。但在fast paxos中，最高編号的value會發現多個，比如（10，1，2）。
假如目前leader正在執行第i個classic round(i-quorum為q) ，得到acceptor回報的最高編号為k，有兩個value：v、w，說明fast round k存在兩個k-quorum，rv,rw。
是以如果保證下面兩個條件：
每個acceptor在同一fast round中僅投票一個value
q∩rv∩rw≠φ
則v、w不可能同時被選擇
根據上面描述，為了防止一次fast round選擇多個value，quorum需要滿足下面兩個條件：
任意兩個classic quorum有交集
任意一個classic quorum與任意兩個fast quorum有交集
不妨設總acceptor數為n，classic round運作的最大失敗acceptor數為f，fast round允許的失敗數為e，即n-f構成classic round的一個quorum，n-e構成fast round的一個quorum。
上面兩個條件等價于：
n>2f
n>2e+f
設qc,qf分别為classic和fast round的quorum大小，經過整理可得兩個下限結果：
|qc| = |qf| ≥ n − ⌈n/3⌉ + 1 ≥ ⌊2n/3⌋ + 1
|qc| ≥n-⌈n/2⌉+1 = ⌈n/2⌉+1
|qf|≥n-⌈n/4⌉≥⌈3n/4⌉
作為優化，acceptor在投票value時也應該發送到leader，這樣leader就很容易能發現沖突。leader如果在round i發現沖突，可以很容易地開始roun i+1，從phase1a開始重新執行classic paxos過程，但這個其實可以進一步優化，我們首先考慮下面這個事實：
如果leader重新開機了round i+1，并且收到了i-quorum個acceptor發送的phase1b消息，則該消息明确了兩件事情：
報告acceptor a參與投票的最大round和對應的value
承諾不會對小于i+1的round作出投票
假如acceptor a也參與了round i的投票，則a的phase1b消息同樣明确了上述兩件事情，并且會把對應的round，value在phase2b中發送給leader（當然還有learner），一旦acceptor a執行了phase2b，則也同時表明a将不會再對小于i+1的round進行投票。
也就是說，round i的phase2b與round i+1的phase1b有同樣的含義，也暗含着如果leader收到了round i的phase2b，則可直接開始round i+1的phase2a。經過整理，産生了兩種解決沖突(recovery)的方法：
如果leader在round i 中收到了(i+1)-quorum個acceptor的phase2b消息，并且發現沖突，則根據o4(v)選取一個value，直接執行round i+1的phase2a；否則，從phase1a開始重新執行round i+1
作為基于協調recovery的擴充，非協調要求acceptor把phase2b消息同時發送給其他quorum acceptor，由每個acceptor直接執行round i+1的phase2a，但這要求i-quorum與(i+1)-quorum必須相同，并且遵循相同選擇value的規則。
這種方式的好處是acceptor直接執行round i+1的phase2a，無需經過leader，節省了一個通信步驟，缺點是acceptor同時也作為proposer，搞的過于複雜。
至此，再完整地總結下fast paxos的progress：
phase2a.2：如果有傳回值
2.1 如果僅存在一個value，則作為結果送出
2.2 如果存在多個value，則根據o4(v)選取符合條件的一個
2.3 如果存在多個結果并且沒有符合o4(v)的value，則自由決定一個
fast paxos基本是本着樂觀鎖的思路：如果存在沖突，則進行補償。其中leader起到一個初始化progress和解決沖突的作用，如果progress一直執行良好，則leader将始終不參與一緻性過程。
是以fast paxos理論上隻需要2個通信步驟，而classic paxos需要3個，但fast paxos在解決沖突時有至少需要1個通信步驟，在高并發的場景下，沖突的機率會非常高，沖突解決的成本也會很大。
另外，fast paxos把client深度引入算法中，緻使其架構遠沒classic paxos那麼清晰，也沒classic paxos容易擴充。
總之，在我看來fast paxos是一個理論上可行，但實際中很難操作的算法，實際中用的比較多的還是classic paxos的各種簡化形式
fast paxos(lamport 2005)
multicoordinated paxos
on the coordinator’s rule for fast paxos
classic paxos vs. fast paxos
<a href="http://en.wikipedia.org/wiki/paxos_%28computer_science%29">http://en.wikipedia.org/wiki/paxos_(computer_science)</a>
http://blog.csdn.net/chen77716/article/details/7297122