Paxos算法被认为是类似算法中最有效的( 二 ) _Paxos算法

说明：下面以一个分布式key-value 数据库为例进行解释。每个key-value 有多个副本，如果客户端发起一个update(key,vaule) 的操作，则会产生由一个节点发起、相关节点进行响应的一次一致性操作，即选举B ，对保存了该key-value 的副本进行更新。法定人数牧师（B_qrm）是副本节点的一个大部分子集，因为有些时候某些副本不可达。B 是关于某个key-value 的一系列更新操作，不同的法律实际上是一个key-value 的不同值。那么B1-B3就好明白了， B1指的是更新操作的顺序是唯一的；B2指的是任意两次更新操作必须有共同的节点参与；B3指的是某次操作的key-value值和所有参与节点中最近一次投票的值相一致。这是因为如果某个节点在之前已经投赞成票，说明它已经确认可以修改该值，而其他法定人数中的牧师/节点还没有确认可以修改该值。
引理1.1 如果B1(B) ， B2(B)$ 和B3(B) 满足，那么对于在B中的任意B 和B’ ，有

文章插图

证明略，有兴趣的可以参考原文
定理1.2 如果B1(B) ， B2(B) 和B3(B) 满足，那么对于在B 中的任意B 和B’ ，有

文章插图

证：如果$B’_bal=B_bal 那么由B1(B) 可知B’=B。如果B’_bal 不等于 B_bal ，那么总有一个编号大、一个小，根据引理1.1 可得。
定理1.3 b>B_bal 且对于所有B 中的B 都有Q 和 B_qrm 交集不为空。有一个选举B’ 满足B’_bal=b、B’_qrm=B’_vot=Q ，那么如果B1(B)、B2(B)、B3(B)满足，则B1(B并B’)、B1(B并B’)、B1(B并B’) 也满足。
证明略，见原文。
这个定理说的是在一个选举集合B 之后的每次成功选举，只要和之前集合中每次选举都有交集，那么这些成功的选举合并选举集合B 满足一致性。
几个协议从B1-B3这些约束条件可以得到初始协议（preliminary protocol ），基础协议（basic protocol）是初始协议的限制版，满足一致性要求。完整议会协议（complete Synod protocol ）进一步限制了基础协议，满足一致性和进展需求（progress requirements），多法律议会协议（multi-decree parliament protocol）源于完整议会协议，它使得议会可以通过一系列而不仅仅是一条法律。下面具体介绍这几个协议。
初始协议
满足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 。