Paxos：以多數決 quorum 讓複本日誌在節點故障與訊息遺失下維持一致，並在網路穩定時取得進展。
Paxos 島的議會必須讓每位議員手上的帳冊保持一致，即使議員隨時離開議事廳、信差可能延遲、遺失或重複投遞訊息。Lamport 的答案是一套建立在三個條件之上的協定：每次投票（ballot）都有唯一編號、任兩次投票的 quorum 必定相交、而新一輪投票必須採用其 quorum 成員先前投過的最高編號那一票的法令。光是這三個條件就能證明任兩次成功的投票必然選出同一條法令，因此一致性完全不依賴時序、訊息送達，也不依賴是否只有一位領導者。進展（progress）是事後另外加上去的一層：選出主席並搭配計時器，把非同步共識的不可能性完全隔離在活性（liveness）那一半。接著替每個法令編號各跑一個協定實例，並讓第一階段對所有實例只執行一次，就得到一個複本狀態機，每條法令只需三個訊息延遲、約 3N 則訊息即可通過。
到 1990 年，狀態機方法（state-machine approach）已經存在十多年：Lamport 1978 年的時鐘論文提出了第一個實作任意狀態機的演算法，1984 年的成果則能容忍任意固定數量 f 的任意型（Byzantine）故障。這些演算法換來了有界時間回應與惡意容錯，代價卻很高——f 越大，硬體冗餘、通訊頻寬與回應時間的成本就越高；而且兩台伺服器無法互相通訊等同於其中一台故障，一旦故障數超過 f，各伺服器的狀態複本就會不一致。資料庫界則有 three-phase commit，協調者與參與者之間同樣要交換五則訊息，但它只能在 commit 與 abort 之間二選一。Fischer、Lynch 與 Paterson 在 1985 年已證明非同步環境下沒有任何協定能保證達成一致，因此任何關於進展的宣稱都必須附上時序假設。這篇論文寫於 1990 年，直到 1998 年才刊出，並以一段編輯說明包裝：這份投稿是在 TOCS 編輯室的檔案櫃後面被發現的。
Paxos 的數學家不是先設計協定再證明，而是先對「所有曾經進行過的投票集合 B」定義三個條件：B1 要求每次投票編號唯一，B2 要求任兩次投票的 quorum 至少有一位祭司重疊，B3 要求一次投票的法令必須等於其 quorum 成員曾參與過的最晚一次較早投票的法令。引理證明只要某次投票成功，之後所有投票都帶著同一條法令；定理 1 由此推得任兩次成功投票選出的法令必然相同。協定接著被定義成「所有能維持 B1 到 B3 的動作」，這也是為什麼每條關於承諾與回報投票紀錄的規則都有顯而易見的理由。順序很重要：這些數學結果確實早於演算法，是數學家在試圖證明「不可能存在可行協定」時發現的。
舊的宗教會議程序要求所有祭司到齊，等到祭司開始隨意進出，這套程序終於徹底失效。Paxos 把全體同意換成只需是一個多數集合的 quorum，而真正被用到的性質只有一個：任兩個多數集合至少有一位祭司重疊。這個交集正是 B2 成立的原因，也是任何新投票必然會看見某次已成功投票之成員所投的票的原因。論文提到這個定義後來被放寬——從簡單多數，到總權重超過一半的集合，再到依出席紀錄給定的象徵性權重——顯示演算法真正依賴的是相交性，而不是計票人數。
祭司 q 以 LastVote(b, v) 回覆 NextBallot(b) 時，除了回報自己在編號小於 b 的投票中最高的那一票，同時也承諾往後不再對編號小於 b 的任何投票投下新的票。這個承諾把該祭司的 MaxVote 凍結住，讓主席在第一階段算出的值，到第二階段決定法令時仍然有效。關鍵在於第一輪根本不夾帶法令：主席先從多數集合的 LastVote 回覆中判斷是否已有法令可能被選定，之後才挑出要提的法令。這種「晚決定」正是 Paxos 與由 commit 協定改造而成的版本的差別，也是第一階段能跨法令重複利用的前提。
在基本協定中，每個步驟都是可做可不做的：祭司可以忽略 NextBallot 訊息，可以在被允許投票時仍選擇不投，也可能弄丟記錄當前投票進度的那張紙。不採取行動、或沒收到訊息，最多只能讓某個動作不發生，而缺少動作永遠無法讓 B1 到 B3 變成假，因此一致性在任意當機、訊息遺失與重複之下都成立。這正是論文能把進展當成完全獨立的一層（計時器加主席選舉）疊上去的原因，也是為什麼多位祭司同時自認主席只會拖慢進度、絕不會讓兩本帳冊互相矛盾。共識中所有麻煩的部分都被推進活性那一半，也就是 FLP 不可能性所在之處。
議會協定在邏輯上等於替每個法令編號各跑一個宗教會議協定實例，但由同一位主席對所有實例只執行一次步驟 1 與步驟 2。一則 NextBallot(b, n) 訊息就是所有編號大於 n 之實例的第一階段，而議員的單一回覆只需帶上他實際投過的那有限多張票，因為他不可能在無限多個實例中投過票。之後每個新請求只花掉步驟 3 到 5——BeginBallot、Voted、Success——所以一條法令只需三個訊息延遲、約 3N 則訊息；若主席把 BeginBallot 與前一條法令的 Success 合併，則降到約 2N。這個攤提正是把五訊息的一致性協定變成實用複本日誌的關鍵。
新上任的主席可能得知第 126 號法令已通過，卻對第 125 號一無所知，因為當初投過 125 號的人都不在廳內。若把新提案編成 125 號，它就會排在一條已經通過的法令之前，可能違反公民的預期。因此主席會用傳統的「橄欖節法令」填滿每個空洞，這條法令什麼也不改變，卻能維持法令排序性質：若法令 A 與 B 都是重要法令，且 A 在 B 被提出之前就已通過，則 A 的編號比 B 小。用 commit 協定的語彙來說，這個技巧就是把 abort 轉譯成日誌中一筆無害的紀錄。
第 4 節給出對照表：議員對應伺服器、公民對應用戶端程式、現行法律對應資料庫狀態、通過法令對應執行一條狀態機命令。因為所有伺服器取得同一串命令序列，它們就會產生同一串回應與狀態變化，於是設計新系統時唯一要發明的只有狀態機本身——一個從（命令, 狀態）對映到（回應, 新狀態）的函式。容錯與同步問題交給一個早已證明正確的標準演算法處理。用論文自己的話說：函式比分散式演算法容易設計得多，也容易做對得多。
一次投票 B 是一個四元組：法令 Bdec、非空的 quorum Bqrm、實際投票者集合 Bvot，以及取自無界有序集合的編號 Bbal。當 Bqrm 是 Bvot 的子集合時該次投票即為成功，成功投票的法令就是宗教會議選定的法令。一張票是（祭司, 投票編號, 法令）三元組，空票的編號定為負無窮大，讓每位祭司永遠有定義良好的最大值。MaxVote(b, p, B) 是 p 編號小於 b 的最大一票，對集合 Q 則取其成員的最大值；B3 說的正是：只要 MaxVote(Bbal, Bqrm, B) 不是空票，投票的法令就必須等於它。集合 B 本身是歷史變數，Paxons 稱它是只有諸神觀察得到的量，因為任何凡人都可能永遠不知道它的值。
步驟 1：祭司 p 從自己專屬的編號區段中選一個大於 lastTried[p] 的編號 b，並送出 NextBallot(b)。步驟 2：祭司 q 若發現 b 大於 nextBal[q]，就把 nextBal[q] 設為 b，並以 v 等於 prevVote[q] 回覆 LastVote(b, v)，同時等於承諾不再對編號小於 b 的投票投下新票。步驟 3：p 收到某個多數集合 Q 的 LastVote 回覆後，依 B3 決定法令 d——取回報中最大那一票的法令，若全是空票則可任選——並向 Q 送出 BeginBallot(b, d)。步驟 4：nextBal[q] 等於 b 的議員投票，把它寫進 prevVote[q]，並回覆 Voted(b, q)。步驟 5 與 6：當 Q 的每位成員都投票後，p 把 d 寫進帳冊並廣播 Success(d)，收到的人各自把 d 寫進自己的帳冊。
基本協定存在的目的，就是把祭司必須寫在帳冊背面的資訊壓縮成三項：lastTried[p]，他最後嘗試發動的投票編號；prevVote[p]，他投過票的最高編號投票中的那一票；以及 nextBal[p]，他送出過 LastVote 的最大 b 值。附錄把 prevVote 拆成 prevBal 與 prevDec，並加上 outcome[p]，也就是寫進帳冊的法令。其餘一切——status、累積的 prevVotes 集合、quorum、投票者、當前法令——都寫在一張可能弄丟的紙上；紙一旦遺失，status 就退回 idle，該祭司單純停止主持那次投票。由於基本協定一次只主持一輪投票，並忽略自己先前投票的訊息，持久化狀態的大小與嘗試過多少輪投票無關，始終是常數。
進展要求必須有人負責發動投票，但發動太頻繁同樣會阻礙進展，因為一個高編號的 NextBallot 會引出承諾，把正在進行中的投票扼殺掉。Paxons 量測過自己的系統：待在廳內的信差 4 分鐘內必定送達，待在廳內的祭司 7 分鐘內必定作出反應，因此一次來回在 22 分鐘內完成。主席只在兩種情況下重新發動投票：前 22 分鐘內沒能執行到步驟 3 或步驟 5，或是得知有人用了更大的投票編號——議員看到過期的 b 時會把 nextBal[q] 回傳給他。主席選舉只需滿足一個要求：無人進出後 T 分鐘內，廳內恰有一位祭司自認是主席；論文給的例子是選字母序最後的名字，每位祭司至少每 T 減 11 分鐘宣告一次自己在場。
新任主席若帳冊已完整到第 n 號法令，就送出 NextBallot(b, n)，它同時是所有編號大於 n 之實例的第一階段。每位議員回覆時附上自己帳冊中所有編號大於 n 的法令，加上尚未定案法令的一般 LastVote 資訊，並請主席補送他缺少的、編號小於等於 n 的法令。主席立刻對那些法令已被 B3 決定的實例執行步驟 3，之後每收到一個新請求，就指派他仍可自由選擇的最小法令編號。前任主席留下的空洞則以橄欖節法令補滿，讓序列保持連續、可依序套用。
隨著法令數量增加，議員把帳冊改成法典，只記錄法律的現況以及最後一條已反映其中的法令編號——這就是快照加上日誌位置。帳冊完整到 1298 號的議員得知 1299 號把橄欖稅設為每噸 6 drachma 時，只要改掉稅則那一條並把標記推進；若接著聽到 1302 號，他先寫在書後，等收到 1300 與 1301 號之後才套用。為了讓短暫離開的議員不必抄整本法典就能追上進度，最近一週的法令會以清單形式留在書後。這正是壓縮合併（log compaction）再加上一段近期紀錄尾巴以支援增量復原。
曾經同時出現兩位乳酪檢查員，因為被撤換的那位還不知道自己已被替換，於是每張任命法令都夾帶提案時間與固定任期——Dikstra 擔任乳酪檢查員 3 個月，自所述時間或前任任期結束（取較晚者）起算。由於 Paxons 只能把時間判斷到 15 分鐘的精度，任期自 8:30 開始的人要等到自己觀測到 8:45 才上工，這就是帶時鐘偏移保護的 lease。查詢則由單調性條件處理：慢讀（slow read）要通過一條法令，快讀（fast read）直接回傳本地複本，實務折衷是在商業交易中一路帶著法令編號，或把每個法律領域的查詢導向該領域唯一指定的專家。只有在該領域的法律不會改變時，才允許同時存在多位專家——報稅季的稅法專家就是這樣撐過查詢洪峰的。
Paxos 成為大型系統中容錯協調的預設答案。Google 的 Chubby 鎖服務（Burrows, OSDI 2006）本質上就是一個包著類檔案系統介面的 Paxos 日誌；而 Paxos Made Live 報告（Chandra、Griesemer、Redstone, PODC 2007）記錄了論文未指定的那些區塊——主席選舉、日誌壓縮、成員管理、磁碟毀損、測試——才是實作工作的主體。Spanner 為每個分片各配一個 Paxos group，Megastore 則以每個 entity group 一個 Paxos 實例跨資料中心複製，而 Bigtable 與 GFS 把 metadata 的一致性外包給 Chubby。Viewstamped Replication（Oki 與 Liskov, 1988）在本文的後記中被承認似乎與 Paxon 協定等價，ZooKeeper 的 Zab 則是同樣骨架、改寫成 primary-order broadcast 的版本。Raft（Ongaro 與 Ousterhout, 2014）明確以「可理解的替代品」為目標設計，卻完整保留了這副骨架：以單調遞增的 term 取代投票編號、以兼具承諾功能的投票請求取代 NextBallot／LastVote、領導者只為活性而存在；經由 Raft，這套設計進入了 etcd、Consul、CockroachDB、TiKV 與 Kubernetes 控制平面。論文的次要構想同樣流傳深遠：官員任期成為 lease，法典成為快照與壓縮合併，法令編號的單調性技巧則演化成現代共識儲存中的 read-index 與 lease read；而 Flexible Paxos（2016）後來證明只有第一階段與第二階段的 quorum 之間才真的需要相交。
“Recent archaeological discoveries on the island of Paxos reveal that the parliament functioned despite the peripatetic propensity of its part-time legislators.”
“However, in the Paxon Synod, having multiple presidents could only impede progress; it could not cause inconsistency.”
“Functions are much easier to design, and to get right, than distributed algorithms.”