MIT 6.824拾遗（一）聊聊basic-paxos

• 2021 年 3 月 27 日
• 筆記

前言

The Paxos algorithm, when presented in plain English, is very simple.
—————— Lamport，《Paxos Made Simple》

Unfortunately, Paxos is quite difficult to understand, in spite of numerous attempts to make it more approachable.
—————— Diego Ongaro，《In Search of an Understandable Consensus Algorithm》

在不同的博客和视频中，对于basic-paxos的讲解有多个维度。例如说zhihu作者@多颗糖和Diego Ongaro（Raft算法的提出者）的视频是以具体事例作为角度来讨论和分析的，而Lamport的《Paxos Made Simple》和Paxos的Wikipedia则通过逐级添加和强化约束条件的方式，来逐步使一个简单的算法渐渐向共识算法靠拢，最终推导出basic-paxos的实现逻辑。我个人比较推荐的是首先参照Diego Ongaro和 @多颗糖 给出的注解来学习和了解basic-paxos的基本逻辑，再将自己想到的和锁提到的各种情景套入到算法中，推断这些情景的存在性、产生过程和解决方法，最后阅读Lamport的论文。

本篇blog更倾向于做一个关于《Paxos Made Simple》中关于basic-paxos的个人注解。参考的资料我会放在博客的最末尾。

共识问题

共识

在一个系统中包含有n个进程{1,2,3,4…n}，部分进程会提出一个VALUE，进程之间互不相知对方的VALUE到底是多少，但可以通过相互通信来获悉其他进程的VALUE，也可以考虑修改自己的VALUE；我们需要设计一种算法，使得这n个进程最终能够协商达成一个不可撤销的最终VALUE；能达成这个目的的算法就被称作是一种共识算法。

异步网络条件

进程之间必须通过相互通信才能获悉对方的VALUE，但通信过程是完全异步的。如果进程1希望与进程2通信，那么进程1就要向进程2发出请求，然后等待进程2的答复；在异步网络环境下，这个等待的时间可能是无限的。

非拜占庭条件

进程之间的异步通信可能丢失、重复、失序、延迟，通信网络之间也可能会发生分区（但分区最终会复原），但通信的内容必定不会损坏（corrupt）；
进程本身也随时可能崩溃、重启，但进程一旦开始运行，必定处于正确的状态。在进程间的通信中，进程的回应必定能正确反映自己的状态，即进程不会对其他进程进行无意（进入了错误状态但不自知）或者恶意的（被黑客篡改、伪造了通信内容）欺诈；

对于一个共识算法来说，它的执行必须满足如下三个性质：
1）终止性（Termination），所有的进程最终都会认同某一个值；
2）协定性（Agreement），所有进程最终认定的必定是同一个值；
3）完整性（Integrity），如果正确的进程都提议同一个值，那么所有处于认同状态的进程都选择该值；

由于我们假定不存在拜占庭问题，因此只要共识算法只需满足1）和2）即可。

共识（consensus）问题是分布式系统研究中的基础问题之一，虽然与解决了多复制状态机间状态一致性问题的raft算法相比，basic-paxos所解决的共识问题看起来更偏向底层、难以直接应用，但其同样可以解决分布式系统中的一系列核心问题。

在理解了basic-paxos运行的环境（异步非拜占庭），以及basic-paxos所需要解决的问题之后（达成共识，并满足三个共识算法的性质），我们可以开始讨论basic-paxos的实现了。

paxos的基本概念

在一个paxos系统中存在三类角色：proposers（提议者）、acceptors（接收者）、learners（学习者）。由proposer提出VALUE，由acceptor表决是否接受（accept）proposer提议的VALUE，共识（consessus）的达成等价于acceptors们对VALUE达成一致共识，learner只能被动的学习acceptor所达成共识的VALUE；

