本文以圖文並茂的方式重新演繹 Paxos 開山之作 《The Part-Time Parliament》[1]，並嘗試解釋原論文中語焉不詳的地方。

背景

在 Paxos 小島上，施行著一種 Parliament(議會) 政治。小島上執行的所有 decree(法令) 都需要先由 Parliament 在 Chamber 內表決通過。legislator(議員) 將 Parliament 通過的 decree 記錄在他隨身攜帶的 ledger(賬本) 上。比如某 legislator 在其 ledger 記錄了第 155 號 decree 如下：

為了防止島上的 decree 出現衝突，導致不必要的糾紛, 任何兩個 legislator 記錄的相同編號的 decree 要麼是一樣的，要麼其中某個 legislator 不存在該編號的 decree。

legislator 傾向於通過別人發起的 decree 請求, 只要其他 legislator 發起的 decree 請求與自己 ledger 記錄不衝突，則為它投票。

為了保證 decree 的順利產生， 除了在 ledger 正面記錄表決通過的 decree, legislator 還需要記錄一些中間過程: 需要長期持有的資訊記錄在 ledger 背面, 這部分資訊可以被劃掉；需要臨時持有的資訊記錄在草稿紙上, legislator 僅在 Chamber 內保留記錄資訊的草稿紙。

legislator 都是兼職的(part-time), 因此他們可以選擇隨時離開或加入 Chamber 參與投票。

由於 Chamber 內人員眾多，比較嘈雜，legislator 之間通過只能通過信使(messager)進行交流。信使同樣也是兼職的，他們和 legislator 一樣，可以隨時選擇進入或離開 Chamber(即使他正在參與某次訊息的傳遞。這將導致這條訊息永遠消失，或者這條訊息會在不可預見的未來重新參與傳遞)。

Chamber 內 legislator 進進出出有個比較嚴重的問題： 兩次參會的人如果沒有交集， 他們可能會投票產生互相沖突的提案，這將導致 legislator 記錄的相同編號 decree 產生衝突，不能滿足一開始對 decree 的約束。(任何兩個 legislator 記錄的相同編號的 decree 要麼是一樣的，要麼其中某個 legislator 不存在該編號的 decree)

為了解決這個問題，Paxos 小島上的人對 與會人數(Quorum) 進行了約束：當與會人數佔 legislator 總人數的一半以上時，才能發起提案流程，否則，法案無法通過。根據鴿巢原理，兩次投票至少有一個 legislator 都有參與，他將會拒絕衝突的提案內容形成 decree。

當與會的所有 legislator 都投票表示贊成(意味著與歷史 decree 無衝突)， 提議的已通過成為 decree， 周知到所有與會人員，記錄在 ledger 證明正式生效。

The Single-Decree Synod

上一部分介紹了 paxos 小島上的 Parliament 將 decree 從提出到通過的整體流程。在 Parliament 中可以通過很多 decree， 本節為了探索 decree 達成共識的具體細節，先從達成單個 decree 的 Synod 會議聊起。Synod 和 Parliament 的差異如下：

在 Synod 會議中，每個 Priest 可以參與多輪 投票(Ballot)。每位 priest 每輪 ballot 僅能投一次票。 ballot B 包含一下四種資訊:

• B_dec: 本輪 ballot 提議待通過的 decree;
• B_qrm: 與會的 priest 的集合;
• B_vot: 已參與投票的 priest 的集合;
• B_bal: 本輪 ballot 的編號, 全序。(注意與 decree 編號區分)
  

根據第一部分的鋪墊，我們知道當且僅當 B_vot 是 B_qrm 的子集，即所有與會的 priest 都已參與投票，這次 ballot 才是成功的(本輪 ballot 提議的 decree 通過)。

為了保證 Synod 會議最終最多產生唯一 decree(無衝突), 我們需要保證以下三點條件:

