paxos协议_从paxos到zookeeper_raft算法paxos算法(4)

(b) v is the value of the highest-numbered proposal among all proposals numbered less than n accepted by the acceptors in S.

首先要清楚P2c要做什么，因为P2b很难直接实现，P2c要做的就是解决P2b的问题，就是解决“如果value v被选择了，更高编号的提案已经具有value v”，也就是说：

R：“For any v and n, if a proposal with value v and number n is issued”是结果，而

C：“ then there is a set S consisting...”是条件

(a) no acceptor in S has accepted any proposal numbered less than n

如果这个条件成立，那么n是S中第一个proposal，根据P1，必须接受，所以结果R成立

(b) v is the value of the highest-numbered proposal among all proposals numbered less than n accepted by the acceptors in S

这个证明先假设编号为n的proposal具有value X被选择，肯定存在一个集合C，其中的每个acceptor都接受了value X，而集合S中的每个Acceptor都接受了value v，因为S、C都是多数派，所以存在一个公共成员u，既接受了X，又接受了v,为了保证选择的唯一性，必须X=v.

大家可能会发觉该证明有点不太严格，“小于n的最大编号”与n之间还有很多proposal，那些proposal也有一些value，那些value会不会不是v？

也就是说，P2c是P2b的一个加强，满足P2c就能满足P2b。

我们再近距离观察下P2c，发现只要在proposer提交提案前，咨询一下acceptor，看他们的最高编号是啥，他们是否选择了某个value v，再根据acceptor的回答进行选择新的编号、value提交，就可以满足P2c。通过编号，可以把(a)和(b)两个条件统一在一起。

其实P2c要表达的思想非常简单：如果前面有value v选出了，那以后就提交这个value v；否则proposer决定提交哪个value，具体做法就是事前咨询，事中决定，事后提交，也就是说可以通过消息传递模型实现。Lamport通过条 件、集合、归纳证明等形式表达该问题，而没提这样做的目的，会导致理解很困难。大家可能会比较疑惑，难道自始至终只能选出一个value？其实这里的选 出，是指一次选举，而不是整个选举周期，可以多次运行paxos，每次都只选出一个value。

满足P2c从侧面也反映出要想提交一个正确的value v，要对proposer、acceptor同时进行限制，仅限制一方问题是无法解决的。

再回顾下条件之间的递推关系P2c=>P2b=>P2a=>P2，就是说P2c最终保证了P2，也就是解决了如何做到一个value v被选择之后，被选择的编号更大的proposal都具有value v，P2c不仅保证P2的结果，更提出了“如何选”的问题，就是上面分阶段进行，这就填补了P1与P2之间缺少如何选的断层，还有P1的2个不完备问题从直观上感觉会得到解决，具体的要看算法过程章节。

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