举例来说，系统中有2个proposer，5个acceptor，2个learner；我们现在希望系统对Colors = {RED,ORANGE,YELLOW,GREEN,BLUE,BLACK,PURPLE} 中的一种Color达成共识；那么需要由proposer发出（issue）提议，希望acceptor们能接受（accept）它所提议的Color（两个proposer可能提议不同的颜色，单独的一个proposer也可能中途改变主意，发出另一种颜色的提议）；当acceptor能够对COLOR达成共识时，便选出（chosen）了一个不可撤销的Color（假设为YELLOW）；acceptor间达成共识的结果应当被learner所学习到；

等价性

不难理解，前文所述的共识算法的三点特性，等价于paxos算法中的以下三个特性：
1）决议（VALUE）必须由proposer提出；
2）如果acceptor达成了共识，那么它们认定的VALUE不可撤销；
3）learn只能学习到那些达成共识的VALUE；

也就是说，我们paxos算法只要保障了以上三个特性，便保证了共识算法需要保证的特性，那么我们的paxos算法就是一种共识算法；这样将原本比较抽象的问题转换成了比较具体的问题；我们在上文中又提出了三个新概念：accept、chosen、issue：

accept

accept指一个acceptor暂时接受了一个VALUE，但不保证这个VALUE是最终达成共识的VALUE；当acceptor收到了新的提案时，它可能会修改自己所accept的VALUE。

chosen

当超过半数的acceptor成功的accept了一个VALUE之后，我们称这个VALUE已经被选中（chosen）了，这个VALUE就是最终必须要达成共识的VALUE，而这也意味着我们可能会修改acceptor所accept的VALUE，让它变成对应的被chosen的VALUE。

issue

一切的VALUE必须先由proposer发布（issue），然后才可能被一些acceptor所接受（accept），然后才可能有机会最终被选中（chosen）。如果一个VALUE没有被proposer所发布，那么这个VALUE就不可能被选中（chosen）。

值得注意的是，在Paxos中，一台机器可以同时担任三种角色中的多个角色。

在定义了上述内容之后，我们终于可以逐渐推导basic-paxos算法了。我们首先讨论最简单的情景与解决这一情景的简单算法，再逐渐强化我们的算法以推广到更加复杂的情景，最终得到basic-paxos算法。

约束条件P1

Lamport首先假定了一个非常简单的情景：网络条件良好（请求和应答都是立即送达的）且机器不会崩溃，只issue了一个提案且这个提案只会被发布一轮，自然也就只有一个VALUE被提出；我们期望我们的算法在这个情景下必定能chosen那个VALUE；为此引入了约束条件P1：

P1. An acceptor must accept the first proposal that it receives.

容易证明，在上述情景下，如果算法满足P1，则必定能chosen一个VALUE，即P1在上述情景下是完备的。但如果把情景稍微复杂化，则P1就不完备了：我们假定多个proposer们issue了提案，这些提案涉及到了不同的VALUE，且存在一定的网络延迟，且proposer们只issue一轮提案；根据P1，acceptor们根据请求到来的先后顺序选择了VALUE，但可能没有一个VALUE被半数以上的acceptor所accept，即没有一个VALUE被chosen，如下图所示：

由于proposer们只会发布一轮提案，因此acceptor们永远不会改变自己所accept的VALUE，也就永远不会有VALUE被chosen，这样就违背了共识算法的Termination要求；

提案号（ProposeNum）的引入

通过上述讨论我们可以得知，如果仅进行一轮提案，则可能会因为其他proposer与之竞争acceptor导致无法chosen一个VALUE。但上文的情景中，仅仅假定网络只会造成延迟（Delay）而已，更加恶劣的情况（丢失、失序等）还尚未考虑在内。实际上在异步的情景下，即使一轮提案顺利的chosen了一个VALUE，proposer也可能因为acceprot的回复丢失和延迟而久久无法获知。因此，约束条件P1仅在前文中的那个简单的情景下适用。现在我们的情景更加复杂了，我们需要寻找更多的约束条件来使算法达到要求！

