The Part-Time Parliament（三）：協議流程

04-01

初級協議

前面的文章中我們證明了只要滿足條件 $B1(eta)、B2(eta)、B3(eta)$ ，那麼就一定能對投票達成一致，接下來我們就來具體描述下如何來構造 $B1(eta)、B2(eta)、B3(eta)$ 。

$B1(eta)$ ：

該條件要求每輪表決的發起者需要使用一個與之前輪次表決完全不同的表決編號，可以這樣做：每個投票者在自己的記賬簿的背面記錄他之前發起表決所使用的編號（id），這樣，在下次發起投票時避免選擇已經使用過的投票編號（可以使用遞增的投票編號）；但是這樣無法避免兩個投票者使用相同的投票編號。於是，可以在投票編號上做點文章，將投票編號設置為二元組<id,發起者名稱>，發起者名稱根據字典序決定先後關係，如

$(13, Gamma ho alpha) < (13, Lambda iota u epsilon) < (15, Gamma ho alpha)$

$B2(eta)$ ：

只需要選擇所有成員的大多數( $n/2+1$ )，即可一定能保證 $B2(eta)$ 成立，這個比較簡單。

$B3(eta)$ ：

假如在表決輪 $B$ 中，投票發起者 $p$ 選擇了編號 $B_{bal} = b$ ，選擇了投票參與者為 $B_{qrm} = Q$ ，接下來要確定投票議案 $B_{dec}$ ，根據要求，它必須要選擇 $MaxVote(b, Q, eta)_{dec}$ ，為此，它必須獲得 $forall q in Q, MaxVote(b, q, eta)_{dec}$ 。因此：

$p$ 向 $Q$ 中的每一個成員發起一次查詢請求 $NextBallot(b)$ ；
$q$ 以 $LastVote(b, v)$ 響應 $p$ ，其中 $v$ 就是 $MaxVote(b, q, eta)$ ，如果 $q$ 未執行任何投票，那就是 $null_{q}$ 。步驟2 要求每個成員 $q$ 需要在記賬簿的背面記錄其每一次投票信息。同時， $q$ 在發送完 $LastVote(b, v)$ 信息後還需要保證其不再為其他的編號介於 $(v_{bal}, b)$ 的選舉進行投票（ $v_{bal}$ 就是 $MaxVote(b, q, eta)_{bal}$ ，所以 $v_{bal} < b$ 必然成立），否則 $p$ 根據 $LastVote(b,v)$ 結果而發起的投票法令可能不再滿足 $B3(eta)$ 。
$p$ 收到 $Q$ 中所有 $q$ 的 $LastVote(b, v)$ 響應後：

取所有 $LastVote(b, v)$ 最大的投票編號的那次投票的法令，記作 $d$ ;
$p$ 發起一輪新的表決 $B：B_{bal}=b，B_{qrm} = Q，B_{dec}=d$ ，向 $Q$ 中的所有成員發起消息 $BeginBallot(b, d)$ ；
投票者 $q$ 收到 $BeginBallot(b, d)$ 後，決定是否為該表決進行投票（即贊成該票決）。投票的標準是：如果 $b$ 與之前 $q$ 的 $LastVote(b^{}, v^{})$ 限制相衝突，那麼就不能投票，否則可投可不投（也許取決於心情）。如果 $q$ 為其投票，那麼返回消息 $Voted(b, q)$ 給 $p$ ，並且將本次投票結果寫在自己記賬簿的背面，表明投票；
如果 $p$ 收到了 $Q$ 中所有投票者的 $Voted(b, q)$ 消息，意味著本輪表決成功，於是將本輪表決的法令 $d$ 寫入記賬簿，且發送消息 $Success(d)$ 給 $Q$ 中所有的投票者；
$q$ 收到消息 $Success(d)$ ，將該法令記錄在自己的記賬簿上。

