用白話重新推導 Paxos，說明容錯共識幾乎是從「多數派 acceptor 必須達成一致」這個要求無可避免地長出來的。
這篇短文把 The Part-Time Parliament 裡的共識演算法從希臘寓言裡拆出來，改成從它必須滿足的安全性性質一步步推導出來。一群 acceptor 接受帶編號的提案，當多數派 acceptor 接受了同一個帶著某個值的提案，該值就算被選定。整套安全性最後只收斂成一條不變式 P2c：提案者在發出編號 n 的提案之前，必須先聽過多數派 acceptor 的回覆，並且沿用其中編號最高的那個已接受提案的值。這條不變式由兩階段協定來維持——prepare 階段讓 acceptor 承諾不再接受編號更小的提案並回報自己接受過什麼，accept 階段再把第一階段限定下來的值提交出去。在節點當機與訊息可能遺失的非同步網路下，安全性是無條件成立的；活性則需要選出單一的 distinguished proposer，而依 FLP 不可能性結果，這個選舉必須依賴隨機性或真實時間。
2001 年時 Paxos 已經問世十多年，但它的正典版本 The Part-Time Parliament 把演算法包裝成一座希臘小島議會的考古報告，用 Lamport 自己的話說，對許多讀者而言那簡直是天書。真正需要容錯複本的工程師，當時要嘛把系統建在單一中央伺服器上——伺服器一掛整個服務就跟著掛，要嘛依賴 two-phase commit——協調者當機時就整個卡住。來自 Time, Clocks, and the Ordering of Events in a Distributed System 的狀態機複製方法早已是分散式系統理論中被引用最多的想法，但它預設了一個沒有人能講清楚的前提：如何對指令序列達成一致。Fischer、Lynch 與 Paterson 在 1985 年已經證明，在非同步模型下只要有一個節點可能故障，就沒有決定性演算法能保證達成共識，因此任何可用的答案都必須把「永遠安全」和「通常會結束」這兩件事切乾淨。這篇筆記存在的理由，就是要讓那個答案能用平常的句子讀懂。
當多數派 acceptor 接受了同一個帶著某值的提案，該值即被選定。這之所以成立，是因為固定 acceptor 集合中的任兩個多數派至少共用一個成員，所以任何後來的多數派都不可能繞過那個已經知道先前決定的 acceptor。這唯一的交集節點就是整個安全性論證的全部機械基礎，也是為什麼同一編號下 acceptor 最多只能接受一個值。Lamport 也點出這可以自然推廣成一般的 quorum 系統，並把這個觀察上溯到他 1978 年關於可靠分散式多行程系統的論文。
這篇文章不是先給出協定再證明它正確，而是先寫下想要的性質——P2：若帶值 v 的提案被選定，則所有編號更高且被選定的提案也帶值 v——再分三步把它強化。P2a 把義務從「被選定的提案」搬到「被接受的提案」，P2b 再往前搬到「被發出的提案」，P2c 則把它變成發提案當下就能在本地檢查的條件。每一步都是被具體反例逼出來的，而不是為了方便才這樣選。回報是：兩階段協定讀起來像是唯一可能寫出的東西，這正好呼應 Lamport 說共識演算法幾乎是從它的需求無可避免地推出來的。
P2c 說：當編號 n、值為 v 的提案被發出時，必須存在一個多數派 S，使得 S 中沒有任何 acceptor 接受過編號小於 n 的提案，或者 v 就是 S 中所有 acceptor 接受過、編號小於 n 的提案裡編號最高者的值。這正是讓「對提案編號做歸納」能走完的關鍵：任何多數派 S 都會和當初選定提案 m 的那個多數派 C 相交，因此 S 裡看得到的最高編號值必定已經是被選定的值。維持 P2c 是整個演算法唯一的安全性義務。Paxos 其餘的一切，都只是為了在非同步、會當機的系統裡把 P2c 撐住的機械裝置。
P2c 要求提案者對「還沒發生的接受行為」下判斷，這在物理上不可能。Paxos 的繞法是讓提案者去控制未來而不是預測未來：prepare 請求向每個 acceptor 索取一個承諾——今後絕不再接受編號小於 n 的提案。一旦多數派給出承諾，那個多數派日後還可能接受的、編號小於 n 的提案集合就被凍結了，提案者對「其中編號最高者」的快照因此永遠有效。這一步把一個關於未來的無界問題換成一個關於過去的有界問題，也是整個演算法的觀念核心。
第一階段送出帶編號的 prepare 請求，收集承諾以及對方先前接受過的提案；第二階段送出 accept 請求，帶的值要嘛是被那些回覆逼出來的，要嘛在沒有人回報任何已接受提案時由提案者自由決定。結構上最關鍵的事實是：第一階段完全不提到值，提案者要到第二階段才對值做出承諾。這正是領導者可以只跑一次第一階段、之後重複沿用於許多次決議的原因，文中也明白指出這是狀態機實作能有效率的關鍵。
演算法裡每一條規則都是單邊的：acceptor 忽略任何請求都不會傷害安全性，所以規格只需要說明什麼時候「可以」回應。於是安全性在訊息遺失與重複、任意延遲、當機與重啟、提案被中途放棄，甚至多台伺服器同時自認是領導者的情況下都仍然成立。活性則完全另外處理，靠選出單一的 distinguished proposer，而文中明講：依 FLP 結果，這種選舉必須用到隨機性或真實時間（例如 timeout）。把兩者切開之後，安全性論證可以是無條件的，活性論證則被允許只是盡力而為。
完整的 Paxos 就是把共識套進狀態機複製方法：指令序列的每一格各跑一個獨立的共識實例，第 i 個實例選出的值就是決定性狀態機執行的第 i 個指令。因為狀態機是決定性的，所有執行相同指令序列的伺服器會產生完全相同的狀態與輸出，客戶端因此可以採用任何一台伺服器產生的輸出。每台伺服器在每個實例中同時扮演 proposer、acceptor 與 learner，而共識演算法保證第 135 個指令最多只會有一個值被選定。這就是後來幾乎所有共識系統都繼承下來的 replicated log 形狀。
提案者從自己專屬、與他人不相交的編號空間中挑一個提案編號 n，向多數派 acceptor 送出帶編號 n 的 prepare 請求。acceptor 只有在 n 大於它已回應過的所有 prepare 編號時才回覆，回覆內容是一個承諾——今後不再接受編號小於 n 的提案——外加它已經接受過的最高編號提案（若有）。作為最佳化，若某個 prepare 請求的編號低於它已給出的承諾，acceptor 直接忽略即可，因為它反正也不會接受由此產生的提案。忽略請求永遠是安全的，這也是為什麼 acceptor 的規則全部寫成「允許」而非「必須」。
若多數派 acceptor 都回覆了，提案者就針對編號 n 送出 accept 請求，其值 v 取自這些回覆中編號最高的提案的值；若沒有任何回覆者報告過已接受的提案，提案者可以自由選值，例如填入一個新的客戶端指令。accept 請求不必送給和第一階段回覆者相同的 acceptor 集合。acceptor 會接受該提案，除非它已經回應過編號大於 n 的 prepare 請求——這就是條件 P1a，而 P1a 涵蓋了原本的 P1。當多數派接受了同一個帶編號的提案，值就在那一瞬間被選定，儘管不見得有任何參與者觀察得到那一刻。
套用忽略最佳化之後，acceptor 只需要記住兩件事：它接受過的最高編號提案，以及它回應過的最高 prepare 編號。因為 P2c 必須在任何故障下都保持不變，這兩項都得撐過當機重啟，所以它們放在穩定儲存中，而且 acceptor 會先把打算送出的回應寫入穩定儲存，才真的把回應送出去。提案者需要的持久狀態少得多：提案者隨時可以中途放棄一個提案並徹底忘掉它，只要它不再用同一個編號發出另一個提案即可。編號的唯一性由「每個提案者使用互不相交的編號集合」來保證，同時它也把自己用過的最高編號記在穩定儲存裡。
learner 必須查出某個提案已被多數派 acceptor 接受。最直接的做法是每個 acceptor 每次接受提案就通知所有 learner，這樣學得最快，但訊息數是 acceptor 數與 learner 數的乘積。另一種做法是把接受訊息集中送給一個 distinguished learner（實作中就是選出來的領導者），再由它轉告其他人，訊息數只剩兩者之和，代價是多一輪往返並多一個單點故障；改用一組 distinguished learner，則是用通訊量換可靠度。由於訊息可能遺失，有可能某個值已被選定卻沒有任何 learner 發現，而 acceptor 故障也可能讓人無法判定是否真有多數派接受過；因此需要確定答案的 learner，只能請提案者依上述演算法再跑一次。
兩個提案者互相干擾會產生具體的活鎖：p 完成編號 n1 的第一階段，q 接著完成 n2（大於 n1）的第一階段，於是 p 的 accept 請求被忽略；p 再用 n3（大於 n2）完成第一階段，於是換 q 的 accept 請求被忽略，如此永無止境。解法是選出唯一的 distinguished proposer，只有它會嘗試發出提案；只要它能和多數派 acceptor 通訊，並使用比任何已用過的編號都大的編號，它的提案就會被接受。為了找到這樣的編號，它一旦得知有更高編號的請求就放棄並重試，這也是為什麼忽略請求的 acceptor 最好回頭通知提案者——這只是效能最佳化，不影響正確性。依 FLP，這個選舉必須用到隨機性或真實時間，但選舉失敗最多只會讓系統停滯，永遠不會破壞安全性。
新選出的領導者同時是每個實例的 learner，因此它已經知道大部分被選定的指令——例如 1 到 134，再加上 138 與 139。它會對實例 135 到 137 以及所有大於 139 的實例執行第一階段，而且對所有實例使用同一個提案編號，因此一封相當短的訊息就夠了；acceptor 也只有在某個實例中已經收過第二階段訊息時，才需要回覆比一句 OK 更多的內容。凡是第一階段已經把值限定下來的實例，領導者就跑第二階段把它定案；至於中間那些沒有待處理指令的空洞，它直接提出一個不改變狀態的特殊 no-op 指令來補，因為空洞後面的指令在洞補起來之前無法執行。等 136 與 137 被填成 no-op，138 到 140 就可以執行，領導者接著把 141、142 依序指派給後續進來的客戶端指令。
領導者最多可以領先 alpha 個指令，也就是在 1 到 i 尚未確認被選定前就先提出 i+1 到 i+alpha；若它在半途故障，序列中可能出現最多 alpha 減 1 個指令的空洞，由下一任領導者用 no-op 補上。由於領導者故障與改選應該是罕見事件，穩態下執行一個指令的實際成本只有第二階段；文中引用 Keidar 與 Rajsbaum 的結果，指出第二階段已達到任何容錯協議演算法可能的最低成本，因此 Paxos 基本上是最佳的。成員變更則被折進狀態機本身：當前的伺服器集合是複製狀態的一部分，用一般的狀態機指令就能修改，而執行實例 i+alpha 的伺服器集合，由第 i 個指令執行後的狀態決定。單憑這條規則，任意複雜的重新組態演算法都能寫成一般的應用邏輯。
Paxos Made Simple 才是業界真正讀進去的那個 Paxos 版本，而它的狀態機那一節，等於是後來幾乎所有 replicated log 的設計藍圖。Google 的 Chubby 鎖服務（Burrows, OSDI 2006）實作的就是這套多實例設計，成為 GFS 與 Bigtable 底下的協調與 metadata 層，其後續論文 Paxos Made Live 則把這篇筆記留給實作者的空白一項項列了出來。Spanner 在每個 tablet 的複本之上跑一個 Paxos 狀態機，Megastore 則是每個 entity group 跑一個，兩者用的都是這裡描述的「領導者即 distinguished proposer、每個 log 格子一個實例」結構。ZooKeeper 的 Zab 協定沿用了同樣的「領導者加上有序日誌」形狀；Raft 更是明白地以「比這個演算法更好懂的替代品」為目標而寫，同時保留了多數派 quorum、以單調遞增的 term 取代提案編號，以及對日誌空洞的處理紀律——etcd、CockroachDB、TiDB、Consul 與 Kafka 的 KRaft 都是 Raft 的後代，因此也是 Paxos 隔一代的後代。Cassandra 的 lightweight transactions 則是每個 compare-and-set 操作跑一輪 Paxos，把 prepare 與 accept 兩階段直接暴露給應用開發者。這篇筆記固定下來的詞彙——proposer、acceptor、learner、prepare 與 accept 階段、quorum、實例、以及用 no-op 補洞——如今已是討論共識時的預設語言。
“The Paxos algorithm, when presented in plain English, is very simple.”
“Instead of trying to predict the future, the proposer controls it by extracting a promise that there won't be any such acceptances.”
“Election of a single leader is needed only to ensure progress.”