由于一轮提案无法保证chosen一个VALUE，因此我们的basic-paxos需要添加多轮提案的支持。此时我们的算法希望能够保证，无论我的提案会进行多少轮，只要我最终能chosen一个不可撤销的VALUE即可。

为了区分开不同的提案以及不同轮次的提案，我们需要为每一个提案分配一个唯一的、单调递增的proposeNum，并将这个proposeNum捎带在通信的信息中。最简单的proposeNum的生成方法为 concatenate（物理or逻辑时钟，proposerId），即将物理or逻辑时钟作为proposeNum的高位，将proposerId作为proposeNum的低位。由于物理or逻辑时钟是严格递增的，因此proposeNum是单调递增的；由于proposerId是唯一的，因此proposeNum必定是唯一的。至于proposeNum的具体应用，将在下面的内容中进行讲解。

上图为Diego Ongaro在讲解Paxos的视频中使用的ProposerNumber的生成方式，Round Number本身可以看做是一个逻辑时钟，类似于Raft算法中的term。

再谈约束条件P1

我们回忆一下P1的内容：

P1. An acceptor must accept the first proposal that it receives.

在Lamport为提出P1所举的例子中，限定只进行一轮提案，因此the first proposal的指代是非常明显的，但在引入了proposeNum之后，the first proposal的指代就不是很明确了，Lamport在《Paxos Made Simple》中也没有很明确的定义在引入了proposeNum下的 the first proposal 到底是什么。

我个人根据上下文的是这样理解的：假设无法保证proposer们提案的proposeNum不同，那么存在不同的proposer通过同一个proposeNum提出不同VALUE的情景；对于这些相同proposeNum但不同VALUE的多个提案，acceptor只能accept它所收到的第一个提案，并拒绝相同proposeNum其他的VALUE；但由于proposeNum是全局唯一、仅用一次的、仅能由唯一的proposer生成的，因此一旦proposeNum给定，那么这个提案的VALUE就已经确定了，因此不存在前文中我所提到的问题。

到此为止，如果是按照我的理解的话，P1条件已经变得非常模糊甚至可以认为不存在了，因为acceptor接受任何proposeNum下的任何VALUE，仍然是满足P1的。但这没有关系，在讨论完P2之后，我们会强化P1条件，使其成为我们共识算法的重要组成部分。

约束条件P2

上文长篇大论的讨论的内容浓缩起来其实很简单：在异步、非拜占庭条件下，共识可能需要一轮以上的提议才能实现，但多轮提议仅仅是共识算法的一个必要不充分条件，我们还需要加入更强的约束。

引入了多轮提议之后，你可以尝试着去构想一些情景，你会发现，构建一个多轮提议下仍然无法让半数以上的acceptor们accept同一个VALUE的情景，实在是太容易太容易了。怎么避免他们陷入这种无穷无尽的扯皮，暂时不是我们要考虑的内容，我们现在要考虑的是另一个同等重要的问题：如何保障chosen VAUE不可撤销，或者说能避免chosen到第二个VALUE？

我们知道，一个VALUE被chosen等价于其被半数以上的acceptor们accpet了，所以最简单的让chosen VALUE不可撤销的方法是禁止acceptor们改变自己accept的VALUE，但这就违背了P1，也很可能使共识永远无法达成，因此我们仍然希望acceptor可以更改自己accept的VALUE。然而但如果不增加额外的约束限制，那么仍然可能有多个VALUE被chosen，这就违背了我们共识算法等价条件的不可撤销性，如下图所示：

一切的罪魁祸首是proposer S5 浑然不知的提出了一个BLUE提案，而acceptor们浑然不知，只是严格的遵守着约束条件P1（proposer：怪我喽？你们acceptor们怎么不长眼呐）；我们要避免这种情况，据此引入了约束条件P2：

P2. If a proposal with value v is chosen, then every higher-numbered proposal that is chosen has value v.

