majority演算法

⑴ 一致性演算法（Paxos、Raft、ZAB)

一致性演算法（Paxos、Raft、ZAB)

什麼是一致性

1、弱一致性
a、最終一致性
i、DNS（Domain Name System）
j、Gossip（Cassandra的通信協議）

以DNS為例：

2、強一致性
a、同步
b、Paxos
c、(multi-paxos)
d、ZAB(multi-paxos)

DNS 就是一種最終一致性，比如 上圖中 增加一條記錄： www.hyb.small.com , 我們從其他DNS伺服器一時會讀取不到，但是過一會就會讀取得到了。

數據不能存在單點上。
分布式系統對fault tolerence的一般解決方案是state machine replication 。

准確的來說應該是 state machine replication 的共識（consensus）演算法。

paxos其實是一個共識演算法，系統的最終一致性，不僅需要達成共識，還會取決於client的行為

主從同步復制

1、Master 接受寫請求
2、Master 復制日誌到slave
3、Master 等待，直到所有從庫返回

問題：

任何一個節點失敗，哪怕是從節點（Slave）同步失敗，都會導致整個集群不可用，雖然保證了一致性，但是可用性卻大大降低

基本想法：
a、多數派：
每次寫都保證寫入大於N/2個節點，每次讀保證從大於N/2個節點中讀。
比如5個節點，每次寫大於3個節點才算成功；讀也是大於3個節點才算成功。

b、多數派還不夠！
在並發環境下，無法保證系統正確性，順序非常重要。比如下圖的 Inc 5; Set 0; 執行順序亂了，結果就會引發錯亂。

Lesile Lamport,Latex的發明者。

為描述Paxos演算法早昌，Lamport虛擬了一個叫做Paxos的希臘城邦，這個島按照議會民主制的政治模式制定法律，但是沒有人願意將自己的全部時間和精力放在這種事上，所以無論是議員、議長或者傳遞消息的時間。

Paxos

1、Basic Paxos
2、Multi Paxos
3、Fast Paxos

強一致性演算法---Basic Paxos

角色叢睜晌介紹：

Client:系統外部角色，請求發起者。像民眾

Propser: 接滲鋒受Client 請求，向集群提出提議(propose)。並在沖突發生時，起到沖突調節的作用。像議員替民眾提出議案

Accpetor(Voter): 提議投票和接收者，只有在形成法定人數(Quorum,一般即為majority 多數派)時，提議才會最終接受，像國會。

Learner:提議接受者，backup，備份，對集群一致性沒什麼影響，像記錄員；

步驟、階段(phases):
1、Phase 1a:Prepare
proposer 提出一個提案，編號為N，此N 大於這個proposer之前提出提案編號，向acceptors請求同意，要求有quorum接受的才行。

2、Phase 1b:Promise
N 必須大於此acceptor之前接受的任何提案編號，才會接受，否則會拒絕。

3、Phase 2a: Accept
如果達到了多數派，proposer會發出accept請求，此請求包含提案編號N ,以及提案內容。

4、Phase 2b:Accepted
如果此acceptor在此期間沒有收到任何編號大於N的提案，則接受此提案內容，否則忽略。

流程圖如下：

操作步驟如下：
Request;
Prepare(1);
Promise(1,{Va,Vb,Vc});
Accept(1,Vn)
Accepted(1,Vn);
Response;

1、Acceptor部分節點失敗，但達到了Quoroms，此時仍然會成功。

如果有一個Acceptor因為各種原因掛掉了，3個Acceptors變成了2個Acceptors，還是滿足>n/2 的要求，所以還是會成功。

2、Proposer失敗，上一次記錄不會被寫入Proposer表，然後重新開啟一個新的Proposer，來替代上次的Proposer來處理未完成請求，此時編號已經增加為2，也就是Prepare(2)

Basic Paxos when an Proposer fails
如果Proposer 在發送了一條Accept消息之後，但是還沒收到Accepted消息之前就掛掉了，只有一個Acceptor接收到了Accept消息。那麼整個Paxos協議就沒法進行下去了，這時一個新的Leader（Proposer）會被選舉出來，重新開始一輪新的共識。

Basic Paxos潛在的問題是：活鎖（liveness）或eling

