Paxos算法是Leslie Lamport（英語：Leslie Lamport，LaTeX中的“La”）于1990年提出的一種基于消息傳遞且具有高度容錯特性的一致性算法。
問題和假設
分布式系統中的節點通信存在兩種模型：共享內存（Shared memory）和消息傳遞（Messages passing）。基于消息傳遞通信模型的分布式系統，不可避免地會發生以下錯誤：進程可能會慢、被殺死或者重啟，消息可能會延遲、丟失、重復，在基礎 Paxos 場景中，先不考慮可能出現消息篡改及拜占庭錯誤的情況。Paxos 算法解決的問題是在一個可能發生上述異常的分布式系統中如何就某個值達成一致，保證不論發生以上任何異常，都不會破壞決議的一致性。一個典型的場景是，在一個分布式數據庫系統中，如果各節點的初始狀態一致，每個節點都執行相同的操作序列，那么他們最后能得到一個一致的狀態。為保證每個節點執行相同的命令序列，需要在每一條指令上執行一個“一致性算法”以保證每個節點看到的指令一致。一個通用的一致性算法可以應用在許多場景中，是分布式計算中的重要問題。因此從20世紀80年代起對于一致性算法的研究就沒有停止過。
為描述 Paxos 算法，Lamport 虛擬了一個叫做 Paxos 的希臘城邦，這個島按照議會民主制的政治模式制訂法律，但是沒有人愿意將自己的全部時間和精力放在這種事情上。所以無論是議員，議長或者傳遞紙條的服務員都不能承諾別人需要時一定會出現，也無法承諾批準決議或者傳遞消息的時間。但是這里假設沒有拜占庭將軍問題（Byzantine failure，即雖然有可能一個消息被傳遞了兩次，但是絕對不會出現錯誤的消息）；只要等待足夠的時間，消息就會被傳到。另外，Paxos 島上的議員是不會反對其他議員提出的決議的。
對應于分布式系統，議員對應于各個節點，制定的法律對應于系統的狀態。各個節點需要進入一個一致的狀態，例如在獨立Cache的對稱多處理器系統中，各個處理器讀取內存的某個字節時，必須讀到同樣的一個值，否則系統就違背了一致性的要求。一致性要求對應于法律條文只能有一個版本。議員和服務員的不確定性對應于節點和消息傳遞通道的不可靠性。
提出與證明
首先將議員的角色分為 proposers，acceptors，和 learners（允許身兼數職）。proposers 提出提案，提案信息包括提案編號和提議的 value；acceptor 收到提案后可以接受（accept）提案，若提案獲得多數 acceptors 的接受，則稱該提案被批準（chosen）；learners 只能“學習”被批準的提案。劃分角色后，就可以更精確的定義問題：
在一次 Paxos 算法的執行實例中，只批準（chosen）一個 value；
learners 只能獲得被批準（chosen）的 value。
1.
決議（value）只有在被 proposers 提出后才能被批準（未經批準的決議稱為“提案（proposal）”）；
2.
在一次 Paxos 算法的執行實例中，只批準（chosen）一個 value；
3.
learners 只能獲得被批準（chosen）的 value。
另外還需要保證 progress。這一點以后再討論。
作者通過不斷加強上述3個約束（主要是第二個）獲得了 Paxos 算法。
批準 value 的過程中，首先 proposers 將 value 發送給 acceptors，之后 acceptors 對 value 進行接受（accept）。為了滿足只批一個人個 value 的約束，要求經“多數派（majority）”接受的 value 成為正式的決議（稱為“批準”決議）。這是因為無論是按照人數還是按照權重劃分，兩組“多數派”至少有一個公共的 acceptor，如果每個 acceptor 只能接受一個 value，約束2就能保證。
于是產生了一個顯而易見的新約束：
P1：一個 acceptor 必須接受（accept）第一次收到的提案。
注意 P1 是不完備的。如果恰好一半 acceptor 接受的提案具有 value A，另一半接受的提案具有 value B，那么就無法形成多數派，無法批準任何一個 value。
約束2并不要求只批準一個提案，暗示可能存在多個提案。只要提案的 value 是一樣的，批準多個提案不違背約束2。于是可以產生約束 P2：
P2：一旦一個具有 value v 的提案被批準（chosen），那么之后批準（chosen）的提案必須具有 value v。
注：通過某種方法可以為每個提案分配一個編號，在提案之間建立一個全序關系，所謂“之后”都是指所有編號更大的提案。
如果 P1 和 P2 都能夠保證，那么約束2就能夠保證。
批準一個 value 意味著多個 acceptor 接受（accept）了該 value。因此，可以對 P2 進行加強：
P2a：一旦一個具有 value v 的提案被批準（chosen），那么之后任何 acceptor 再次接受（accept）的提案必須具有 value v。
由于通信是異步的，P2a 和 P1 會發生沖突。如果一個 value 被批準后，一個 proposer 和一個 acceptor 從休眠中蘇醒，前者提出一個具有新的 value 的提案。根據 P1，后者應當接受，根據 P2a，則不應當接受種這種場景下 P2a 和 P1 有矛盾。于是需要換個思路，轉而對 proposer 的行為進行約束：
P2b：一旦一個具有 value v 的提案被批準（chosen），那么以后任何 proposer 提出的提案必須具有 value v。
由于 acceptor 能接受的提案都必須由 proposer 提出，所以 P2b 蘊涵了 P2a，是一個更強的約束。
但是根據 P2b 難以提出實現手段。因此需要進一步加強 P2b。
假設一個編號為 m 的 value v 已經獲得批準（chosen），來看看在什么情況下對任何編號為的提案都含有 value v。因為 m 已經獲得批準（chosen），顯然存在一個 acceptors 的多數派 C，他們都接受（accept）了v?？紤]到任何多數派都和 C 具有至少一個公共成員，可以找到一個蘊涵 P2b 的約束 P2c：
P2c：如果一個編號為 n 的提案具有 value v，那么存在一個多數派，要么他們中所有人都沒有接受（accept）編號小于 n 的任何提案，要么他們已經接受（accept）的所有編號小于 n 的提案中編號最大的那個提案具有 value v。
可以用數學歸納法證明 P2c 蘊涵 P2b：
假設具有value v的提案m獲得批準，當時，采用反證法，假如提案n不具有value v，而是具有value w，根據P2c，則存在一個多數派S1，要么他們中沒有人接受過編號小于n的任何提案，要么他們已經接受的所有編號小于n的提案中編號最大的那個提案是value w。由于S1和通過提案m時的多數派C之間至少有一個公共的acceptor，所以以上兩個條件都不成立，導出矛盾從而推翻假設，證明了提案n必須具有value v；
若所有提案都具有value v，采用反證法，假如新提案N不具有value v，而是具有value w',根據P2c，則存在一個多數派S2，要么他們沒有接受過中的任何提案，要么他們已經接受的所有編號小于N的提案中編號最大的那個提案是value w'。由于S2和通過m的多數派C之間至少有一個公共的acceptor，所以至少有一個acceptor曾經接受了m，從而也可以推出S2中已接受的所有編號小于n的提案中編號最大的那個提案的編號范圍在之間，而根據初始假設，之間的所有提案都具有value v，所以S2中已接受的所有編號小于n的提案中編號最大的那個提案肯定具有value v，導出矛盾從而推翻新提案n不具有value v的假設。根據數學歸納法，我們證明了若滿足P2c，則P2b一定滿足。
P2c是可以通過消息傳遞模型實現的。另外，引入了P2c后，也解決了前文提到的P1不完備的問題。
算法的內容
要滿足P2c的約束，proposer提出一個提案前，首先要和足以形成多數派的acceptors進行通信，獲得他們進行的最近一次接受（accept）的提案（prepare過程），之后根據回收的信息決定這次提案的value，形成提案開始投票。當獲得多數acceptors接受（accept）后，提案獲得批準（chosen），由proposer將這個消息告知learner。這個簡略的過程經過進一步細化后就形成了Paxos算法。
在一個paxos實例中，每個提案需要有不同的編號，且編號間要存在全序關系?？梢杂枚喾N方法實現這一點，例如將序數和proposer的名字拼接起來。如何做到這一點不在Paxos算法討論的范圍之內。
如果一個沒有chosen過任何proposer提案的acceptor在prepare過程中回答了一個proposer針對提案n的問題，但是在開始對n進行投票前，又接受（accept）了編號小于n的另一個提案（例如），如果和n具有不同的value，這個投票就會違背P2c。因此在prepare過程中，acceptor進行的回答同時也應包含承諾：不會再接受（accept）編號小于n的提案。這是對P1的加強：
P1a：當且僅當acceptor沒有回應過編號大于n的prepare請求時，acceptor接受（accept）編號為n的提案。
現在已經可以提出完整的算法了。
決議的提出與批準
通過一個決議分為兩個階段：
prepare階段：
proposer選擇一個提案編號n并將prepare請求發送給acceptors中的一個多數派；
1.
prepare階段：
2.
proposer選擇一個提案編號n并將prepare請求發送給acceptors中的一個多數派；
3.
acceptor收到prepare消息后，如果提案的編號大于它已經回復的所有prepare消息(回復消息表示接受accept)，則acceptor將自己上次接受的提案回復給proposer，并承諾不再回復小于n的提案；
4.
批準階段：
5.
當一個proposer收到了多數acceptors對prepare的回復后，就進入批準階段。它要向回復prepare請求的acceptors發送accept請求，包括編號n和根據P2c決定的value（如果根據P2c沒有已經接受的value，那么它可以自由決定value）。
6.
在不違背自己向其他proposer的承諾的前提下，acceptor收到accept請求后即批準這個請求。
這個過程在任何時候中斷都可以保證正確性。例如如果一個proposer發現已經有其他proposers提出了編號更高的提案，則有必要中斷這個過程。因此為了優化，在上述prepare過程中，如果一個acceptor發現存在一個更高編號的提案，則需要通知proposer，提醒其中斷這次提案。
參考資料 >