(美丽的Paxos小岛，希腊。图片来源于网络)

本篇看点：兰伯特的论文为什么用了近10年才得以发表？中本聪对拜占庭将军问题给出了怎样的解法？

前情回顾：
【连载】比特币史话 | 拜占庭将军(2)
【连载】比特币史话 | 拜占庭将军(3)
【连载】比特币史话 | 拜占庭将军(4)

正文：
就在埃里克·布鲁尔(Eric Brewer)提出CAP理论假设的那个1998年的春天，拜占庭将军问题的提出者，美国计算机科学家莱斯利·兰伯特(Leslie Lamport)——拜占庭将军问题的提出者，发表了另一篇著名的论文，《兼职议会》(The Part-Time Parliment)[1]。[公众号:刘教链]
在这篇论文中，他提出了一种算法，可以在任意数量节点失败(非拜占庭式的失败)的情况下，令分布式数据库保持一致性。[公众号:刘教链]
由于在拜占庭将军问题上讲故事取得的成功经验，这一次兰伯特决定为这个算法起一个美丽的名字——Paxos，一个风景如画的希腊小岛。在这个小岛上有一个议会，他们对公共事务通过相互投票来达成一致。[公众号:刘教链]
可是这一次，兰伯特的浪漫主义碰了个钉子。[公众号:刘教链]
据他本人的讲述，他的论文早在1990年就递交给编辑部了。但是编辑部不喜欢Paxos这个故事，于是回信要求他删掉故事，只保留理论内容。兰伯特很恼火，觉得这帮人太缺乏幽默细胞了，愤而撤稿。[公众号:刘教链]
过了好多年，经过其他计算机科学家重述他的论文工作，论文才在1998年被最终接受并发表。[公众号:刘教链]
这个将近10年的冷板凳让兰伯特也不禁有所反思。他回忆道，“我在主题中插入一些幽默的尝试是一次令人沮丧的失败”。[公众号:刘教链]
据他记述，听他讲座的人都记住了童话故事而不是他的算法；甚至在他把论文发给几个学者，包括MIT的南希·林奇(Nancy Lynch)，一个月之后问他们，没有一个人想起来他的算法[2]。[公众号:刘教链]
这篇难产的论文，已经成为了计算机科学史上广为流传的一则趣事。[公众号:刘教链]
作为对1985年FLP不可能定理的回应，Paxos算法证明了，分布式数据库可以有办法保持较强的一致性，实现较高的访问性能。此时，可用性会被妥协(不过这时候CAP定理还没有被提出和证明呢)，也就是有可能会陷入死锁而变得不可用，但是，通过适当的控制，可以把死锁的可能性降到最低。[公众号:刘教链]
Paxos算法可用场景的最大限制就是，它只适用于节点中没有恶意节点，并且数量预先确定(以便于知道几个节点能算多数同意)的和平、稳定的网络环境。非恶意节点只有正常工作和不能正常工作（失去响应）两种情况，而不会主动造假、发假消息欺诈其他节点。当机节点数量也不能超过总数的一半，否则算法也无法取得多数表决结果，从而无法达成一致。[公众号:刘教链]
一个隐藏的问题是，Paxos算法中每一轮的询问和商讨，需要一个全局不冲突、单调有序的序列号发生。这个序列号发生及其有序性(按照时间先后有序)，实质上是由中心权威决定的，而不是系统自决的。[公众号:刘教链]
另一个隐藏的问题是，如何引入可验证的全局随机性，以便公平决定领导节点，打破争议时的死循环，Paxos算法的应对措施本质上是回避了这个问题。[公众号:刘教链]
可见，与比特币需要同时做到兼容恶意节点、非恶意节点可以随意离线、数量未知、身份未知、系统自决全局事件先后顺序、自决全局可验证随机性这些要求比起来，Paxos算法所面对的问题场景具备的条件，简直不要好太多！[公众号:刘教链]
也正是引入了诸多限制和善意假设，Paxos算法才可以达到数亿TPS。当然，Paxos算法中节点间协商需要产生O(n)的通信开销，而整个系统的性能会被多数节点的响应性所决定，节点越多、分布越远，性能越差。[公众号:刘教链]
而比特币网络是拜占庭环境，节点间没有协商、不能协商也不需要协商，也就消除了节点间通信开销。节点可以从网络中隐身，只在出块时把新区块及工作量证明抛出来即可。[公众号:刘教链]
所有这些比特币克服的问题，内生时间问题、可验证全局随机性问题、通信开销问题等，共同建构了比特币在十万节点规模的拜占庭环境下实现去中心化共识的坚实基础。[公众号:刘教链]
中本聪在2008年11月13日的邮件中写道，“工作量证明链就是拜占庭将军问题的解”，“工作量证明链是所有的同步性问题、分布式数据库问题以及全局视图问题的解决方法”[3]。[公众号:刘教链]
必须指出的是，区块链并不能解决拜占庭将军问题，工作量证明链才能——因为前者不含时间之矢，只是一个空间意义上的数据结构，而后者则具有内生的时间之矢。[公众号:刘教链]

【未完待续】(公众号：刘教链)