如果我们的共识算法能让acceptor们遵守P1，让proposer们遵守P2，虽然proposer和acceptor们可能还会因为迟迟无法让VALUE达成共识而互飞提案相互扯皮，但只要一个VALUE被chosen了，那么后续的proposer们issue的提案中的VALUE只能是那个chosen VALUE，这样就保证了VALUE的不可撤销性。如果我们引入了一些其他的手段解决了相互扯皮的问题，那么我们的算法就是一个共识算法了！

但是想着容易做着难，如何实现P2约束目前来说是一个很棘手的问题。此时，Lamport点明了几个尝试，试图使用一个比P2更严格但更好实现的约束来解决这个问题。由于这些约束比P2更加严格，因此实现了这些约束，也就实现了P2。

P2a约束

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

即我们希望在acceptor处加强限制；如果半数以上的acceptor们已经accept了VALUE，那么我们期望acceptor在accept更高proposeNum的提案时，只接受那些VALUE为v的提案；暂时不考虑具体的实现方式，不难推理得出，满足P2a就满足了P2。

但这又产生了一些问题：第一，一个acceptor很难知道一个VALUE是不是chosen VALUE，这在实现上有一些困难；第二，正如前文所述，只有P1和P2同时满足时，我们的算法才是共识算法，但P1和P2a可能存在冲突。仍然假设我们的系统中有2个proposer，5个acceptor。proposerId为1的proposer兢兢业业的让VALUE = RED 这个VALUE被acceptor {1,4,5}所accept，但由于网络分区的缘故，3没有收到过任何提案。现在我们知道RED已经被chosen了，而浑浑噩噩的proposerId为2的proposer它 issue 了 VALUE = GREEN 的提案，这个提案被递交到了3上。根据P1，3应当accept了GREEN这个VALUE，但根据P2a，3 accept的提案的VALUE必须是RED，这样就产生了冲突。

最终由于各种原因，P2a约束没有被我们所采用，Lamport又点出了第二个约束：

P2b约束

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

这里我们将限制条件加在了proposer端，使得实现大为简化，因为proposer是可以根据proposeNum以及与acceptor之间的通信得知是否有VALUE被chosen的。虽然从构思上讲，P2b的实现已经比较容易了，但我们期望让它实现的更简单、更严谨、更明确一些，Lamport继续提出新的约束条件P2c：

P2c约束

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 (b) v is the value of the highest-numbered proposal among all proposals numbered less than n accepted by the acceptors in S.

在P2c约束下，proposer发布提案<proposeNum = n, value = VALUE>之前，这个提案的proposeNum和VALUE至少要满足如下两个条件之中的一个：
a）acceptor中存在一个多数派S，它们均未曾accpet过 proposeNum < n 的提案，或者
b）acceptor中存在一个多数派S，它们之中至少一个acceptor曾经accept过proposeNum < n的提案，且VALUE等于S中，proposeNum < n的最大的proposeNum的提案所提出的VALUE；

P2c约束是包含了P2b的，在《Paxos Made Simple》中也有归纳证明，我个人就不叙述了（其实就是看不懂）。

但是P2c的a和b仍然难以实现。不要忘记我们的网络环境是异步的！proposer为了推断自己的提案是属于情况a还是情况b，必须向acceptor发送异步请求获悉acceptor当时的<lastAcceptPropNum, lastAcceptValue>。假设当proposer收到了半数以上的回复，发现proposer的提案满足a。很容易推断在a下是没有chosen的值的，因此proposer可以随便任选一个值。但由于问询和回复均是异步的，因此proposer收到回复后，无法得知情景是不是发生了变化。假设proposer在把这个提案发布之前，一个<proposeNum = n, VALUE = BLUE> 的提案被S中的一个acceptor所接受，那么此时p2c约束条件就被打破了。在这种情景下，如果发布提案仍然可能会chosen出多个VALUE，破坏了VALUE的不可撤销性。