對於一個投票者是否為表決投票，這個可能存在理解上的困惑。每次投票其實有兩個階段組成：階段1表決發起者必須要向表決參與者發起詢問，決定本次投票法令，而根據我們前面描述，一旦參與者回復了法令，那麼不能再對位於該法令的表決編號與投票發起者提出的表決編號之間的表決投票，否則將違背 $B3(eta)$ 。
舉例來說，假如 $q$ 收到了發起者 $p$ 的 $NextBallot(b), b=10$ 請求，其返回的 $LastVote(b, v)$ 結果為 $v_{bal}=5$ ，如果此時 $q$ 收到了另外一個發起者 $m$ 的 $BeginBallot(b, d), b=8$ 的表決請求， $q$ 不能為其投票，這是因為 $m$ 的表決編號為8，介於5和10之間，如果投票，很可能會違背條件 $B3(eta)$ 。但是如果 $m$ 的表決編號為13（大於10），此時是可以為其投票的，因為這次投票是不會破壞條件 $B3(eta)$ 。

在步驟3中，即使與 $B3(eta)$ 的限制不相衝突， $q$ 也可以選擇不投票，這樣做不會影響法律簿的一致性，只是可能永遠也無法達成因此成功的表決。

基本協議

再來回味下初級協議實施流程，我們可以發現，每一個牧師必須在自己的記錄簿的背面記錄如下信息：

他發起的每個表決的編號：下一次表決編號需要在此基礎上遞增；
他對於其他牧師的每輪投票信息 $vote$ ，包括 $vote_{bal}, vote_{dec}$ ：因為在回復投票發起者的 $NextBallot(b, q)$ 時需要找到表決編號小於 $b$ 的最大的一次投票法令，而可能會存在多個其他牧師使用不同的表決編號同時向自己發起 $NextBallot(b,q)$ 請求，為了處理這種狀況，牧師必須要能記錄每一輪的歷史投票信息；
每輪的 $LastVote(b, v)$ 信息：它記錄了該牧師對其他發起 $NextBallot(b, q)$ 請求的牧師的一個承諾：我不會為所有 $BeginBallot(b, d)(v_{bal} < b < b)$ 請求投票。因此，牧師對其他人發起的 $BeginBallot(b,d)$ 請求處理時需要根據 $LastVote(b, v)$ 信息來判斷是否投票，而之所以記錄所有的 $LastVote$ 信息是因為可能會同時存在多個發起者同時會發起 $NextBallot$ 查詢，如下例：

發起者 $p$ 發起查詢請求 $NextBallot(12, q)$ ， $q$ 回復消息 $LastVote(12, v), v_{bal} = 10, v_{dec} = alpha$ ；
發起者 $m$ 發起查詢請求 $NextBallot(18, q)$ ， $q$ 回復消息 $LastVote(18, v), v_{bal} = 16, v_{dec} = eta$ ；
如果不記錄所有的 $LastVote$ 消息，那麼對於 $BeginBallot(11, eta)$ 和 $BeginBallot(17, alpha)$ 便無法處理了。實際上，兩個表決都是應該被拒絕的。

為了解決牧師需要在法律簿上記錄如此多繁雜信息（可能紙張都寫不下），Paxos對初級協議作了進一步約束，得到一個更實用的基本協議。在基本協議中，每個牧師必須且只需在其法律簿後面記錄如下信息：

$lastTried[p]$ ：由 $p$ 發起的最後一次表決編號，如果沒有發起，為 $- infty$ ；
$preVote[p]$ ：在 $p$ 投票的所有表決中，編號最大的投票 $vote$ ，如果 $p$ 尚未進行任何投票，那麼為 $null_p$ ，實際上，這一點與初級協議不同：初級協議要求記錄所有輪投票信息，而基本協議只記錄編號最大的投票信息；
$nextBal[p]$ ：由 $p$ 發出的所有 $LastVote(b, v)$ 投票中，編號最大的那個投票。

更少的消息記錄意味著更多的限制，基本協議和初級協議的主要區別體現在以下兩點：

