区块链上的共识机制
区块链上的共识机制有多种，没有一种共识机制是完美无缺的，同时也意味着没有一种共识机制是适合所有应用场景的。
PoW：Proof of Work，工作量证明
依赖机器进行数学运算来获取记账权，资源消耗相比其他共识机制高、可监管性弱，同时每次达成共识需要全网共同参与运算，性能效率比较低，容错性方面允许全网50%节点出错1。
优点：完全去中心化，节点自由进出;缺点：目前bitcoin已经吸引全球大部分的算力，其它再用Pow共识机制的区块链应用很难获得相同的算力来保障自身的安全;挖矿造成大量的资源浪费;共识达成的周期较长。
使用PoW的项目：
比特币以太坊前三个阶段：即Frontier(前沿)、Homestead(家园)、Metropolis(大都会)。第四个阶段，即Serenity(宁静)，将采用PoS机制。
PoS：Proof of Stake，权益证明
Proof of Stake由Quantum Mechanic 2011年在bitcointalk首先提出，后经Peercoin和NXT以不同思路实现3。
主要思想是节点记账权的获得难度与节点持有的权益成反比，相对于PoW，一定程度减少了数学运算带来的资源消耗，性能也得到了相应的提升，但依然是基于哈希运算竞争获取记账权的方式，可监管性弱。该共识机制容错性和PoW相同4。它是Pow的一种升级共识机制，根据每个节点所占代币的比例和时间，等比例的降低挖矿难度，从而加快找随机数的速度5。
优缺点678：
优点：在一定程度上缩短了共识达成的时间;不再需要大量消耗能源挖矿。缺点：还是需要挖矿，本质上没有解决商业应用的痛点;所有的确认都只是一个概率上的表达，而不是一个确定性的事情，理论上有可能存在其他攻击影响。例如，以太坊的DAO攻击事件造成以太坊硬分叉，而ETC由此事件出现，事实上证明了此次硬分叉的失败。
Proof of Stake - 股权证明 系列1中对PoS有以下描述：
在POW中，一个用户可能拿1000美元来买计算机，加入网络来挖矿产生新区块，从而得到奖励。而在POS中，用户可以拿1000美元购买等价值的代币，把这些代币当作押金放入POS机制中，这样用户就有机会产生新块而得到奖励。
总体上说，POS算法如下所示。存在一个持币人的集合，他们把手中的代币放入POS机制中，这样他们就变成验证者。假设在区块链最前面一个区块(区块链中最新的块)，这时POS算法在这些验证者中随机选取一个(选择验证者的权重依据他们投入的代币多少，比如一个投入押金为10000代币的验证者被选择的概率是一个投入1000代币验证者的10倍)，给他们权利产生下一个区块。如果在一定时间内，这个验证者没有产生一个区块，则选出第二个验证者来代替来产生新区块。与POW一样，以最长的链为准。
有什么好处?
简而言之：
不再需要为了安全产生区块而大量消耗电能。
由于不再需要大量能耗，通过发行新币以激励参与者继续参与网络的压力会下降。理论上负总发行量甚至成为可能，由于一部分交易费&被烧&掉因此货币供应随着时间减少。
有可能通过&合作博弈论&减少自私挖矿攻击遭成的弱点，虽然POW在一定程度上也可以做到这一点。
随着规模经济(指扩大生产规模引起经济效益增加的现象)的消失，中心化所带来的风险减小了。价值一千万美元的代笔带来的回报不多不少是价值一百万美元代币的10倍，不会有人因为负担得起大规模生产工具得到不成比例的额外回报。
有关PoS的资料：
Proof of Stake - 股权证明 系列1 Proof of Stake - 股权证明 系列2：这两篇文章都是以太坊爱好者网站翻译的文章，里面简要介绍的PoS，没有介绍技术细节。
DPoS：Delegate Proof of Stake，股份授权证明
BitShares社区首先提出了DPoS机制9。
与PoS的主要区别在于节点选举若干代理人，由代理人验证和记账。其合规监管、性能、资源消耗和容错性与PoS相似10。类似于董事会投票，持币者投出一定数量的节点，代理他们进行验证和记账11。
DPoS的工作原理为12：
去中心化表示每个股东按其持股比例拥有影响力，51%股东投票的结果将是不可逆且有约束力的。其挑战是通过及时而高效的方法达到51%批准。为达到这个目标，每个股东可以将其投票权授予一名代表。获票数最多的前100位代表按既定时间表轮流产生区块。每名代表分配到一个时间段来生产区块。所有的代表将收到等同于一个平均水平的区块所含交易费的10%作为报酬。如果一个平均水平的区块含有100股作为交易费，一名代表将获得1股作为报酬。
网络延迟有可能使某些代表没能及时广播他们的区块，而这将导致区块链分叉。然而，这不太可能发生，因为制造区块的代表可以与制造前后区块的代表建立直接连接。建立这种与你之后的代表(也许也包括其后的那名代表)的直接连接是为了确保你能得到报酬。
该模式可以每30秒产生一个新区块，并且在正常的网络条件下区块链分叉的可能性极其小，即使发生也可以在几分钟内得到解决。
成为代表：
成为一名代表，你必须在网络上注册你的公钥，然后分配到一个32位的特有标识符。然后该标识符会被每笔交易数据的&头部&引用。
授权选票：
每个钱包有一个参数设置窗口，在该窗口里用户可以选择一个或更多的代表，并将其分级。一经设定，用户所做的每笔交易将把选票从&输入代表&转移至&输出代表&。一般情况下，用户不会创建特别以投票为目的的交易，因为那将耗费他们一笔交易费。但在紧急情况下，某些用户可能觉得通过支付费用这一更积极的方式来改变他们的投票是值得的。
保持代表诚实：
每个钱包将显示一个状态指示器，让用户知道他们的代表表现如何。如果他们错过了太多的区块，那么系统将会推荐用户去换一个新的代表。如果任何代表被发现签发了一个无效的区块，那么所有标准钱包将在每个钱包进行更多交易前要求选出一个新代表。
抵抗攻击：
在抵抗攻击上，因为前100名代表所获得的权力权是相同的，每名代表都有一份相等的投票权。因此，无法通过获得超过1%的选票而将权力集中到一个单一代表上。因为只有100名代表，可以想象一个攻击者对每名轮到生产区块的代表依次进行拒绝服务攻击。幸运的是，由于事实上每名代表的标识是其公钥而非IP地址，这种特定攻击的威胁很容易被减轻。这将使确定DDOS攻击目标更为困难。而代表之间的潜在直接连接，将使妨碍他们生产区块变得更为困难。
优缺点13：
优点：大幅缩小参与验证和记账节点的数量，可以达到秒级的共识验证。缺点：整个共识机制还是依赖于代币，很多商业应用是不需要代币存在的。
DPoS的相关资料：
浅谈区块链共识机制与分布式一致性算法：这篇文章主要介绍了一些传统分布式共识算法和DPoS白皮书。
Cer：投注共识
这是一种以太坊下一代的共识机制，属于PoS。Casper的共识是按块达成的而不是像PoS那样按链达成的14。
为了防止验证人在不同的世界中提供不同的投注，我们还有一个简单严格的条款：如果你有两次投注序号一样，或者说你提交了一个无法让Casper合约处理的投注，你将失去所有保证金15。从这一点我们可以看出，Casper与传统的PoS不同的是Casper有惩罚机制，这样非法节点通过恶意攻击网络不仅得不到交易费，而且还面临着保证金被没收的风险。
Casper协议下的验证人需要完成出块和投注两个活动。具体如下16：
出块是一个独立于其它所有事件而发生的过程：验证人收集交易，当轮到他们的出块时间时，他们就制造一个区块，签名，然后发送到网络上。投注的过程更为复杂一些。目前Casper默认的验证人策略被设计为模仿传统的拜占庭容错共识：观察其他的验证人如何投注，取33%处的值，向0或者1进一步移动。
而客户端的确认当前状态的过程如下所示17：
一开始先下载所有的区块和投注，然后用上面的算法来形成自己的意见，但是不公布意见。它只要简单的按顺序在每个高度进行观察，如果一个块的概率高于0.5就处理它，否则就跳过它。在处理所有的区块之后得到的状态就可以显示为区块链的&当前状态&。客户端还可以给出对于&最终确定&的主观看法：当高度k之前的每个块，意见要么高于99.999%或者低于0.001%，那么客户端就可以认为前k个块已经最终确定。
有关Casper的资料：
理解 Serenity - 第二部分: Casper：这篇文章是翻译自以太坊的博客，里面详细描述了casper的工作原理是什么。同时由于这个是以太坊官方描述，因此，如果想要深入了解Casper，那么这篇文章是必读的。 以太坊紫皮书(中文版)：紫皮书发布于2016年在上海举办的以太坊第二届开发者大会。里面详细介绍了以太坊下一代PoS共识机制的相关设想。也可以看紫皮书英文版：Ethereum 2.0 Mauve Paper。
Ripple Consensus：瑞波共识机制
瑞波币的共识算法如下18：
瑞波共识算法，使一组节点能够基于特殊节点列表达成共识。初始特殊节点列表就像一个俱乐部，要接纳一个新成员，必须由51%的该俱乐部会员投票通过。共识遵循这核心成员的51%权力，外部人员则没有影响力。由于该俱乐部由&中心化&开始，它将一直是&中心化的&，而如果它开始腐化，股东们什么也做不了。与比特币及点点币一样，瑞波系统将股东们与其投票权隔开，并因此比其他系统更中心化。
Pool验证池
基于传统的分布式一致性技术，加上数据验证机制;是目前行业链大范围在使用的共识机制。布比特有的?
优缺点19：
优点：不需要代币也可以工作，在成熟的分布式一致性算法(Pasox、Raft)基础上，实现秒级共识验证。缺点：去中心化程度不如更适合多方参与的多中心商业模式。
PBFT：Practical Byzantine Fault Tolerance，实用拜占庭容错
在分布式计算上，不同的计算机透过讯息交换，尝试达成共识;但有时候，系统上协调计算机(Coordinator / Commander)或成员计算机 (Member /Lieutanent)可能因系统错误并交换错的讯息，导致影响最终的系统一致性。拜占庭将军问题就根据错误计算机的数量，寻找可能的解决办法，这无法找到一个绝对的答案，但只可以用来验证一个机制的有效程度20。
而拜占庭问题的可能解决方法为21：
在 N & 3F + 1 的情况下一致性是可能解决。其中，N为计算机总数，F为有问题计算机总数。信息在计算机间互相交换后，各计算机列出所有得到的信息，以大多数的结果作为解决办法。
最早由 Castro 和 Liskov 在 1999 年提出的 Practical Byzantine Fault Tolerant(PBFT)是第一个得到广泛应用的 BFT 算法。只要系统中有2/3的节点是正常工作的，则可以保证一致性22。
PBFT算法的总体过程如下23：
客户端向主节点发送请求调用服务操作：
客户端c向主节点发送
dBFT：delegated BFT，授权拜占庭容错
2016年4月，小蚁发布共识算法白皮书，描述了一种通用的共识机制模块dBFT(delegated BFT)，提出了一种改进的拜占庭容错算法，使其能够适用于区块链系统24。dBFT算法在PBFT基础上进行了改进25：
将C/S架构的请求响应模式，改进为适合P2P网络的对等节点模式;将静态的共识参与节点改进为可动态进入、退出的动态共识参与节点;为共识参与节点的产生设计了一套基于持有权益比例的投票机制，通过投票决定共识参与节点(记账节点);在区块链中引入数字证书，解决了投票中对记账节点真实身份的认证问题。
专业化的记账人;可以容忍任何类型的错误;记账由多人协同完成，每一个区块都有最终性，不会分叉;算法的可靠性有严格的数学证明;
当有1/3或以上记账人停止工作后，系统将无法提供服务;当有1/3或以上记账人联合作恶，且其它所有的记账人被恰好分割为两个网络孤岛时，恶意记账人可以使系统出现分叉，但是会留下密码学证据;以上总结来说，dBFT机制最核心的一点，就是最大限度地确保系统的最终性，使区块链能够适用于真正的金融应用场景。
有关dBFT的资料：
一种用于区块链的拜占庭容错算法：这个是小蚁官方发布的关于dBFT算法的文档，里面详细介绍了dBFT算法的过程。
PoET：Proof of Elapsed Time，消逝时间量证明
它是由英特尔构建在可信执行环境的一种彩票协议28。
Quorum Voting：仲裁投票
它采用了瑞波和恒星的共识协议，用来解决需立即交易定局的需求29。
这是一种传统的分布式一致性算法。
是一种基于选举领导者的共识机制，领导者节点拥有绝对权限，并允许强监管节点参与，性能高，资源消耗低。所有节点一般有线下准入机制，但选举过程中不允许有作恶节点，不具备容错性30。
有关Paxos的资料：
维基百科-Paxos算法 知乎-如何浅显易懂地解说 Paxos 的算法?
这是一种传统的分布式一致性算法。
Raft相关资料：
The Raft Consensus Algorithm：Raft算法简介。 The Secret Lives of Data：这个是Raft算法动态演示，通过简单的动画将Raft的技术原理演示出来，非常值得一看。当前位置： &
paxos算法的英文
英文翻译paxos algorithm&&&&algorithm&&&&paxos算法&&&&algorithm◇算法语句 a 算法语言 algorithmic language (algol)&&&&algorithm&&&&de boor's algorithm&&&&de casteljau's algorithm&&&&cyk algorithm&&&&dfs algorithm&&&&dijkstra's algorithm&&&& d-algorithm&&&&knuthmorrispratt algorithm&&&&minimax&&&&rsa&&&&zip (file format)&&&& longhand method&&&&retrograde method&&&&back-calculation&&&&approximation method&&&& conversion&&&&integration method&&&& calculati ...&&&&contracted calculation&&&&order algorithm&&&&actuarial method&&&&annual report law
相邻词汇热门词汇
paxos算法的英文翻译，paxos算法英文怎么说，怎么用英语翻译paxos算法，paxos算法的英文意思，，，发音，例句，用法和解释由查查在线词典提供，版权所有违者必究。
&&&&&&&&&&&&&&&&
Copyright &
(京ICP备号)
All rights reserved当前位置：
(暂无评分)
&Loading ...
1982年，Leslie Lamport与另两人共同发表论文描述了一种计算机容错理论。为了形象的表达其中的问题，Lamport设想出了一种场景：拜占庭帝国有许多支军队，军队的将军们必须制订一个统一的行动计划——进攻或者撤退。将军们在地理上是分隔开来的，只能靠通讯员进行通讯。并且将军中存在叛徒。叛徒可以任意篡改消息，欺骗某些将军进攻或撤退。
这就是著名的“拜占廷将军问题”。理论研究显示，在一个3N+1的系统中，只有叛徒数目小于等于N的情况下，才有可能设计出一种协议，使得不管叛徒怎样作梗也能达成一致。
大多数系统在同一局域网中，消息被篡改的情况很罕见；因硬件和网络造成的消息不完整，只需简单的校验，丢弃不完整的消息即可。因此可以假设不存在拜占庭问题，也即假设所有消息都是完整的，没有被篡改的。在这种情况下需要什么样的算法保证一致性呢？
Leslie Lamport在1990年提出了理论上的解决方案，并给出了严格的数学证明。介于阐述“拜占廷将军问题”时这种类比方式的成功，Lamport同样用心良苦地设想出了一种场景来描述这种算法面对的问题和解决的过程：
在古希腊有一个Paxos小岛，岛上以议会的形式通过法令。议会中的议员通过信使传递消息，议员和信使都是兼职的，随时可能离开议会厅，并且信使可能重复投递消息，也可能一去不复返。议会协议要保证在这种情况下法令仍然能够正确的产生，并且不会出现冲突。
这也是Paxos算法名称的由来。于是有了《The Part-Time Parliament》这篇论文。但是论文中压根没有说Paxos小岛是虚构出来的，而是煞有介事的说是考古工作者发现了Paxos议会事务的手稿，从这些手稿猜测Paxos人议会的做法。从问题的提出到算法的推演论证，通篇贯穿了对Paxos议会历史的描述。
这篇论文提交之后，几个编辑都认为不够吸引人，要求Lamport将所有Paxos相关的类比描述都去掉。Lamport觉得这些人太没幽默感了，拒绝修改。直到8年后，有一个团队需要建设一个分布式系统，需要一种保证一致性的方法，Lamport将当年的论文交给他们，他们马上明白并去实行了。Lamport觉得时机成熟了，于是再次发表这篇论文。这次编辑同意了，并且在编者按中一本正经的说：“作者貌似是个对计算机科学偶尔感兴趣的考古学家，现在正在希腊小岛上进行野外考古作业，委托我来发表它”。。。也算是配合Lamport幽默了一把。—-这就是1998年Paxos算法的第一次公开发表。
Paxos算法用来解决通信不可靠的分布式系统中的一致性问题。通信不可靠包括：消息会延迟、重复投递甚至丢失，但是消息不会被篡改（没有拜占庭问题）。
在《The Part-Time Parliament》中议会协议以一个基本的Synod协议为基础。Synod协议描述了在早期的宗教会议中，多个牧师在随机缺席的情况下如何通过一项法令，并能保证一致性：每个牧师用结实耐用的律簿和擦不掉的墨水来记录法令，他们会把一些重要的表决信息记在律簿的背面。律簿上的法令条目永远不会改变，但是律簿背面的备注可能会被划掉。每个牧师p必须且只需在他的律簿后面记录如下信息：
lastTried[p]：由p试图发起的最后一个表决的编号，如果没有发起过则记录-∞
prevVote[p]：由p投票的所有表决中，编号最大的表决对应的p的投票，如果没有投过票则记录-∞
nextBal[p]：由p发出的所有LastVote(b,v)消息中，表决编号b的最大值。
基本协议的完整过程为：
牧师p选择一个比lastTried[p]大的表决编号b，设置lastTried[p]为b，然后发送NextBallot(b)消息给某些牧师。
在从p收到一个b大于nextBal[q]的NextBallot(b)消息后，牧师q将nextBal[q]设置为b，然后发送一个LastVote(b,v)消息给p，其中v等于prevVote[q]。（b&= nextBal[q]的NextBallot(b)消息将被忽略）
在从某个多数集合Q中的每个成员都收到一个LastVote(b,v)消息后，牧师p发起一个编号为b，法定人数集为Q，法令为d的新表决，其中d的选择遵守B3条件。然后他发送一个BeginBallot(b,d)消息给Q中的每一个牧师
在收到一个b= nextBal[q]的BeginBallot(b,d)消息后，牧师q在编号为b的表决中投出他的一票，设置prevVote[p]为这一票，然后发送Voted(b,q)消息给p（b!= nextBal[q]的BeginBallot(b,d)消息将被忽略）
在p收到Q中每一个q的Voted(b,q)消息后（这里Q是表决b的法定人数集合，b= lastTried[p]），他将d（这轮表决的法令）记录到他的律簿上，然后发送一条Success(d)消息给每个q
一个牧师在接收到Success(d)消息后，将法令d写到他的律簿上。
上图是在《The Part-Time Parliament》中描述的基本协议的交互过程。在基本协议的基础上完善各种问题得到了最终的议会协议。
为了让人更容易理解《The Part-Time Parliament》中描述的Paxos算法，Lamport在2001发表了《Paxos Made Simple》，以更平直的口头语言描述了Paxos，而没有包含正式的证明和数学术语。《Paxos Made Simple》中，将算法的参与者更细致的划分成了几个角色：Proposer、Acceptor、Learner。另外还有Leader和Client。将算法的过程明确的划分为4个阶段：
Phase 1a: Prepare
Proposer (当时的leader) 选择一个编号N，发送Prepare消息给所有Acceptor的某个子集（quorum）
Phase 1b: Promise
如果N比之前接受到的Prepare编号都大, 那么Acceptor承诺不再接受小于N的Prepare，并且发送本轮算法中他上一次接受的值给Proposer (当时的leader，以便leader作出符合算法的决定)。如果N比之前接受到的Prepare的编号小，那么拒绝发送消息。为什么要有这个承诺? 其实Lamport在《The Part-Time Parliament》中给出了很关键的说明和论证。因为消息的延时性，这个承诺可以保证在Leader选择一个value时，一致性成立的前提条件能够得到保证。但是在《Paxos Made Simple》中说的不是很透彻，因此这里会显得比较突兀。
Phase 2a: Accept!
如果Proposer接收到了多数（quorum）Acceptor的响应, 他就根据这些响应的返回值，选择一个恰当的值，将选出的值通过Accept!消息发送给Acceptor集合。怎样选择一个值是《Paxos Made Simple》重点说明的。选择值的规则保证了算法的一致性。
Phase 2b: Accepted
如果Acceptor收到了他承诺过的proposal对应的Accept!消息，那么接受其值，并发送Accepted消息给Proposer和每个Learner
在随后的几年，Lamport陆续发表了《Consensus on Transaction Commit》、《Cheap Paxos》、《Fast Paxos》等一系列论文，阐述了Paxos算法的各种演化、优化、简化和变种。这些算法和变种，在维基百科中概括的很好：
本文固定链接:
【上一篇】【下一篇】
您可能还会对这些文章感兴趣！Paxos算法-维基百科，自由的百科全书
Paxos算法是（Leslie
Lamport，就是
中的"La"，此人现在在）于提出的一种基于消息传递且具有高度容错特性的一致性算法。
问题和假设
分布式系统中的节点通信存在两种模型：（Shared
memory）和（Messages
passing）。基于消息传递通信模型的分布式系统，不可避免的会发生以下错误：进程可能会慢、垮、重启，消息可能会延迟、丢失、重复，在基础
Paxos 场景中，先不考虑可能出现消息篡改即拜占庭错误的情况。Paxos 算法解决的问题是在一个可能发生上述异常的中如何就某个值达成一致，保证不论发生以上任何异常，都不会破坏决议的一致性。一个典型的场景是，在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点都执行相同的操作序列，那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。一个通用的一致性算法可以应用在许多场景中，是分布式计算中的重要问题。因此从20世纪80年代起对于一致性算法的研究就没有停止过。
为描述 Paxos 算法，Lamport 虚拟了一个叫做 Paxos 的，这个岛按照议会民主制的政治模式制订法律，但是没有人愿意将自己的全部时间和精力放在这种事情上。所以无论是议员，议长或者传递纸条的服务员都不能承诺别人需要时一定会出现，也无法承诺批准决议或者传递消息的时间。但是这里假设没有（Byzantine
failure，即虽然有可能一个消息被传递了两次，但是绝对不会出现错误的消息）；只要等待足够的时间，消息就会被传到。另外，Paxos
岛上的议员是不会反对其他议员提出的决议的。
对应于分布式系统，议员对应于各个节点，制定的法律对应于系统的状态。各个节点需要进入一个一致的状态，例如在独立的系统中，各个处理器读内存的某个字节时，必须读到同样的一个值，否则系统就违背了一致性的要求。一致性要求对应于法律条文只能有一个版本。议员和服务员的不确定性对应于节点和消息传递通道的不可靠性。
算法的提出与证明
首先将议员的角色分为 proposers，acceptors，和 learners（允许身兼数职）。proposers
提出提案，提案信息包括提案编号和提议的 value；acceptor 收到提案后可以接受（accept）提案，若提案获得多数
acceptors 的接受，则称该提案被批准（chosen）；learners
只能“学习”被批准的提案。划分角色后，就可以更精确的定义问题：
决议（value）只有在被 proposers 提出后才能被批准（未经批准的决议称为“提案（proposal）”）；
在一次 Paxos 算法的执行实例中，只批准（chosen）一个 value；
learners 只能获得被批准（chosen）的 value。
另外还需要保证 progress。这一点以后再讨论。
作者通过不断加强上述3个约束（主要是第二个）获得了 Paxos 算法。
批准 value 的过程中，首先 proposers 将 value 发送给 acceptors，之后 acceptors 对
value 进行接受(accept)。为了满足只批准一个 value 的约束，要求经“多数派（majority）”接受的 value
成为正式的决议（称为“批准”决议）。这是因为无论是按照人数还是按照权重划分，两组“多数派”至少有一个公共的 acceptor，如果每个
acceptor 只能接受一个 value，约束2就能保证。
于是产生了一个显而易见的新约束：
P1：一个 acceptor 必须接受(accept)第一次收到的提案。
注意 P1 是不完备的。如果恰好一半 acceptor 接受的提案具有 value A，另一半接受的提案具有 value
B，那么就无法形成多数派，无法批准任何一个 value。
约束2并不要求只批准一个提案, 暗示可能存在多个提案。只要提案的 value
是一样的，批准多个提案不违背约束2。于是可以产生约束 P2：
P2：一旦一个具有 value v 的提案被批准(chosen)，那么之后批准(chosen)的提案必须具有 value v。
注:通过某种方法可以为每个提案分配一个编号，在提案之间建立一个全序关系，所谓“之后”都是指所有编号更大的提案。
如果 P1 和 P2 都能够保证，那么约束2就能够保证。
批准一个value意味着多个acceptor接受(accept)了该value. 因此,可以对P2 进行加强：
P2a：一旦一个具有 value v 的提案被批准(chosen)，那么之后任何 acceptor 再次接受(accept)的提案必须具有 value v。
由于通信是异步的，P2a 和 P1 会发生冲突。如果一个 value 被批准后，一个 proposer 和一个 acceptor
从休眠中苏醒，前者提出一个具有新的 value 的提案。根据 P1，后者应当接受，根据 P2a，则不应当接受，这中场景下 P2a 和
P1 有矛盾。于是需要换个思路，转而对 proposer 的行为进行约束：
P2b：一旦一个具有 value v 的提案被批准(chosen)，那么以后任何 proposer 提出的提案必须具有 value v。
由于acceptor能接受的提案都必须由proposer提出，所以P2b 蕴涵了 P2a，是一个更强的约束。
但是根据 P2b 难以提出实现手段。因此需要进一步加强 P2b。
假设一个编号为 m 的 value v 已经获得批准(chosen)，来看看在什么情况下对任何编号为
n（n&m）的提案都含有 value v。因为 m 已经获得批准(chosen)，显然存在一个 acceptors 的多数派
C，他们都接受(accept)了 v。考虑到任何多数派都和 C 具有至少一个公共成员，可以找到一个蕴涵 P2b 的约束
P2c：如果一个编号为 n 的提案具有 value v，那么存在一个多数派，要么他们中所有人都没有接受(accept)编号小于 n
的任何提案，要么他们已经接受(accpet)的所有编号小于 n 的提案中编号最大的那个提案具有 value v。
可以用证明
P2c 蕴涵 P2b：
假设具有 value v 的提案 m 获得批准，当 n=m+1 时，采用反证法，假如提案 n 不具有 value
v，根据P2c，则存在一个多数派S1，要么他们中没有人接受过编号小于 n 的任何提案，要么他们已经接受的所有编号小于 n
的提案中编号最大的那个提案不具有 value
v。由于S1和通过提案m时的多数派C之间至少有一个公共的acceptor，所以以上两个条件都不成立，导出矛盾从而推翻假设，证明了提案
n 必须具有 value v；
若 (m+1)..(n-1) 所有提案都具有 value v，采用反证法，假如新提案 n 不具有 value
v，根据P2c，则存在一个多数派S2，要么他们没有接受过 0..(n-1) 中的任何提案，要么他们已经接受的所有编号小于 n
的提案中编号最大的那个提案不具有 value v。由于S2和通过 m 的多数派 C 之间至少有一个公共的
acceptor，所以至少有一个 acceptor 曾经接受了 m，从而也可以推出 S2 中已接受的所有编号小于 n
的提案中编号最大的那个提案的编号范围在 m..(n-1) 之间，而根据初始假设，m..(n-1)之间的所有提案都具有 value
v，所以 S2 中已接受的所有编号小于 n 的提案中编号最大的那个提案肯定具有 value v，导出矛盾从而推翻新提案 n 不具有
value v 的假设。根据数学归纳法，我们证明了若满足P2c，则P2b一定满足。
P2c 是可以通过消息传递模型实现的。另外，引入了 P2c 后，也解决了前文提到的 P1 不完备的问题。
算法的内容
要满足 P2c 的约束，proposer 提出一个提案前，首先要和足以形成多数派的 acceptors
进行通信，获得他们进行的最近一次接受(accept)的提案（prepare 过程），之后根据回收的信息决定这次提案的
value，形成提案开始投票。当获得多数 acceptors 接受(accept)后，提案获得批准(chosen)，由
proposer 将这个消息告知 learner。这个简略的过程经过进一步细化后就形成了 Paxos 算法。
在一个paxos实例中，每个提案需要有不同的编号，且编号间要存在全序关系。可以用多种方法实现这一点，例如将序数和
proposer 的名字拼接起来。如何做到这一点不在 Paxos 算法讨论的范围之内。
如果一个最近一次接受(accept)的提案编号为 m 的acceptor 在 prepare 过程中回答了一个 proposer
针对提案 n (n & m)的问题，但是在开始对 n 进行投票前，又接受(accept)了编号小于 n 的另一个提案（例如
n-1），如果 n-1 和 m 具有不同的 value，这个投票就会违背 P2c。因此在 prepare 过程中，acceptor
进行的回答同时也应包含承诺：不会再接受(accept)编号小于 n 的提案。这是对 P1 的加强：
P1a：当且仅当 acceptor 没有回应过编号大于 n 的 prepare 请求时，acceptor 接受(accept)编号为 n 的提案。
现在已经可以提出完整的算法了。
决议的提出与批准
通过一个决议分为两个阶段：
prepare 阶段：
proposer 选择一个提案编号 n 并将 prepare 请求发送给 acceptors 中的一个多数派；
acceptor 收到 prepare 消息后，如果提案的编号大于它已经回复的所有 prepare 消息，则 acceptor
将自己上次接受的提案回复给 proposer，并承诺不再回复小于 n 的提案；
批准阶段：
当一个 proposor 收到了多数 acceptors 对 prepare 的回复后，就进入批准阶段。它要向回复
prepare 请求的 acceptors 发送 accept 请求，包括编号 n 和根据 P2c 决定的 value（如果根据
P2c 没有已经接受的 value，那么它可以自由决定 value）。
在不违背自己向其他 proposer 的承诺的前提下，acceptor 收到 accept 请求后即接受这个请求。
这个过程在任何时候中断都可以保证正确性。例如如果一个 proposer 发现已经有其他 proposers
提出了编号更高的提案，则有必要中断这个过程。因此为了优化，在上述 prepare 过程中，如果一个 acceptor
发现存在一个更高编号的提案，则需要通知 proposer，提醒其中断这次提案。
用实际的例子来更清晰地描述上述过程:
有 A1, A2, A3, A4, A5 5位议员, 就税率问题进行决议. 议员 A1 决定将税率定为 10%,
因此它向所有人发出一个草案. 这个草案的内容是:
现有的税率是什么? 如果没有决定, 则建议将其定为 10%. 时间: 本届议会第3年3月15日; 提案者: A1
在最简单的情况下, 没有人与其竞争; 信息能及时顺利地传达到其它议员处.
于是, A2-A5 回应:
我已收到你的提案, 等待最终批准
而 A1 在收到2份回复后就发布最终决议:
税率已定为 10%, 新的提案不得再讨论本问题.
这实际上退化为协议.
现在我们假设在 A1 提出提案的同时, A5 决定将税率定为 20%:
现有的税率是什么? 如果没有决定, 则建议将其定为 20%. 时间: 本届议会第3年3月15日; 提案者: A5
草案要通过侍从送到其它议员的案头. A1 的草案将由4位侍从送到 A2-A5 那里. 现在, 负责 A2 和 A3
的侍从将草案顺利送达, 负责 A4 和 A5 的侍从则不上班. A5 的草案则顺利的送至 A3 和 A4 手中.
现在, A1, A2, A3 收到了 A1 的提案; A3, A4, A5 收到了 A5 的提案. 按照协议, A1, A2,
A4, A5 将接受他们收到的提案, 侍从将拿着
我已收到你的提案, 等待最终批准
的回复回到提案者那里.
而 A3 的行为将决定批准哪一个.
假设 A1 的提案先送到 A3 处, 而 A5 的侍从决定放假一段时间. 于是 A3 接受并派出了侍从. A1 等到了两位侍从,
加上它自己已经构成一个多数派, 于是税率 10% 将成为决议. A1 派出侍从将决议送到所有议员处:
税率已定为 10%, 新的提案不得再讨论本问题.
A3 在很久以后收到了来自 A5 的提案. 由于税率问题已经讨论完毕, 他决定不再理会. 但是他要抱怨一句:
税率已在之前的投票中定为 10%, 你不要再来烦我!
这个回复对 A5 可能有帮助, 因为 A5 可能因为某种原因很久无法与与外界联系了. 当然更可能对 A5 没有任何作用, 因为
A5 可能已经从 A1 处获得了刚才的决议.
依然假设 A1 的提案先送到 A3 处, 但是这次 A5 的侍从不是放假了, 只是中途耽搁了一会. 这次, A3
依然会将"接受"回复给 A1. 但是在决议成型之前它又收到了 A5 的提案. 这时协议有两种处理方式:
1. 如果 A5 的提案更早, 按照传统应该由较早的提案者主持投票. 现在看来两份提案的时间一样(本届议会第3年3月15日).
但是 A5 是个惹不起的大人物. 于是 A3 回复:
我已收到您的提案, 等待最终批准, 但是您之前有人提出将税率定为 10%, 请明察.
于是, A1 和 A5 都收到了足够的回复. 这时关于税率问题就有两个提案在同时进行. 但是 A5 知道之前有人提出税率为
10%. 于是 A1 和 A5 都会向全体议员广播:
税率已定为 10%, 新的提案不得再讨论本问题.
一致性得到了保证.
2. A5 是个无足轻重的小人物. 这时 A3 不再理会他, A1 不久后就会广播税率定为 10%.
在这个情况中, 我们将看见, 根据提案的时间及提案者的权势决定是否应答是有意义的. 在这里,
时间和提案者的权势就构成了给提案编号的依据. 这样的编号符合"任何两个提案之间构成偏序"的要求.
A1 和 A5 同样提出上述提案, 这时 A1 可以正常联系 A2 和 A3; A5 也可以正常联系这两个人. 这次 A2
先收到 A1 的提案; A3 则先收到 A5 的提案. A5 更有权势.
在这种情况下, 已经回答 A1 的 A2 发现有比 A1 更有权势的 A5 提出了税率 20% 的新提案, 于是回复 A5
我已收到您的提案, 等待最终批准.
而回复了 A5 的 A3 发现新的提案者A1是个小人物, 不予理会.
A1没有达到多数，A5达到了，于是 A5 将主持投票, 决议的内容是 A5 提出的税率 20%.
如果 A3 决定平等地对待每一位议员, 对 A1 做出"你之前有人提出将税率定为 20%" 的回复, 则将造成混乱. 这种情况下
A1 和 A5 都将试图主持投票, 但是这次两份提案的内容不同.
这种情况下, A3 若对 A1 进行回复, 只能说:
有更大的人物关注此事, 请等待他做出决定.
另外, 在这种情况下, A4 与外界失去了联系. 等到他恢复联系, 并需要得知税率情况时,
他(在最简单的协议中)将提出一个提案:
现有的税率是什么? 如果没有决定, 则建议将其定为 15%. 时间: 本届议会第3年4月1日; 提案者: A4
这时, (在最简单的协议中)其他议员将会回复:
税率已在之前的投票中定为 20%, 你不要再来烦我!
决议的发布
一个显而易见的方法是当 acceptors 批准一个 value 时，将这个消息发送给所有
learner。但是这个方法会导致消息量过大。
由于假设没有 Byzantine failures，learners 可以通过别的 learners 获取已经通过的决议。因此
acceptors 只需将批准的消息发送给指定的某一个 learner，其他 learners
向它询问已经通过的决议。这个方法降低了消息量，但是指定 learner 失效将引起系统失效。
因此 acceptors 需要将 accept 消息发送给 learners 的一个子集，然后由这些 learners
去通知所有 learners。
但是由于消息传递的不确定性，可能会没有任何 learner 获得了决议批准的消息。当 learners
需要了解决议通过情况时，可以让一个 proposer 重新进行一次提案。注意一个 learner 可能兼任 proposer。
Progress 的保证
根据上述过程当一个 proposer
发现存在编号更大的提案时将终止提案。这意味这提出一个编号更大的提案会终止之前的提案过程。如果两个 proposer
在这种情况下都转而提出一个编号更大的提案，就可能陷入活锁，违背了 Progress 的要求。这种情况下的解决方案是选举出一个
leader，仅允许 leader 提出提案。但是由于消息传递的不确定性，可能有多个 proposer 自认为自己已经成为
leader。Lamport 在一文中描述并解决了这个问题。
为简化的 Paxos 算法申请了。但专利中公开的技术和本文所描述的不尽相同。
（Google 公司）在其（Chubby
lock）中应用了Paxos算法。Chubby
lock 应用于（Bigtable），后者在所提供的各项服务中得到了广泛的应用。
── Lamport 于1998年发表在
ACM Transactions on Computer Systems。
注：这是该算法第一次公开发表。
，2001年。
注：Lamport 觉得同行无法接受他的幽默感，于是用容易接受的方法重新表述了一遍。
Lamport 本人在
中描写了他用9年时间发表这个算法的前前后后
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。