上图是一种在P2c约束的悬崖上走钢丝情景。S1希望issue一个<PropNum=5, Value = RED>的提案，为此它要向半数以上的acceptor询问他们最近一次accpet的propseNum和VALUE；当S1收到半数以上的回复时，它感觉自己的提案符合情景a，但它不敢issue这个提案。在异步网络环境下，由于网络延迟，proposer不敢确定在它issue提案时，acceptor们的情景仍然是它从回复中了解到的那个情景。实际上在proposer准备issue时，VALUE = BLUE已经被chosen，根据P2c约束要求，S1所issue的提案中的VALUE应当是BLUE，但S1并不能从这一轮的回复中推断得知这个消息。

P1a约束

basic-paxos采用了一种非常精髓的方式来避免上述情景，即将P1约束进行加强，获得新的约束P1a：

P1a. An acceptor can accept a proposal numbered n iff it has not responded to a prepare request having a number greater than n.

P2c约束对proposer所issue的提案进行了限制，而P1a则对acceptor们accept的情景进行了限制：在proposer向acceptor询问<lastProposeNum, lastProposeValue>时，要求这个acceptor给出承诺，不得accept任何proposeNum < n 的提案。在P1a的助攻下，P2c也终于可以通过一轮简单的问询，确认自己的提案是不是属于a情景或者b情景了。

这样我们得到了basic-paxos的最终约束条件：P1a再加上P2c。

二阶段协议的设计

P2c + P1a 组成了basic-paxos的全部约束条件，他们也是非常详细且易于实现的。很明显，一个轮次的basic-paxos可以分为两个阶段：Prepare和Issue，分别对应两个RPC（prepareRPC，acceptRPC）。现在假设这个提案的proposeNum为 n，让我们来考察一下basic-paxos的两个阶段：

Prepare阶段

根据P2c约束我们可知，proposer的提案必须要满足a或者b；根据P1a约束我们可知，可以通过一轮对acceptor们的 <lastProposeNum，lastProposeValue> 的询问推断提案是否满足a或者b；Prepare阶段的目的就在于向acceptor们咨询<lastProposeNum，lastProposeValue> 。当proposer收到了半数以上的回复后，就可以判断自己的提案的情况了：

0）acceptor收到了来自proposer的prepareRPC请求时，必须要向proposer承诺不再accept那些proposeNum < n的请求，为此它维持一个max_propose_num，如果 n > max_propose_num，则令自己的max_propose_num = n，并承诺拒绝一切 proposeNum < max_propose_num 的 acceptRPC。

1）如果多数派的acceptor未曾accept过 proposeNum < n 的提案，则可以得知 proposeNum < n 的提案没有chosen出一个VALUE。此时proposer可以issue这个提案，VALUE是多少可以由proposer自行决定；或者说

2）得到的半数以上的回复中，至少有一个acceptor过去曾经 accept 过 proposeNum < n 的提案；此时proposer必须放弃自己想要提出的VALUE，替代以收到的回复中proposeNum最接近且小于（“旧中最新”）的那个提案中的VALUE；

Accept阶段

经过Prepare阶段后，proposer已经知道自己到底应该issue一个什么VALUE了，因此它向所有的acceptor们发送acceptRPC请求，并将自己的proposeNum（本例中是n）添加到acceptRPC中。acceptor接收到acceptRPC后，会将proposeNum与自己的max_propose_num进行比较。如果proposeNum >= max_propose_num，则设定自己的lastProposeNum = proposeNum，lastProposeValue = VALUE，必要时会更新自己的max_propose_num。

伪代码

Diego Ongaro在basic paxos的讲解视频中，将伪代码表述如下：

再谈终止性（Termination）

现在回顾一下章节约束条件P2中我所说的话：

你会发现，构建一个多轮提议下仍然无法让半数以上的acceptor们accept同一个VALUE的情景，实在是太容易太容易了。怎么避免他们陷入这种无穷无尽的扯皮，暂时不是我们要考虑的内容，我们现在要考虑的是另一个同等重要的问题 ….