初級協議允許 $p$ 並行地發起任意數量的表決，而在基本協議中，每次只允許發起一個表決，其編號為 $lastTried[p]$ 。當 $p$ 發起該表決後，他會忽略先前發起的任何其他表決的相關消息。 $p$ 在小紙片上保留編號為 $lastTried[p]$ 的表決所有信息，如果小紙片丟失，此輪表決亦停止；
在初級協議中，牧師 $p$ 發出每一個 $LastVote(b, v)$ 消息意味著其承諾不再對任何編號介於 $v_{bal}$ 和 $b$ 之間的表決進行投票。在基本協議中， $LastVote(b, v)$ 意味著更強的承諾：不再對任何編號小於 $b$ 的消息進行表決。這個更強的承諾可能會阻止一些原本在初級協議中被允許的投票。但是很明顯，基本協議不會要求 $p$ 作出違反任何初級協議的事情。還是以上面的例子說明：

發起者 $p$ 發起查詢請求 $NextBallot(12, q)$ ， $q$ 回復消息 $LastVote(12, v), v_{bal} = 10, v_{dec} = alpha$ ；
發起者 $m$ 發起查詢請求 $NextBallot(18, q)$ ， $q$ 回復消息 $LastVote(18, v), v_{bal} = 16, v_{dec} = eta$ ；
在初級協議中， $BeginBallot(14, eta)$ 是允許被投票的（14並非處於範圍 $(10, 12)$ 和 $(16, 18)$ ），但在基本協議中，由於 $14 < 18$ ，這個投票也是不被允許的。

基本協議的協議運作流程如下：

牧師 $p$ 選擇一個比 $lastTried[p]$ 大的表決編號 $b$ ，設置 $lastTried[p]=b$ ，然後發送 $NextBallot(b)$ 消息給其他牧師；
牧師 $q$ 從 $p$ 收到消息 $NextBallot(b)$ 後：如果 $b leq nextBal[q]$ ，忽略該消息；如果 $b > nextBal[q]$ ，令 $nextBal[q]=b$ ，然後發送 $LastVote(b,v)$ 消息給 $p$ ，其中 $v$ 等於 $prevVote[q]$ ;
當收到大多數( $Q$ )牧師的 $LastVote(b, v)$ 消息後，牧師 $p$ 從其中選擇所有投票編號最大的 $vote$ ，發起一次新表決 $B: B_{qrm}=Q, B_{bal}=b, B_{dec}=d(d=vote_{dec})$ ：即發送消息 $BeginBallot(b,d)$ 給 $Q$ 的所有成員；
$q$ 收到一個 $b=nextBal[q]$ 的 $BeginBallot(b,d)$ 消息後，牧師 $q$ 在編號為 $b$ 的表決中投出他的一票，設置 $prevVote[q]$ 為本次表決 $B$ ，然後發送 $Voted(b,q)$ 消息給 $p$ ， $b ot= nextBal[q]$ 的 $BeginBallot(b,d)$ 消息將被忽略;
$p$ 收到 $Q$ 中每一個 $q$ 的 $Voted(b,q)$ 消息後（這裡 $Q$ 是表決 $b$ 的法定人數集合， $b=lastTried[p]$ ），他將 $d$ （這輪表決的法令）記錄到他的律簿上，然後發送一條 $Success(d)$ 消息給每個 $q$ ；
一個牧師在接收到 $Success(d)$ 消息後，將法令 $d$ 寫到他的律簿上。

基本協議是初級協議的一個受約束版本，意味著基本協議允許的任何行為在初級協議中都是允許的。初級協議滿足一致性條件，那麼基本協議也滿足一致性條件。

完整的神會協議

雖然基本協議維護了一致性，但是沒有保證任何可進展性，因為它僅僅規定了一個牧師可以怎麼做；它沒有要求他一定要做任何事情。完整的協議和基本協議一樣包含 6 個步驟來操控一個表決。為了促成可進展性，它很直觀地要求牧師們儘可能快地執行協議的 2-6 步驟。為了滿足可進展性條件，必須要求某些牧師來執行步驟 1 來發起一輪表決。完整協議的關鍵一點是決定什麼時候一個牧師應該發起一輪表決。

