Consensus

Paxos paxos Paxos (Greek: Παξοί, pronounced Paksi in English ) 又名Paxi是希腊西南部一个风景如画的小岛。而Paxos算法则是现在很火的分布式一致性算法,为何以一个希腊小岛名字算法？Lamport这样解释道: I thought, and still think, that Paxos is an important algorithm. Inspired by my success at popularizing the consensus problem by describing it with Byzantine generals, I decided to cast the algorithm in terms of a parliament on an ancient Greek island. Leo Guibas suggested the name Paxos for the island. 为描述 Paxos 算法,Lamport 虚拟了一个叫做 Paxos 的希腊城邦,这个岛按照议会民主制的政治模式制订法律,但是没有人愿意将自己的全部时间和精力放在这种事情上。所以无论是议员,议长或者传递纸条的服务员都不能承诺别人需要时一定会出现,也无法承诺批准决议或者传递消息的时间。但是这里假设没有拜占庭将军问题 (Byzantine failure,即虽然有可能一个消息被传递了两次,但是绝对不会出现错误的消息) ；只要等待足够的时间,消息就会被传到。另外,Paxos 岛上的议员是不会反对其他议员提出的决议的[1]。 ...

接触区块链，多少会听到「某某算法解决了拜占庭将军问题」。它其实是分布式系统一致性（distributed consensus）领域一个很经典的抽象问题，由 Leslie Lamport（2013 年图灵奖得主，分布式系统领域奠基人之一，逻辑时钟、Paxos、LaTeX 的作者）与 Robert Shostak、Marshall Pease 在 1982 年的论文 《The Byzantine Generals Problem》 中提出。 什么是拜占庭将军问题 它也被叫作「拜占庭容错问题」。用一个比喻来描述： 拜占庭帝国派出 10 支军队去包围一个敌人。这个敌人能抵御 5 支常规军队的同时袭击，所以至少要有 6 支军队（过半）同时进攻才能取胜。这些军队分散在敌国四周，只能靠通信兵骑马互相传递消息来约定「进攻意向」和「进攻时间」。 麻烦在于：将军中可能有叛徒。叛徒会擅自篡改进攻意向或时间。那么，在可能存在叛徒的情况下，忠诚的将军们要如何达成一致、保证有多于 6 支军队在同一时间发起进攻？ 需要注意，这个问题里假定信道本身是可靠的（消息不会丢失、不会被截获）。至于「在可能丢消息的不可靠信道上，靠消息传递达成一致是不可能的」，那是另一个经典结论——两将军问题（Two Generals’ Problem），由 Akkoyunlu 等人在 1975 年提出并证明无解、Jim Gray 1978 年将其命名，是第一个被证明无解的计算机通信问题。它常被误记为 Lamport 的成果，其实和拜占庭将军问题是两回事：前者讲「信道不可靠」，后者讲「节点会作恶」。所以拜占庭将军问题把信道问题排除在外，焦点放在「节点（将军）本身可能作恶」上。 问题分析 先看没有叛徒的情况：将军 A 提一个进攻提议（「明天下午 1 点进攻，你加入吗？」），通过通信兵告诉其他将军。如果他收到 6 个以上将军的同意，就能发起进攻。但如果其他将军同时也在发不同的提议（2 点、3 点……），由于消息到达有时间差，不同将军收到并认可的提议可能不一样，于是出现 A 提议 3 票、B 提议 4 票、C 提议 2 票这种分裂局面。 再加入叛徒就更复杂了：一个叛徒会向不同的将军发出不同的提议（告诉 A 是 1 点、告诉 B 是 2 点），也可能同时同意多个互相冲突的提议。 叛徒发送的这种前后不一致、互相矛盾的信息，就叫「拜占庭错误（Byzantine fault）」。 ...