PDF《The Part-Time Parliament》

6 个月 的航海.他甚至可能会一去不复返,在这种情况下消息永远也不会被送达. 尽管议员和信使可以随时离开或进入, 但是只要他们在议会厅里, 他们就会专注于议会事务. 只要呆在议会厅,信使会很快速的投递消息,议员会立即快速的处理任何他们收到的消息. Paxos 的官方记录声称议员和信使绝对的诚实并严格遵循议会协议.大多数学者仅仅把这当 做将 Paxos 描绘为在道德上优越于其东方邻国的宣传.不诚实,尽管稀少,但毫无疑问一定 是存在的, 但由于官方文本里从未提及, 我们也不知道议会是怎样应付不诚实的议员或信使 的.在3.3.5 节讨论了已经发现的迹象 2. The Single-Decree Synod Paxos 议会由更早期的牧师的宗教仪式会议(Synod,以下简称神会)演化而来.这种神会每

19 年召集一次来选择一个象征性的法令.几个世纪以来,神会约定俗成地要求所有牧师都 到场来选择一个法令.但是随着商业的繁荣,牧师开始在神会期间就进进出出会议厅,最后 旧的协议失效了,一个神会没有达成任何法令就结束了.为了避免重复这种宗教上的灾难, Paxos 的宗教领袖请求数学家制定一个协议来达成神会法令.协议的要求和假定本质上与后 来的议会协议是一样的,除了一点不同:神会只允许在律簿上包含一条法令,而后来的议会 《The Part-Time Parliament》

5 可以包含一系列法令.神会协议在本章中描述,议会协议在

第三章中描述. 数学家通过几个步骤来得到神会协议. 首先他们证明了一个满足特定约束的协议能够保证一 致性,并且可以进展下去.由这些约束直接得出了一个初级协议.初级协议的一个约束版本 提供了能够保证一致性,但是不能保证进展性的基本协议(basic protocol) .通过进一步约 束基本协议得到了能够满足一致性和进展性要求的完整神会协议(synod protocol) [神会协议 的完整的发现历史已不可考.就像现代的计算机科学家,Paxos 的数学家将描述优美的逻辑 推演,描述毫不相干的算法是如何推演产生的.我们知道数学结论(2.1 节的定理

1 和2) 确实是在协议产生之前作出的. 当数学家在回复关于协议的请求, 试图证明不可能有一个满 足要求的协议时,发现了这些数学结论] 2.1 节描述了这些数学结论.2.2-2.4 节非正式地描述了这些协议.在附录中给出了基本协议 的更正式的描述和正确性证明. 2.1.数学结论 神会法令从多轮带编号的表决(ballot)中选择.一轮表决是对一个单条法令的投票. 在每次表 决中,牧师只有两种选择:对这个法令投票(表示赞成这个法令) ,或不投票(不赞成) [像 许多现代国家一样, Paxos 并没有完全领会古希腊民主的精髓] . 与一轮表决相关联的是一个 牧师的集合,称为法定人数集(quorum) .当且仅当法定人数集中的每个牧师都赞成这个法 令时,这轮表决才是成功的.正式的表述是,一轮表决B由下面

4 个要素组成: (除非特别 说明,集合指有限集合) 一条法令(被投票的那条 decree) 一个牧师的非空集合(表决的法定人数集 quorum) 一个牧师的集合(所有对法令作出投票(赞成)的牧师) 这轮表决的编号 说一轮表决B是成功的,当且仅当Bqrm Bvot,所以一轮成功的投票是每一个法定人数 集的成员都投了票的(赞成票,不赞成则不投票). 表决的编号从一个无界有序的数字集合中选取.如果 >