Basic Paxos很有可能出現這種情況：
1、議員A(proposer A)說我們來討論提案1，大部分議員說：「好，我們來討論提案1」；
2、但是此時議員A還沒有說內容是什麼，這時候又來了一個議員B，又來說：「我們來討論提案2」；這時候大部分還沒有接受提案1，提案2的編號是大於提案1的，這時候大部分還沒有接受議案2；
3、這時候議員A以為網路斷了，然後把編號改下，內容不變然後提出議案3；然後議案4、議案5....
這樣就形成了活鎖。
解決活鎖的方法是用Random的timeout，當兩個沖突的時候用一個隨機的等待時間；當自己提議未生效時，再發起提議等待幾秒。

Basic-Paxos是一個無限循環的2PC，1條日誌的確認至少需要2個RTT + 2次落盤（1次是prepare的廣播與回復，1次是accept的廣播與回復）。

Basic Paxos when multiple Proposers conflict
最後再描述一個最復雜的情況，即有多個Proposers認為他們是Leaders，並不斷的發送Prepare請求。為什麼會有多個Leaders呢？ 有可能一個Proposer當了一段時間Leader之後掛掉了，新的Proposer被選為Leader繼續新的一輪共識。後面掛掉的Proposer又恢復了，它認為自己還是Leader，所以繼續發送Prepare請求。

Basic Paxos的問題
難實現（角色太多）、效率低（2輪RPC）、活鎖問題

Multi Paxos:
新概念，Leader;唯一的propser，所有請求都需經過此Leader;

只有一個Proposer，沒有第二個Proposer； 這個Proposer就是Leader,沒人跟他搶;

再者分布式系統必須串列執行所有提議，否則就會出現前面說的順序問題。

--------First Request(第一次執行)----------
Request
Prepare(N) //選Leader
Promise(N,I,{Va,Vb,Vc})
Accept!(N,I,Vm)
Accepted(N,I,Vm)
Response;

--------Following Request(第二次或者以後)----------
Request
Accept!(N,I,Vm)
Accepted(N,I,Vm)
Response;

第二次或者以後，就不用再選Leader了 直接執行Request 請求，由Leader 發出議案。
如果Leader 掛了 就選下一個總統Leader(N+1)

減少角色，進一步簡化，在Basic-Paxos中我們區分了很多角色，有Clients、Proposers、Acceptors、 Learners，實際上Proposers、Acceptors 、Leanrners可以合並成一個，統稱為Server，下面是合並之後的序列圖。

Multi-Paxos when roles are collapsed and the leader is steady
同樣的，當Leader很穩定的時候，我們可以在接下來的執行中忽略Phase 1. 如下圖所示：

Raft
1、劃分三個子問題
a、Leader Election
b、Log Replication
c、Safely
2、重定義角色
a、Leader
b、Follower
c、Candidate

原理動畫解釋： http://thesecretlivesofdata.com/raft
場景測試： https://raft.github.io

Raft 是比 Multi Paxos 還要簡單的一個版本
一致性並不代表完全正確性！三個可能結果：成功，失敗，unknown

詳細內容參考：
https://www.jianshu.com/p/6cd41fe0b8f6

強一致性演算法--ZAB
基本與raft相同。在一些名詞的叫法上有些區別：如ZAB將某一個leader的周期稱為epoch，而raft則稱為term。實現上也有些許不同：如raft保證日誌連續性，心跳方向為leader至follower，ZAB則相反。

⑵ 拜占庭將軍問題的解決演算法