• B1: 為了標識 ballot，每一輪 ballot 需要有唯一的編號。
• B2: 任意兩輪 bollot 至少保證有一個 priest 同時參與。(第一部分已經解釋過這麼做的原因)
• B3 : 如果某些 priest 在之前的 ballot 已經參與過投票，則本輪 ballot 投票的 decree 等於他們參與的最近一次 ballot 的 decree。

比如，在 Fig. 1 [1] 中, 展示了五輪 ballot(ballot 編號分別為 2, 5, 14, 27, 29)。 Synod 共有五位 priest: A, B, Γ，Δ 和 E。 每輪 ballot 羅列出來的 priest 就是本輪與會的 Quorum。用矩形框框出的 priest 代表本輪已參與投票的 priest。依次解釋每輪 ballot 的內容如下：

• 2: 最早的 ballot，可以投票任何 decree。 本輪提議 decree α， Δ 已為它投票。
• 5: 參與本輪 ballot 的 A, B, Γ 和 E 都沒有參與更早的投票，因此他們都可以為本輪提議 decree β 投票。本輪僅 Γ 參與了投票。
• 14: 本輪 ballot 中, Δ 已經為 decree α 投過票(ballot 2 中)，因此本輪 decree 只能為 α。本輪 B, E 已經投票。
• 27: 本輪 ballot 中， Δ 已經為 decree α 投過票(ballot 2 中, 注意 Δ 未參與 ballot 14 的投票)， Γ 已經為 decree β 投過票(ballot 5 中)。因此本輪 decree 必須與 ballot 5(max(2, 5)) 相同，即 decree β。本輪與會的 A, Γ，Δ 都已參與投票，本輪 ballot 成功通過了 decree β。
• 29: 參與本輪 ballot 的 priest 中，B 參與的最新一次投票為 ballot 14， Γ，Δ 參與的最新一次投票為 ballot 27， 因此本輪 ballot 的 decree 必須和 ballot 27(max(14, 27) ) 一致，即 decree β。本輪僅 B 完成了投票。

某輪 ballot B 一旦投票成功，參與後續 ballot 的 priest 至少有一位曾參與 B 的投票(B2)，根據 B3, 後續 ballot 投票的 decree 必須保持和 ballot B 一致。因此， 後續通過的所有 decree 都必須和第一次通過的 decree 內容保持一致。

為了滿足 B1 的需求，將 Bollot 編號設為 <priest id, ballot id> 格式, 其中 priest id 表示發起該 Ballot 的 priest 的編號。同一個 priest 不會發起編號相同的 Ballot， 因此能滿足 Ballot 編號不衝突的要求。

在第一部分已經討論，為了滿足 B2，只需要保證每次參與投票的 priest 人數佔總人數的一半以上，根據鴿巢原理，任意兩輪 bollot 至少保證有一個 priest 同時參與。

要滿足 B3 的要求相對麻煩一些。保證 B3 的關鍵在於 Ballot 編號小於當前正在處理的 Ballot 的集合不再變動(否則無法拿到最新的「本輪 ballot 投票的 decree 等於他們參與的最近一次 ballot 的 decree」。)。

為了保證「 Ballot 編號小於當前正在處理的 Ballot 的集合不再變動」， 借鑑兩階段提交策略，將請求拆分為兩部分：第一部分向 B_qrm 的 priest 申請處理當前 Ballot(編號為 B_bal)，並且要求他們保證不再處理 「Ballot 編號小於當前正在處理的 Ballot」；第二部分才向 B_qrm 實際發起本輪 Ballot 的資料請求。

實現細節見下圖：

The Multi-Decree Parliament

The Multi-Decree Parliament 演演算法實際上是對每個帶有編號的 decree 執行 The Single-Decree Synod 演演算法，最終實現一系列 decree 都能達成一致。

參考文獻

[0] 本文所有繪圖均使用 draw.io 繪製
[1] The Part-Time Parliament