Paxos算法是萊斯利·蘭伯特（英語：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）提案，若提案獲得多數派（majority）的 acceptors 的接受，則稱該提案被準許（chosen）；
- learners 隻能“學習”被準許的提案。
劃分角色後，就可以更精确的定義問題：
- 決議（value）隻有在被 proposers 提出後才能被準許（未經準許的決議稱為“提案（proposal）”）；
- 在一次 Paxos 算法的執行執行個體中，隻準許（chosen）一個 value；
- learners 隻能獲得被準許（chosen）的 value。
在 Leslie Lamport 之後發表的paper中将 majority 替換為更通用的 quorum 概念，但在描述classic paxos的論文 Paxos made simple 中使用的還是majority的概念。
另外還需要保證 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），來看看在什麼情況下對任何編号為 n（n>m）的提案都含有 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=m+1時，采用反證法，假如提案n不具有value v，而是具有value w，根據P2c，則存在一個多數派S1，要麼他們中沒有人接受過編号小于n的任何提案，要麼他們已經接受的所有編号小于n的提案中編号最大的那個提案是value w。由于S1和通過提案m時的多數派C之間至少有一個公共的acceptor，是以以上兩個條件都不成立，導出沖突進而推翻假設，證明了提案n必須具有value v；
若（m+1）..（N-1）所有提案都具有value v，采用反證法，假如新提案N不具有value v，而是具有value w',根據P2c，則存在一個多數派S2，要麼他們沒有接受過m..（N-1）中的任何提案，要麼他們已經接受的所有編号小于N的提案中編号最大的那個提案是value w'。由于S2和通過m的多數派C之間至少有一個公共的acceptor，是以至少有一個acceptor曾經接受了m，進而也可以推出S2中已接受的所有編号小于n的提案中編号最大的那個提案的編号範圍在m..（N-1）之間，而根據初始假設，m..（N-1）之間的所有提案都具有value v，是以S2中已接受的所有編号小于n的提案中編号最大的那個提案肯定具有value v，導出沖突進而推翻新提案n不具有value v的假設。根據數學歸納法，我們證明了若滿足P2c，則P2b一定滿足。
P2c是可以通過消息傳遞模型實作的。另外，引入了P2c後，也解決了前文提到的P1不完備的問題。
算法的内容
要滿足P2c的限制，proposer提出一個提案前，首先要和足以形成多數派的acceptors進行通信，獲得他們進行的最近一次接受（accept）的提案（prepare過程），之後根據回收的資訊決定這次提案的value，形成提案開始投票。當獲得多數acceptors接受（accept）後，提案獲得準許（chosen），由acceptor将這個消息告知learner。這個簡略的過程經過進一步細化後就形成了Paxos算法。
在一個paxos執行個體中，每個提案需要有不同的編号，且編号間要存在全序關系。可以用多種方法實作這一點，例如将序數和proposer的名字拼接起來。如何做到這一點不在Paxos算法讨論的範圍之内。
如果一個沒有chosen過任何proposer提案的acceptor在prepare過程中回答了一個proposer針對提案n的問題，但是在開始對n進行投票前，又接受（accept）了編号小于n的另一個提案（例如n-1），如果n-1和n具有不同的value，這個投票就會違背P2c。是以在prepare過程中，acceptor進行的回答同時也應包含承諾：不會再接受（accept）編号小于n的提案。這是對P1的加強：
P1a：當且僅當acceptor沒有回應過編号大于n的prepare請求時，acceptor接受（accept）編号為n的提案。
現在已經可以提出完整的算法了。
決議的提出與準許
通過一個決議分為兩個階段：
- prepare階段：
- proposer選擇一個提案編号n并将prepare請求發送給acceptors中的一個多數派；
- acceptor收到prepare消息後，如果提案的編号大于它已經回複的所有prepare消息(回複消息表示接受accept)，則acceptor将自己上次接受的提案回複給proposer，并承諾不再回複小于n的提案；
- 準許階段：
- 當一個proposer收到了多數acceptors對prepare的回複後，就進入準許階段。它要向回複prepare請求的acceptors發送accept請求，包括編号n和根據P2c決定的value（如果根據P2c沒有已經接受的value，那麼它可以自由決定value）。
- 在不違背自己向其他proposer的承諾的前提下，acceptor收到accept請求後即準許這個請求。
這個過程在任何時候中斷都可以保證正确性。例如如果一個proposer發現已經有其他proposers提出了編号更高的提案，則有必要中斷這個過程。是以為了優化，在上述prepare過程中，如果一個acceptor發現存在一個更高編号的提案，則需要通知proposer，提醒其中斷這次提案。
執行個體
用實際的例子來更清晰地描述上述過程：
有A1, A2, A3, A4, A5 5位議員，就稅率問題進行決議。議員A1決定将稅率定為10%,是以它向所有人發出一個草案。這個草案的内容是：
現有的稅率是什麼?如果沒有決定，則建議将其定為10%.時間：本屆議會第3年3月15日;提案者：A1
在最簡單的情況下，沒有人與其競争;資訊能及時順利地傳達到其它議員處。
于是, A2-A5回應：
我已收到你的提案，等待最終準許
而A1在收到2份回複後就釋出最終決議：
稅率已定為10%,新的提案不得再讨論本問題。
這實際上退化為二階段送出協定。
現在我們假設在A1提出提案的同時, A5決定将稅率定為20%:
現有的稅率是什麼?如果沒有決定，則建議将其定為20%.時間：本屆議會第3年3月15日;提案者：A5
草案要通過侍從送到其它議員的案頭. A1的草案将由4位侍從送到A2-A5那裡。現在，負責A2和A3的侍從将草案順利送達，負責A4和A5的侍從則不上班. A5的草案則順利的送至A4和A3手中。
現在, A1, A2, A3收到了A1的提案; A4, A3, A5收到了A5的提案。按照協定, A1, A2, A4, A5将接受他們收到的提案，侍從将拿着
我已收到你的提案，等待最終準許
的回複回到提案者那裡。
而A3的行為将決定準許哪一個。
https://zh.wikipedia.org/zh-cn/Paxos%E7%AE%97%E6%B3%95#
Paxos在原作者的《Paxos Made Simple》中内容是比較精簡的：
Phase 1
(a) A proposer selects a proposal number n and sends a prepare request with number n to a majority of acceptors.
(b) If an acceptor receives a prepare request with number n greater than that of any prepare request to which it has already responded, then it responds to the request with a promise not to accept any more proposals numbered less than n and with the highest-numbered pro-posal (if any) that it has accepted.
Phase 2
(a) If the proposer receives a response to its prepare requests (numbered n) from a majority of acceptors, then it sends an accept request to each of those acceptors for a proposal numbered n with a value v , where v is the value of the highest-numbered proposal among the responses, or is any value if the responses reported no proposals.
(b) If an acceptor receives an accept request for a proposal numbered n, it accepts the proposal unless it has already responded to a prepare request having a number greater than n.
借用paxos圖解文中的流程圖可概括為：
執行個體及詳解
Paxos中有三類角色
Proposer
、
Acceptor
及
Learner
，主要互動過程在
Proposer
和
Acceptor
之間。
Proposer
與
Acceptor
之間的互動主要有4類消息通信，如下圖：
這4類消息對應于paxos算法的兩個階段4個過程：
- phase 1
- a) proposer向網絡内超過半數的acceptor發送prepare消息
- b) acceptor正常情況下回複promise消息
- phase 2
- a) 在有足夠多acceptor回複promise消息時，proposer發送accept消息
- b) 正常情況下acceptor回複accepted消息
因為在整個過程中可能有其他proposer針對同一件事情發出以上請求，是以在每個過程中都會有些特殊情況處理，這也是為了達成一緻性所做的事情。如果在整個過程中沒有其他proposer來競争，那麼這個操作的結果就是确定無異議的。但是如果有其他proposer的話，情況就不一樣了。
以paxos中文wiki上的例子為例。簡單來說該例子以若幹個議員提議稅收，确定最終通過的法案稅收比例。
以下圖中基本隻畫出proposer與一個acceptor的互動。時間标志T2總是在T1後面。propose number簡稱N。
情況之一如下圖：
A3在T1發出accepted給A1，然後在T2收到A5的prepare，在T3的時候A1才通知A5最終結果(稅率10%)。這裡會有兩種情況：
- A5發來的N5小于A1發出去的N1，那麼A3直接拒絕(reject)A5
- A5發來的N5大于A1發出去的N1，那麼A3回複promise，但帶上A1的(N1, 10%)
這裡可以與paxos流程圖對應起來，更好了解。acceptor會記錄(MaxN, AcceptN, AcceptV)。
A5在收到promise後，後續的流程可以順利進行。但是發出accept時，因為收到了(AcceptN, AcceptV)，是以會取最大的AcceptN對應的AcceptV，例子中也就是A1的10%作為AcceptV。如果在收到promise時沒有發現有其他已記錄的AcceptV，則其值可以由自己決定。
針對以上A1和A5沖突的情況，最終A1和A5都會廣播接受的值為10%。
其實4個過程中對于acceptor而言，在回複promise和accepted時由于都可能因為其他proposer的介入而導緻特殊處理。是以基本上看在這兩個時間點收到其他proposer的請求時就可以了解整個算法了。例如在回複promise時則可能因為proposer發來的N不夠大而reject：
如果在發accepted消息時，對其他更大N的proposer發出過promise，那麼也會reject該proposer發出的accept，如圖：
這個對應于Phase 2 b)：
it accepts the proposal unless it has already responded to a prepare request having a number greater than n.
總結
Leslie Lamport沒有用數學描述Paxos，但是他用英文闡述得很清晰。将Paxos的兩個Phase的内容了解清楚，整個算法過程還是不複雜的。
至于Paxos中一直提到的一個全局唯一且遞增的proposer number，其如何實作，引用如下：