mysql gr_fast paxos_paxos视频(2)

(4) 在收到一个b= nextBal[q]的BeginBallot(b,d)消息后，牧师q在编号为b的表决中投出他的一票，设置prevVote[p]为这一票，然后发送Voted(b,q)消息给p（b!= nextBal[q]的BeginBallot(b,d)消息将被忽略）

(5) 在p收到Q中每一个q的Voted(b,q)消息后（这里Q是表决b的法定人数集合，b= lastTried[p]），他将d（这轮表决的法令）记录到他的律簿上，然后发送一条Success(d)消息给每个q

(6) 一个牧师在接收到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算法的各种演化、优化、简化和变种。这些算法和变种，在维基百科中概括的很好：

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-29394-2.html