拜占庭問題的最初描述是：n 個將軍被分隔在不同的地方，忠誠的將軍希望通過某種協議達成某個命令的一致（比如一起進攻或者一起後退）。但其中一些背叛的將軍會通過發送錯誤的消息阻撓忠誠的將軍達成命令上的一致。Lamport 證明了在將軍總數大於3m ，背叛者為m 或者更少時，忠誠的將軍可以達成命令上的一致。
為了保證上面的需求，必須滿足下面兩個條件：
1. 每兩個忠誠的將軍必須收到相同的值 v(i)（v(i)是第i 個將軍的命令）
2. 如果第i 個將軍是忠誠的，那麼他發送的命令和每個忠誠將軍收到的v(i)相同
為了簡化以上模型，我們使用一個將軍發送命令給多個副官的形式來證明，發送命令的將軍稱為發令者，接收命令的將軍為副官，那麼上面的兩個條件可以表述為：
IC1. 所有忠誠的副官遵守相同的命令
IC2. 如果發出命令的將軍是忠誠的，那麼所有忠誠的副官遵守司令（發出命令的將軍）的命令
特別提示：發送命令的每次只有一個將軍，將其命令發送給n-1 個副官。m 代表叛國者的個數，因為將軍總數為n，所以副官總數為n-1 個。IC2 中副官遵守實際上是指忠誠的將軍能夠正確收到忠誠將軍的命令消息。 通過口頭消息傳遞達到一致，如果有m 個叛國將軍，則將軍們的總數必須為3m+1 個以上。下面是口頭消息傳遞過程中默認的一些條件：
A1. 每個被發送的消息都能夠被正確的投遞
A2. 信息接收者知道是誰發送的消息
A3. 能夠知道缺少的消息
A1 和A2 假設了兩個將軍之間通信沒有干擾，既不會有背叛者阻礙消息的發送（截斷）也不會有背叛者偽造消息的情況（偽造）。即是每個將軍都可以無誤地將自己的消息發送給其他每個將軍。（下一節中可以不需要這個必要條件）
我們定義口頭消息演算法OM(m) 。對於所有的非負整數m ，每個發令者通過OM(M) 演算法發送命令給n-1 個副官。下面將說明OM(m) 演算法在最多有m 個背叛者且總將軍數為3m+1 或者更多的情況下可以解決拜占庭將軍問題。（考慮到網路應用實際環境，原文使用了收到值代替收到命令，本文不做修改）
演算法定義一個函數：majority(com1,com2,…,comn)等於多數派命令。
OM(0)演算法
（1）發令者將他的命令發送給每個副官。
（2）每個副官採用他從發令者得到的命令，或者默認使用撤退命令，如果沒有收到任何命令。
OM(m)演算法
（1）發令者將他的命令發送給每個副官。
（2）對於每個i ，vi 是每個副官i 從發令者收到的命令，如果沒有收到命令則為撤退命令。副官i 在OM(m-1) 中作為發令者將vi 發送給另外n-2 個副官。
（3）對於每個i，並且j eq i，vj 是副官i 從第（2）步中的副官j 發送過來的命令（使用OM(m-1)演算法），如果沒有收到第（2）步中的副官j 的命令則默認為撤退命令。最後副官i 使用majority(v1,…,vn-1)得到命令。
接下來實際的考慮一個n=4，m=1 的情況：
1. 當副官D是背叛者
第一步發令者A執行演算法OM(1)將自己的命令發送給三個副官B，C，D，三個副官都正確地收到了命令。
第二步每個收到命令的副官都作為發令者執行演算法OM(0)，將自己收到的命令轉發給其餘副官，因為副官D是背叛者，所以他給副官B和C傳遞的消息可能會是假消息。副官B和C分別根據majority 函數來決定命令。
這樣背叛的副官D 同理也干擾不了發令者的決定。下面看看如果發令者是背叛者。
2. 發令者是背叛者，其餘副官為忠誠的
第一步：發令者A向副官B，C，D發送了不同的命令，實際情況中是一個攻擊者向不同方發送了不一致的值（例如，0或1）企圖擾亂副官做出一致決定。
第二步：副官收到命令後，搖身一變為發令者執行OM(0) 向所有的副官發送命令，每個副官通過多數表決演算法仍可以達成一致的命令。
文章接著就證明了OM(m)演算法對任意m 都是可以滿足，首先引入一個引理（歸納法證明）：
引理1：對於任意m 和k ，如果有超過2k+m 個將軍和最多k 個背叛者，那麼演算法OM(m) 滿足IC2 （回顧下IC2 指的是，如果將軍是忠誠的，所有的副官遵守將軍命令）。
證明：當m=0 的時候，OM(0) 在將軍是忠誠的時候滿足IC2。當m>0 時，首先將軍將命令傳遞給 n-1 個副官，然後每個副官對n-1 個將軍執行OM(m-1) 演算法。因為假設了n>2k+m（引理中有將軍數大於2k+m），所以 n-1 > 2k+(m-1) >= 2k（即每一輪中副官總數不小於背叛者的兩倍），這樣每輪OM(m-k) 演算法中忠誠的副官收到的命令都是majority(v1,v2,...,v(n-1))，其中忠誠副官發送的命令大於或者等於一半。
接著解決拜占庭將軍問題。
定理1：對於任意m，如果有超過3m 個將軍和最多m 個背叛者，演算法OM(m) 滿足條件IC1 和條件IC2。
證明：通過m 的歸納法證明，我們通過假設OM(m-1) 成立來證明OM(m) m>0。首先考慮發送命令的將軍是忠誠的。那麼將引理中k 設為m 則OM(m) 滿足IC2 ，IC1 在發令將軍是忠誠的情況下也滿足。
接著考慮m 個背叛者中有一個是發令者，那最多就只有m-1 個副官是背叛者了，又因為有3m 個將軍，所以副官的總數超過3m-1，且有3m-1>3(m-1) 。因此通過歸納法假設 OM(m-1) 滿足IC1 和IC2（最多3(m-1) 個將軍和最多m-1 個背叛者）。那麼任意兩個忠誠的副官j 在OM(m-1) 獲得相同命令vj，那麼在OM(m) 演算法中每個忠誠的副官都會收到(v1,v2,...,v(n-1))，可知滿足條件IC1 和IC2。
看完這段證明其實我也挺糊塗的~~~~，畫了張圖來看看lamport 是怎麼證明的：
簽名消息在除了滿足口頭消息A1-A3 三點要求外還應該滿足下面A4：
A4 （a）簽名不可被偽造，一旦被篡改即可發現
（b）任何人都可以驗證將軍簽名的可靠性
下面定義一個類似於上面majority() 函數的choice() 來決定副官的選擇：1.當集合V 只包含了一個元素v ，那麼choice(V)=v ；2. choice(o)=RETREAT。
有了上面A4 和choice() 基礎我們給出SM(m) 方法：
SM(m) 演算法
初始化Vi=空集合
（1）將軍簽署命令並發給每個副官
（2）對於每個副官i ：
（A）如果副官i 從發令者收到v:0 的消息，且還沒有收到其他命令序列，那麼：
（i）使Vi 為{v}
（ii）發送v:0:i 給其他所有副官
（B）如果副官i 收到消息v:0:j1:...:jk 且v 不在集合Vi 中則
（i）添加v 到Vi
（ii）如果k<m ，那麼發送v:0:j1:...:jk:i 給每個不在j1,..,jk 中的副官
（3）對於每個副官i ，當不再收到消息，則遵守命令choive(Vi)
演算法的幾點說明：
演算法第三步並沒有說明副官如何判斷沒有新的消息，可以通過兩個解決方法：一是要求每個副官收到消息後要麼簽名轉發該消息，要麼發送一個通知他將不發送這個消息；二是設置一個超時時間，如果在該時間段還沒有收到消息，則認為不再收到消息。
演算法SM(m) 中，讓副官簽名是確認其收到了該消息（有點像來了份文件給每個領導批閱）。在SM(1) 中副官收到消息就不用簽字了，因為不用轉發給其他副官。
定理2：對於任意m，最多隻有m 個背叛者情況下，演算法SM(m) 解決拜占庭將軍問題
Proof：首先證明IC2，如果發令者是忠誠的，那麼所有的副官一定收到相同的命令，因為簽名無法篡改，且IC1 也就滿足了。證明IC1 只用考慮發令者是背叛者的情況（重新回顧下IC1 是指所有忠誠的副官執行相同的命令），IC1 要求兩個忠誠的副官（i，j）必須收到相同的命令集合Vi、Vj，也就是Vi 中每個v 都在Vj 中。會存在兩種情況，其一當副官i 收到v 命令的序列後，加入到Vi，並將其發送給副官j ，j 將命令v 保存；其二副官i 收到命令v:0:j1:...:jk:i，其中有jr=j，所以 由A4 可知副官j 也收到了該命令。如果沒有，則有：
k<m。這種情況下，i 發送信息v:0:j1:...:jk:i 給副官j ，那麼j 一定收到v 。（這點感覺和上面有重復）
k=m。發令者是背叛者，最多隻有m-1 個副官是背叛者。因此，最少有一個序列j1,...,jm是忠誠的。那麼j 一定收到這個忠誠的副官序列發來的值v ，所以副官j 收到v 。
證明完畢。