永遠不發起表決肯定會阻止進展性，但是發起太多的表決同樣會阻止進展性。假設 $b$ 比任何其他表決的編號都大，牧師 $q$ 在步驟中收到一條 $NextBallot(b)$ 消息會引出一個承諾，阻止他在步驟4中對任何之前發起的表決投票（ $BeginBallot(b, (b < b)$ ）。這樣，一輪新表決的發起會阻止任何之前發起的表決成功。如果新的表決以不斷增大的編號在之前的表決有機會成功之前不斷地被發起，那麼整個表決將會沒有任何進展。

達到可進展性條件要求新的表決直到某個表決成功之後（即處理完成BeginBallot()消息後）才發起，但是不被頻繁地發起。為了開發完整協議，Paxos 人首先必須知道信使傳遞消息和牧師響應要花費多長時間。他們測定了一個沒有離開議會廳的信使，總會在4分鐘之內送出消息，一個呆在議會廳中的牧師，總會在 7 分鐘內處理消息。這樣如果 $p$ 和 $q$ 在議會廳中，這時某些事件使得 $p$ 發送一條消息給 $q$ ，並且 $q$ 響應了一個答覆給 $p$ ，那麼在沒有任何信使離開議會廳的情況下， $p$ 將在 22 分鐘之內收到這個答覆（牧師 $p$ 會在事件的7分鐘內發出消息， $q$ 將會在接下來的 4 分鐘內收到這個消息，然後在7分鐘內作出響應，答覆會在接下來的4分鐘內送達 $p$ ）。

假設只有一個牧師在發起表決，他在協議的步驟1中給每個牧師發送一條消息。如果 $p$ 在多數牧師呆在議會廳中時發起表決，那麼他可以期望在 22分鐘之內執行步驟 3，在另一個 22

分鐘之內執行步驟 5。如果他沒有能夠在這些時間內執行這些步驟：那麼或者某些牧師或信

使在 $p$ 發起這個表決後離開了議會廳，或者一個更大編號的表決已經在之前由另一個牧師發

起了。為了解決後一個可能性， $p$ 必須學習其他牧師使用的任何編號比 $lastTried[p]$ 大的表決。可以通過擴展協議以要求牧師 $q$ 收到 $p$ 的 $NextBallot(b)$ 和 $BeginBallot(b,d)$ 消息時，如果發現 $b< nextBal[q]$ ，則將 $nextBal[q]$ 發送給 $p$ 來完成這個學習。這樣牧師 $p$ 就可以發起一個更大編號的新的表決。

仍然假設 $p$ 是唯一發起表決的牧師，假定他被要求當且僅當如下條件滿足時，才發起一個新

表決：

在最近的 22 分鐘之內他沒有執行步驟3或步驟 5；
他得知另一個牧師 $q$ 已經發起了一個編號更大的表決。

如果議會廳的門在 $p$ 和過半的牧師在裡面時鎖住了，那麼一條法令會在 99 分鐘內通過並寫到議會廳中每個牧師的律簿上。（22 分鐘牧師 $p$ 啟動下一個表決，22 分鐘得知另一個牧師發起過更大編號的表決，55 分鐘完成一個成功表決的步驟 1-6）。這樣，在只有一個牧師發起表決，並且不會離開議會廳的前提下，可進展性條件將會被滿足。

完整協議因此包含一個流程來選擇一個唯一的牧師，稱作總統，來發起表決。在多數形式的政府中，選擇一個總統會是一個困難的問題。但是這種困難僅僅是因為大多數政府要求任意時候都必須有一個唯一的總統存在。例如在美國，如果某些人認為 $Bush$ 已經當選為總統，而這時另一些人認為是 $Dukakis$ ，就會造成混亂，因為其中的某個可能會決定簽署某個法案而同時另一個決定否決這個法案。但是在 Paxos 的神會中，擁有多個總統只會阻止進展性，而不會導致不一致。為了完整協議滿足可進展性條件，選擇總統的方法只需要滿足以下「總統選舉要求」：

如果沒有人進入或離開議會廳，那麼接下來的 $T$ 分鐘之內只會有一個議會廳中的牧師會
認為他自己是總統。

如果滿足了總統選舉要求，那麼完整協議將具有如下特性：

如果多數的議員在議會廳內，並且在 $T+99$ 分鐘內沒有人進出議會廳，那麼在這段時間的最後，議會廳中的每個牧師的律簿上都會記下一條法令。

完整的神會協議在基礎協議之上增加了總統選舉過程，提高了Paxos協議的可進展性。但是該協議並沒有完整說明過程如何運作。