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

也不是说P1就没有用，反过来看，P2是个未知问题，而P1是这个未知问题的已知部分，从契约的角度来看，P1就是个不变式，任何对P2的增强都不能过了头以至于无法满足P1这个不变式，也就是说，P1是P2增强的底线。

那还有没有其他的不变式需要遵守？是否在对P2增强的过程中已破坏了这些未知的不变式？这些高难度的问题牵扯到Paxos算确性，要看MIT的严格的数学证明，已超出了本文。

我们暂时按下P1不表，近距离观察一下P2，为了保证每次选出一个value，P2规定在一个Value已经被选出的情况下，如果还有其他的 proposer提交value，那之后批准的value应该跟前一个一致，就是在事实上已经选定一个value时，之后的proposer不能提交不同 的value把之前的结果打乱。这是一个泛泛的描述，但如果这个描述能得到实现，paxos算法就能得到保证，因此P2也称"safety property"。

接下来的讨论都时基于“If a proposal with value v is chosen”，如何保证“then every higher-numbered proposal that is chosen has value v”，具体怎么做到“a proposal with value v is chosen"暂且不谈。

P2更多是从思想层面上提出来该如何解决这个问题，但具体的落实工作需要很多细化的步骤，Lamport是通过逐步增强条件的方式进行落实P2，主要从下面几个方面进行：

对整个结果提出要求（P2）

对Acceptor提出要求（P2a）

对Proposer提出要求（P2b）

对Acceptor与Proposer同时提出要求（P2c）

Lamport为什么能把过程划分的如此清楚已经不得而知，但从Lamport发表的文章来看，他对分布式有很深的造诣，也持续了很长的时间，能有如此的结果，与他对分布式的基础与背后的巨大努力有很大关系。但对我们而言，不知过程只知个结果，总感觉知其然不知其所以然。

我们沿着上面的思路继续：

P2a：If a proposal with value v is chosen, then every higher-numbered proposal accepted by any acceptor has value v.

P2b：If a proposal with value v is chosen, then every higher-numbered proposal issued by any proposer has value v.

这个条件是在限制proposer，如果能限制住proposer，对acceptor的限制当然能被满足的。同时，因为限制proposer必须提交value v，也就顺便保证了P1（第一个肯定是value v）

但P2b是难以实现的，难实现的原因是多个proposer可以提交任意value的proposal，无法限制proposer不能提交某个value，因此需要寻找P2b的等价条件：

P2c：For any v and n, if a proposal with value v and number n is issued, then there is a set S consisting of a majority of acceptors such that either

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

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