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 命令可以进一步减少消息传递。