是的，读到现在你发现，我们长篇大论了这么久，仅仅只解决了一个问题，即如果一个VALUE已经被chosen，如何保证这个chosen VALUE不可撤销，并设计出了满足这一问题的实现算法而已！proposer和acceptor可能迟迟达不成共识这一问题，仍然没有得到较好的解决！但这一问题如果不能解决，我们的basic-paxos算法就和Termination这一原则相抵触了。Lamport在《Paxos Made Simple》中也注意到了这一点，他提出的解决方法是选主，即尽最大努力保证系统内仅有一个proposer，以避免多个proposer间提案相互冲突的情景。但Lamport也点明，即使我们不实用选主策略，算法仍然是可以推进的。

一点分析

直接看伪代码可能仍然会比较疑惑，我们考察一些具体的情景，换一种方式理解Basic-Paxos。

假定集群中的acceptor们为{1, 2, 3, 4, 5}；
1）1在prepare阶段使用proposeNum = 1 联系了{1, 2, 3}，则当前的 minProposal 为{1, 1, 1, 0, 0}；然后1顺利的让自己accept了BLUE，但其他的acceptRPC全部丢失；
2) 2prepare阶段使用proposeNum = 2 联系了{1, 2, 3}，当前的 minProposal 为 {2, 2, 2, 0, 0}，根据算法，2必须要用issue的VALUE为BLUE，但它也仅让自己accpet了BLUE，其他acceptRPC全部丢失；
3) 5在prepare阶段使用proposeNum = 3 联系了 {3, 4, 5}，则当前的 minProposal 为 {2, 2, 3, 3, 3}，根据算法，5可以使用自定义的VALUE，假定为RED；但它也仅让自己accept了RED；
此时此刻，accpetor {1, 2, 5} 顺利的accpet了VALUE，分别为 {BLUE, BLUE, NULL, NULL, RED}, accpetProposeNum分别为 {1, 2, NULL, NULL, 3}；
4）通过proposeNum = 4联系了 {1, 2, 3}，当前的minProposal 为 {4, 4, 4, 3, 3}，根据算法，3要issue的提案中的VALUE必须是BLUE。当3成功的accept了BLUE后，那么BLUE就成功的被{1, 2, 3}所accept了，因此BLUE成功被chosen；

结论1：如果已经有VALUE被chosen了，假定acceptor们所有accpet的VALUE构成集合S，那么proposer们所issue的任何提案的VALUE必定属于S；

如果已经有了chosen VALUE，那么必定有多数的acceptor已经accept了VALUE。回顾一下我们的算法，只有当proposer发现半数以上的acceptor没有accept过任何VALUE时，才能自己决定一个VALUE;在prepare阶段，proposer与半数以上的acceptor们联系，必定会发现至少一个acceptor已经accept了VALUE，这些VALUE均属于S；根据算法，proposer必须放弃自己想要propose的VALUE；故结论1得证；

结论2：如果已经VALUE被chosen了，那么不存在一个未chosen的VALUE，它的acceptedProposedNum比一切chosen VALUE的acceptedProposeNum更大；

在我举的栗子中，chosen VALUE为BLUE，其最大的acceptedProposedNum为4，大于unchosen VALUE 3的acceptedProposedNum（值为3）；

我们可以通过反证法来证明结论2，即假设存在一个acceptor成功accept了一个VALUE，它的acceptProposeNum比一切chosen VALUE的acceptedProposeNum更大；
根据结论0我们可知，不可能有S以外的VALUE被issue，因此这个特殊的VALUE必定是属于S的；考察这个特殊的VALUE被accept的时机，要么在chosen VALUE被chosen之前，要么在之后。

