PDF《The Part-Time Parliament》

, 则说 比B大.但这并 不能表明表决进行的顺序.一个大的表决实际上可以在一个小的表决之前发生. (这里故意 将later 翻译成了大,省得 later 和before 掺杂不清) Paxos 的数学家在一个由多轮表决构成的集合 上定义了

3 个条件,然后展示了如果已经进 行过的表决满足这些条件,那么一致性会得到保证,进行性也是可能的.头两个条件比较简 单,可以被非正式的描述如下: B1( ): 中的每一轮表决,都有一个唯一的编号 B2( ): 中任意两轮表决的法定人数集中,至少有一个公共的牧师成员 《The Part-Time Parliament》

6 第三个条件更复杂一些.在一个 Paxos 人的手稿中包含了如下内容,比较绕,描述了这个条 件: B3( ):对于 中每一轮表决B,如果B的法定人数集中的任何一个牧师在 中一个更小 轮的表决中投过(赞成)票, 那么B的法令与所有这些更小轮表决中的最大的那次表决的 法令相同 图1的手稿帮助诠释了这一段隐晦的文本.手稿画出了

5 个牧师 A、B、 、 和E的5轮投 票来阐明条件 B3( )的含义.5 轮表决组成了集合 ,对于其中的每轮表决,投了票的牧师集 合是定额集合牧师的子集,投了票的牧师被方框圈起来.例如,第14 轮表决的法令是 , 定额集合包含

3 位牧师和两个投票者. 条件 B3( )有这样的形式: 对于中 的每一个 B: ... , 这里 … 是一个限制在表决 B 上的条件.图1中5个表决的条件描述如下: # 法令 法定人数集和投票 Α Β Γ Γ Δ

2 α * * * √ 缺席

5 β * * √ 缺席 *

14 α 缺席 √ 缺席 * √

27 β √ 缺席 √ √ 缺席

29 β 缺席 √ * * 缺席 图1:Paxos 手稿展示了五轮表决组成的集合 ,满足条件 B1( )- B3( )(加上了说明性的列头) 2. 编号为

2 的表决是最小(早)的表决,从而这轮投票的条件也都满足 5. 编号为

5 的表决中没有牧师在更小号的投票中投过票,所以这轮的条件也平凡的满足 14.这轮表决的定额集合中,唯一一个在更小编号的表决中投过票的牧师是 ,他在编号为

2 的表决中投了票,所以要求这轮的法令和

2 的法令必须相等(成立) 27. (这是一次成功的表决)27 轮表决的定额集合是 A、 、 .牧师 A 没有在更小号的表决 中投过票. 投过票的小编号表决只有 5, 投过票的小编号表决只有 2;

这两个更小编 号表决中最大的是 5,所以条件要求本轮的 法令和

5 的法令相同. (成立) 29.本论的定额集合是 B、 、 .B 投过票的小编号表决只有 14, 是5和27, 是2和27. 这4个小编号表决中最大的一个是 27,所以条件要求

29 的法令和

27 的法令相同 正式的表述 B1( )- B3( )需要更多的符号标记.我们用符号 v 表示一个投票,那么 v 包含

3 个组成部分:投票的牧师 ,本论表决的编号 ,和所表决的法令 .Paxos 人同时定 义了 = -∞, =BLANK 的投票 v 为null 投票. 对于 -∞<

b <

∞的所有编号为 b 的表决, 不会以 BLANK 作为法令.对于任意牧师 p,他们定义了 作为唯一的 null 投票 v, =p Paxos 数学家为所有投票定义了一个全局顺序,........