⑶ Paxos 演算法的幾種演算法

上面通過證明如果一個協議滿足B1-B3 約束條件，那麼就可以保證一致性。直接從這些約束得到preliminary protocol ，basic protocol 是preliminary protocol 的限製版，保證了一致性。complete Synod protocol 進一步限制了basic protocol ，滿足一致性和過程需求（progress requirements）。下面將這三個演算法的具體過程。 滿足B1，牧師發起選舉的編號必須滿足偏序關系，有一個方法是每個發起牧師使用遞增的數值作為選舉編號，但這樣牧師無法立即知道他們選的數值有沒有被其他牧師選作選舉編號已經被使用。還有一個方法是使用數字+牧師姓名作為選舉編號，這樣就避免了自己的選舉編號被其他牧師使用。
滿足B2，每次選舉的法定人數必須是一個大部分集合（majority set）Q，這樣任意兩個選舉都會有一個共同的牧師。這里大部分集合是一個靈活的選擇，在原文中Lamport 使用體重打比方，體重的人更有可能呆在議會大廳，這樣就可以使用體重超過一半的牧師集合作為大部分集合。至於實際情況中的大部分集合是什麼要看具體情況了。
滿足B3，要求每個牧師p 每次在發起選舉前必須找到B_qrm 中每個牧師q 的MaxVote(b,q,B)。
根據以上要求，可以得到初始協議：
1. 牧師p 選擇一個選舉編號b ，並發送NextBallot(b)送給其他牧師
2. 其他牧師q 在收到NextBallot(b) 後，返回LastVote(b,v) 給牧師p，v=MaxVote(b,q,B)$是小於b 編號的q 投的最大的贊成票。為了保證B3，q 不能在b 和b_bal 之間的選舉投贊成票。（如果q 在發送了LastVote(b,v)又對新的選舉投票了那麼v 也就不是q 投的最大贊成票）
3. 牧師p 從一個大部分集合Q 中每個牧師q 中都收到LastVote(b,v) 後，發起一個新的選舉，編號為b，法定人數為Q，法律d滿足B3。然後牧師p 將這個法律寫在自己賬目的背面，發送BeginBallot(b,d)給Q 中每個牧師。
4. 牧師q 收到BeginBallot(b,d) 後決定是否為這次選舉投贊成票，如果贊同，則他將發送Vote(b,q) 給牧師p。
5. 如果牧師p 收到Q 中每個牧師q 發來的贊成票Vote(b,q)，則將法律d 寫入他的賬目中，並向所有q發送Success(d) 消息。
6. 收到Success(d) 消息後，牧師q 將法律d 寫入到自己的賬目中。
說明：第一步表示發起法律的牧師p 希望下一個選舉的編號是b 。牧師q 用LastVote(b,v) 回應了牧師p 的請求，也就是向牧師p 通過法律時保證了v=MaxVote(b,q,B) 的被改變，具體來說就是不在b 和b_bal 之間的選舉投贊成票。
第三步要求法律d 需要滿足B3，這里我開始有點迷糊，實際系統中的值是客戶端決定的，而不應該是B3 決定的。這里我們還是用上面的key-value 資料庫的例子來理清下思路：當某個節點/牧師第一次發起更新前相當於B為空集，發起更新/選舉的操作不斷進行，直至所有法定人數（quorum）都對法律投了贊成票（即majority set 的節點都更新了該key-value 的值則認為更新成功），B3對應的就是之前的更新沒有成功，那麼新的選舉值需要保持的情況。第四步允許牧師可以不發送Vote(b,q) 或者發送幾次，對應的是發送的信息可能因為通信而失敗而未發送或者被多次發送。一旦牧師投了贊成票則確認可以修改該值。
考慮到最後第六步法律d 才被牧師q 寫入到賬目，有可能出現的情況就是在第五步的時候牧師p 將法律寫入到了自己賬目中，接著發送Success(d) 給其他牧師，其中因為通信或者牧師離開議會大廳而沒有被寫入到自己的賬目中，導致不一致。所以真正寫入到賬目時機應該是在第四步牧師q 在發送給牧師p 贊成票的同時就法律寫入到了各自賬目中。而不用考慮如何保證牧師q 第四步寫入的法律會導致不一致，因為法律如果沒有通過則還有更多的選舉來保證一致性。後面也談到了當法律第一次別寫入到賬目中算通過法律。 初始協議（Preliminary Protocol）要求每個牧師都保存 (i) 他發起的每個選舉； (ii) 他投的每個贊成票； (iii) 他發送的每個$LastVote$。為了簡化牧師需要保存的數據，我們對上面的協議做一個限制，得到基礎（Basic Protocol）協議。首先介紹三個新的參數：
lastTried[p] 牧師p 發起的最後一個選舉
prevVote[p] 牧師p 最近一次的投票
nextBal[p] 收到的選舉編號的b 的最大值，即牧師p參加的最大選舉編號
在初始協議中，每個牧師可以同時發起任意個選舉，在基礎協議中要求每個牧師只能發起一個選舉lastTried[p]，一旦發起一個選舉，那麼之前發起選舉的信息就都不重要了。在初始協議中要求每個牧師不能在b_bal 和b 之間投贊成票，在基礎協議中則更嚴格地要求不能給小於b 的選舉投贊成票。那麼基礎協議可以概述為下面幾步：
1. 牧師p 選擇一個大於lastTried[p] 的選舉編號b ，發送NextBallot(b)給其他牧師
2. 牧師q 收到NextBallot(b) 且b>nextBal[q]後設置nextBal[q]=b ，接著發送LastVote(b,v) 給牧師p，其中v==prevBa[q] 。（如果b 小於或等於nextBal[q]，則不回復）
3. 從滿足某個大部分集合Q 中每個牧師收到了LastVote(b,v) 信息，牧師p 發起一個編號為b ，法定人數為Q ，法律為d（滿足B3 ）的選舉，並將BeginBallot(b,d) 發送給Q 中每個牧師。（如果沒有滿足任意大部分集合Q 的牧師返回，則返回第一步）
4. 牧師q 收到BeginBallot(b,d) ，決定投贊成票，設置prevVote[p] 為這次投票，並發送Vote(b,q) 給牧師p。（如果在收到BeginBallot(b,d) 後發現b 不等於nextBal[q] 則忽略這條信息，說明這期間牧師q 還收到了其他的編號更大的選舉）
5. 牧師p 從大部分集合Q 中每個牧師q 收到了Voted(b,d) ，且b==lastTried[p] ，則認為這次選舉成功，將法律d 記錄在賬目中，並向Q 中每個牧師q 發功成功消息Success(d) 。
6. 每個牧師q 收到Success(d) 消息後將法律寫入賬目。
基礎協議是初始協議的限製版，因為兩者都對牧師沒有行為要求，所以也不保證過程（QS）。下面介紹一個保證過程的協議— 完整議會協議（complete Synode protocol）。 基礎協議保證了一致性卻沒有保證任何過程，因為它只闡述了牧師可能做什麼，沒有要求牧師應該做什麼。為了達到之前談到的過程需求（Qrogress Requirements），我們需要添加一些額外的要求使得牧師們盡快執行完2-6 步。
考慮一種情況如果牧師q 第二步收到的選舉編號b 都比之前收到的要大，那麼他就要放棄之前收到的所有選舉。可是在選舉編號為b 的選舉在未確認前，可能又會收到更大編號的選舉b』 ，這樣就無法通過任何法律，過程也不能保證。所以為了達到過程需求則需要一個選舉成功後再發起另一個選舉。而首先應該知道服務員傳遞消息和牧師處理消息的時間，在網路中常常通過設置timeout 來實現，同樣的如果超過了一定時間牧師沒有收到服務員的回復，則認為該服務員或者對應的牧師離開了議會大廳。
假設牧師執行一個動作在7 分鍾以內，服務員傳遞一個消息在4 分鍾以內，那麼一個牧師p 發送消息給牧師q ，希望其回復的時間應該是在22 分鍾內（7+4+7+4 分鍾）。
有了上面時間的假設，再考慮上面討論過的情況，如果發起選舉的牧師p 會在第二步和第四步期望22 分鍾內收到其他牧師的回復，如果沒有則可能是一些牧師或者服務員離開了議會大廳，或者還有一些牧師發起了編號更大的選舉。遇到這兩種情況都牧師p 應該終止本次選舉，而重新開始發起一個新的選舉，為了不至於新發起的選舉編號還是太小而仍不能執行，需要從其他牧師哪裡獲取最新的選舉編號，從而選取一個更大的編號發起選舉。
進而假設牧師p 是唯一能夠發起選舉的牧師且議會大廳內有大部分集合的牧師，那麼可以保證在99分鍾內通過一條法律：22 分鍾內發現了有更大編號的法律，22 分鍾內獲取最大編號並選擇個更大的編號，55 分鍾內完成1-6 步完成一次成功的選舉（疑問：既然只有牧師p 能夠發起選舉，那麼編號都是由其控制的，前兩步發現並選擇更大的編號似乎就沒有必要了。答：並不是所有的選舉都是president發起的，其他牧師發起選舉，president向其他希望發起選舉的牧師配發選舉編號）。從上面的過程我們發現完整議會協議需要一個選舉president的過程，president的選舉演算法不是文章重點，所以文章中僅用T 分鍾代替了選舉president的時間，這樣T+99 分鍾內可以通過一部法律。
文中選擇president的方法是誰的姓在字母表中最後，並將自己的姓發送給議會大廳內所有牧師，如果在T-11 分鍾內某個牧師沒有收到比自己姓在字母表中更靠後的姓，則認為自己是president（我覺得廣播體重也應該不錯，不是說體重更重的呆在議會大廳會更久么？^_^）。還有一個細節：在選舉president的時候每個牧師p 需要將自己的lastTried[p] 發送給其他牧師，以使得president能夠在第一次選舉時選擇一個足夠大的編號。
至此，通過選舉president和設置超時，完整議會協議就可以保證過程了。
多法律國會協議
上節的議會協議（complete Synod protocol）中，president被選舉出來後，每個希望發起選舉的牧師通知他，president給牧師配發選舉編號，每次僅通過一部法律。多法律國會協議（The Multi-Decree Parliment）選擇一個president通過一系列法律，且只需要執行前兩步一次即可。
具體方法是president第一步發送NextBallot(b,n) 代替NextBallot(b) ，表示希望通過n-b 之間的所有的法律，在president 的賬目上，編號n 之前的法律都是連續記錄了的，b>n 。其他牧師q 收到消息後將每部已經出現在其賬目中編號大於$n$的法律都返回給president，不在賬目上的返回正常的LastVote 信息。
下面談到多法律國會協議有關性質，首先是法律的順序，不同法律編號的選舉同時進行，發起選舉的每個牧師都認為自己是president（不知道president 是怎麼選舉出來的，也不知道法律通過的順序）。在完整議會協議第三步中法律被提議，第一次寫入到賬目上時稱法律被通過。當一個president需要提出新的法案時，他必須從大部分集合牧師中學習到那麼法律他們都投了贊成票，每部法律都被大部分集合牧師中至少一個牧師投了票，所以president發起新的選舉前總能學到所有之前通過了的法律。president不會在空缺的法律編號內填補重要的法律。，也不會亂序提議法律，所以協議滿足「法律有序性」：如果法律A 和法律B 都是重要的法律，法律A 在法律B 提議之前通過，那麼法律A 有比法律B 更低的法律編號。第二點屬性是president在選舉出後且沒有人再進出議會大廳，法律是按照下面步驟不斷通過的（對應完整議會協議的3-5步）：
3. president 向一個法定人數牧師中每個牧師發送BeginBallot ；
4.每個牧師向president 發送Voted 信息。
5.president向每個牧師發送Success 消息。這樣通過每部法律只需要三次消息傳遞，通過合並BeginBallot 和Success 命令可以進一步減少消息傳遞。