情况一：如果这个SPECIAL VALUE是在chosen VALUE被chosen之前才被某个acceptor所accept的，假设对应的acceptProposeNum为specialProposeNum。由于这个SPECIAL VALUE已经被accept，它必定通过了prepare阶段，那么必定多数的acceptor的minPropose被设定为了specialProposeNum。但chosen VALUE在被chosen前的最后一步（即只需要再有一个acceptor成功accept了chosen VALUE，那么chosen VALUE就顺利被chosn了），也会和多数的acceptor取得联系，必定能得知specialProposeNum，因此最后的一个acceptor成功accept chosen VALUE时，对应的acceptProposeNum必定是大于specialProposeNum的，这个我们的假设相矛盾；

情况二：如果这个SPECIAL VALUE是在chosen VALUE被chosen之后才被某个acceptor所accpet的。注意此时此刻，SPECIAL VALUE尚未被任何acceptor所accept（否则，应该属于情况一）；既然SPECIAL VALUE已经被accept了，那么它必定已经顺利通过了prepare阶段，这与结论1相矛盾；

因此结论2得证；

结论3：如果已经VALUE被chosen了，已经accept了chosen VALUE的acceptor不可能改变自己accept的结果；

结论3仍然可以用反证法轻松证明。如果某个accept了chosen VALUE的accpetor改变了自己的accept结果accept了一个unchosen VALUE，那么必定有一个proposer成功的发出了acceptRPC，那么这个proposer必定要通过了prepare阶段，那么根据prepare规则，这个proposer必须要发现一个acceptor的多数派M，在M中的acceptor，要么没有accept过任何VALUE，要么accept的VALUE就是那个unchosen VALUE。这个多数派与accept了chosen VALUE的多数派至少有一个交集，故矛盾。

结论4：如果已经VALUE被chosen了，那么全体acceptor达成共识的进度（即达成全部的acceptor均accept到chosen VALUE的成就）只能向前推进，不可能后退；

虽然在prepare阶段，proposer可能会pick一个unchosen value，且可能无限次的pick这个unchosen value。例如说3崩溃了，5只能和{1, 2, 5}取得联系，对应的acceptProposeNum = {1, 2, 3}，根据规则，需要重新一轮二阶段算法，提议那个acceptedProposeNum = 3的VALUE，这个VALUE是unchosen VALUE。

但只要3能够回归，那么3就有在prepare阶段被找到的可能性，那么chosen VALUE就有被issue的可能性；如果新的一轮的accept仍然没能让那些accept了unchosen VALUE的acceptor改变自己的结果，那么只需重来就可以了；从具体到一般，根据结论2我们可知，只要那个持有最大的acceptProposeNum的、accept了chosen VALUE的acceptor能加入，那么它就可能在prepare阶段被联络到，那么proposer就必须采用来自它的chosen VALUE；那么就存在issue新的提案，让那些accept了unchosen VALUE的accpetor改邪归正的可能性；

又根据结论3，选择了chosen VALUE的accpetor不可能改变自己的accept结果，因此只有那些accept了unchosen VALUE的acceptor可能会改变自己的VALUE。如果改变了，那么我们向全体acceptor达成共识又迈进了异步；如果没能改变，只不过是重来一遍而已。

如果你学过马尔科夫链，你会发现最终达成共识这个状态就像一个吸收态。

参考资料

[1] Paxos Made Simple；Lamport大仙对paxos的（一点也不）通俗解释
[2] //zh.wikipedia.org/wiki/Paxos算法#算法 ；关于paxos的wikipedia，基本上是《Paxos Made Simple》的简中翻译；
[3] //zhuanlan.zhihu.com/p/220311761 ；从中理解到共识（consensus）的含义即可；
[4] //www.youtube.com/watch?v=JEpsBg0AO6o ；Raft作者 Diego Ongaro 对 basic-paxos 和 multi-paxos 的讲解，强烈推荐；
[5] //zhuanlan.zhihu.com/p/260204158 ；可以看做是对上述视频内容的简中翻译；