paxos算法学习.docx

取名 Paxos（Greek: ,pronouncedPaksi in English）又名Paxi是希腊西南部一个风景如画的小岛。而Paxos算法则是现在很火的分布式一致性算法，为何以一个希腊小岛名字算法？Lamport这样解释道：I thought, and still think, that Paxos is an important algorithm. Inspired by my success at popularizing the consensus problem by describing it with Byzantine generals, I decided to cast the algorithm in terms of a parliament on an ancient Greek island. Leo Guibas suggested the namePaxosfor the island.为描述 Paxos 算法，Lamport 虚拟了一个叫做 Paxos 的希腊城邦，这个岛按照议会民主制的政治模式制订法律，但是没有人愿意将自己的全部时间和精力放在这种事情上。所以无论是议员，议长或者传递纸条的服务员 都不能承诺别人需要时一定会出现，也无法承诺批准决议或者传递消息的时间。但是这里假设没有拜占庭将军问题（Byzantine failure，即虽然有可能一个消息被传递了两次，但是绝对不会出现错误的消息）；只要等待足够的时间，消息就会被传到。另外，Paxos 岛上的议员是不会反对其他议员提出的决议的1。背景 Paxos算法是莱斯利兰伯特（Leslie Lamport，就是LaTeX中的La，此人现在在微软研究院） 于1990年提出的一种基于消息传递的一致性算法。由于算法难以理解起初并没有引起人们的重视，使Lamport在八年后重新发表到TOCS上2。即 便如此paxos算法还是没有得到重视，2001年Lamport用可读性比较强的叙述性语言给出算法描述3。可见Lamport对paxos算法情 有独钟。近几年paxos算法的普遍使用也证明它在分布式一致性算法中的重要地位。06年google的三篇论文初现“云”的端倪，其中的chubby锁 服务使用paxos作为chubby cell中的一致性算法，paxos的人气从此一路狂飙。Paxos是什么？ Paxos 算法是分布式一致性算法用来解决一个分布式系统如何就某个值(决议)达成一致的问题。一个典型的场景是，在一个分布式数据库系统中，如果各节点的初始状态 一致，每个节点都执行相同的操作序列，那么他们最后能得到一个一致的状态1。为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个一致性 算法以保证每个节点看到的指令一致。这里想提一下一些中文的paxos算法理解的文章中用分布式系统竞争锁的场景作例子介绍paxos算法的过程，就我 个人感觉不是很合适，因为paxos算法是一个较高效的一致性算法，和传统的分布式锁算法还是不太一样的，比如RA算法，它和单机上的加锁解锁有一个最大 的共同点就是有很明显的“请求-等待”的过程，而paxos算法每一个实例之间相对独立，选举过程可以平行执行，后发生的实例是可以再先发生的实例之前 表决的，并没有明显的“请求-等待”的感觉。在具体的应用时，分布式锁算法更多的是“互斥”的感觉，一致性算法更多的是“同步”的感觉。Paxos适合什么场合？ 参考转载的Paxos算法在大型系统中常见的应用场景，在chubby中paxos用于保持chubby cell内部所有主机操作序列的一致性，同时也用于选举出chubby cell中的master或者说是leader。Paxos的实现？ chubby中有paxos的具体实现可惜看不到代码，表现形式也不确定，可能是以库的形式提供也可能散布在程序的很多地方。现在手里能拿到的一个是 sourceforge上的开源库libpaxos，作者是一位意大利的帅小伙Marco。和Marco交流后发现他对paxos的理解确实挺深的。虽然 libpaxos现在还没得到商用，但感觉还是挺有前途的；另一个实现是在北大天网实验室的类chubby实现-debby，是使用ICE现实的，看 过之后总觉得有些不太通顺的地方，似乎代码的实现并没有严格遵循paxos算法（很可能是本人水平不足，没看出其中的玄机）；还有一个是Diskless Paxos的实现，不使用disk保存状态怎么实现各个角色的“可重启”呢？还没时间研究，应该还是挺有意思的；除了这些，在google code上有paxos的java实现，BerkeleyDB的复制也有使用了paxos算法。在本系列的后续文章中将重点介绍对其中一些实现的理解，以 及给libpaxos做跨windows平台移植遇到的问题。关于本学习笔记 Paxos算法学习笔记系列文章记录了本人这半年多对paxos学习和应用的一些理解，因水平有限可能有很多理解上的错误，欢迎大家批评！在此要感谢Marco的帮助，感谢川大智胜胡术老师及其带领的空管部网络组的支持。后续：“分布式一致性Paxos算法学习笔记（二）：算法详解”Reference1维基百科，Paxos算法：/wiki/Paxos算法#.E9.97.AE.E9.A2.98.E5.92.8C.E5.81.87.E8.AE.BE2Lamport, The part-time parliament, ACM Transactions on Computer Systems 16(2):133-169, 19983Lamport, Paxos made simple, SIGACT News 32(4):18-25, 2001.分布式一致性Paxos算法学习笔记（二）：算法详解 阅读本文前最好能先阅读参考文献2。最近在写毕业论文，导致这边学习笔记也写得很生硬. 大家轻拍。文章为本人对paxos算法(basic paxos)的理解，水平有限难免有理解不到位的地方，欢迎批评。 一、简介1.1Paxos算法处理的问题 Paxos 算法解决的问题是一个分布式系统如何就某个值(决议)达成一致。一个典型的场景是，在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点都执行 相同的操作序列，那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列，需要在每一条指令上执行一致性算法以保证每个节点看到的指令 一致。节点通信存在两种模型：共享内存（Shared memory）和消息传递（Messages passing）。Paxos 算法就是一种基于消息传递模型的一致性算法1。1.2算法简介及一致性问题场景 为描述 Paxos 算法，Lamport 虚拟了一个叫做 Paxos 的希腊城邦，这个岛按照议会民主制的政治模式制订法律，但是没有人愿意将自己的全部时间和精力放在这种事情上。所以无论是议员，议长或者传递纸条的服务员 都不能承诺别人需要时一定会出现，也无法承诺批准决议或者传递消息的时间。但是这里假设没有拜占庭将军问题（Byzantine failure，即虽然有可能一个消息被传递了两次，但是绝对不会出现错误的消息）；只要等待足够的时间，消息就会被传到。另外，Paxos 岛上的议员是不会反对其他议员提出的决议的1。 对应于分布式系统，议员对应于各个节点，制定的法律对应于系统的状态。各个节点需要进入一个一致的状态，例如在独立Cache的对称多处理器系统中，各 个处理器读内存的某个字节时，必须读到同样的一个值，否则系统就违背了一致性的要求。一致性要求对应于法律条文只能有一个版本。议员和服务员的不确定性对 应于节点和消息传递通道的不可靠性1。 场景一：C/S模式的冗余备份的系统，C=C1,C2,C3,.,Cn代表n个客户端，S= S1,S2,S3,.,Sm代表m个服务器。在这样的冗余系统中要完成这样的任务：让任何一个Cx提出的请求(提交的数据)，能在这m 个服务器上都执行(保存)一遍，最终所有的服务器达到一个一致的状态（也就是说每个server相当于一个“replica”，而外部看来似乎只有一个 server提够服务，这样设计主要是为了容灾考虑）。这时问题就产生了，由于client与server、server与server之间是用网络连接 的，则由网络协议带来的不可靠、不确定性将会影响这m个server到达一个一致状态。例如：C1、C2先后提出请求，C1要求更新value1，C2要 求删除value1。由于网络的不确定，这两个请求到达server的顺序可能是 S1（requestC1，requestC2），S2（requestC2、requestC1）.等等，使得操作序列在m个服务器可能各不相 同，如果S中的每一个server执行了不同的合法操作序列，将会导致整个系统的不一致问题，所以一致性算法的任务就是保证S中每个处于正常工作的 server都将执行一个相同的操作序列，如（requestC1、requestC2）。C/S模式的冗余备份 系统常常有两种形式：1.每一个client和所有的server连接（如图1）。2.所有的client和一个server连接（相当于server中 的leader），再由这个leader与其他冗余server连接。不管是那种形式都会受到网络不确定性的影响从而产生操作序列不一致问题。 场景二：系统中各节点是对等关系，互为client/server,当一节点发生改变时，其他所有节点也要发生相同的改变。比如在ATC（空中交通管制 系统）中有五台供管制员使用的席位(即五台主机)，在实际应用中会遇到这样的情况：管制员G1在席位1对参数value1做相应的操作，而几乎同时管制员 G2在席位2上也对value1做操作。由于网络传输的不确定性可能会导致这五台主机最终的显示结果不尽相同，产生不一致性的问题。paxos算法就是用 来解决这类问题。二、算法详解2.1一致性算法 一个一致性算法需要保证：一次选举中只批准一个决议(value)，只有被提出(proposed)的决议才能被批准，只有已经被批准的决议才能被学习 (即可以执行或保存这个决定的内容)。Paxos算法为了完成这样的选举过程将参与者分为：proposers，acceptors，和 posers 提出决议，acceptors 批准决议，learners“学习”决议。划分为三类角色后，一致性算法的要求可以更精确的表述为：1.决议（value）只有在被 proposers 提出后才能批准（未经批准的决议称为“提案（proposal）”）；2.在一次 Paxos 算法的执行实例中，只批准一个 Value；3.learners 只能获得被批准（chosen）的 Value。 这样的表述看似简单，但实际的证明过程还是很复杂的，而在三条中最为重要的是第二条作者Lamport在Paxos made simple2中花大量的篇幅来加强第二条的约束，从而总结出一个paxos实例的两个阶段及三类角色各自的工作。如何保证在一个paxos中只选出 一个value的推导过程建议阅读原文或Fastpaxos3的The Basic Algorithm章节尤其在注意Picking a Value in Phase 2a，在本学习笔记后续文章中有较为工程化的描述，可能比较好理解一些。 分布式领域的许多算法由于先决条件过于苛刻导致工程实现上的困难，相比较而言Paxos算法的先决条件要弱很多。as follow：（1）.Paxos算法应当执行在一个可靠的通讯环境中，即在异步通讯过 程中不会出现被篡改的情况(non-Byzantine model)，但允许发送的数据出现丢失、延迟、重复的情况。则个角色可工作在任意速度、允许停止和重启的错误。可重启(restart)性质就要求各角 色随时保存自己的当前状态，换句话说就是要把状态写入硬盘，所以在Paxos算法学习笔记（一）中提到的diskles paxos让我很疑惑，有时间在研究。（2）.任何一个算法的运行实体不会出现拜占庭将军问题4，可以简单的理解为结点群的决议序列没有受到病毒、黑客的影响。2.2算法的内容 一个Paxos算法执行实例只能批准一个决议(value)，以下描述的算法内容都是指在一个paxos实例中。 可以这样理解：现在有C1、C2要提出保存key1、key2两数据的请求，他们分别向server结点群发出请求，server结点群可以由一个 leader(也可以是结点群中每一个server)负责处理这两个请求然后发起两个paxos执行实例，也就是提出两个不同的决议(value)，待 acceptors进行表决。这两个paxos实例是相互独立的，它们分别独立的执行paxos过程(round)的两个阶段，最终两个实例得到通过后，在server结点群的每一台server上按一定顺序保存key1、key2(不一定是按请求到达的顺序)。 理解一个paxos实例只能批准一个决议是很重要的，因为这点非常容易和paxos算法阶段一的“picking a value”3混淆，在看论文的时候也很容易出现理解偏差。 当一个请求到来后，由proposer或leader发起新的paxos执行实例，这时proposer会选择一个“新”的实例id(instance id)用于和别的决议(value)进行区分，使得这个提案能独立的进行paxos round。前面提到的“新”实例id，之所以新字用引号是因为这个实例id可能已经被别的proposer使用。如果这个id已经被别的 proposer使用(这种情况不是可以通过crnd来判断，)，那么一个paxos实例中就有两个value进行表决，这与一致性算法的第二条要求有冲突，为了保证一致性算法的性质，paxos 算法的第一阶段才有了一个叫“picking a value”的过程。对于同一个paxos实例来说执行多少次都只会“pick”相同的value，以证第二条要求。2.2.1通过一个决议 新的paxos执行实例发起后，接下来就是执行paxos算法，算法每执行一遍叫一个paxos过程(paoxs round)，一个value的批准可能经历多个paxos过程。下面是paxos算法的具体过程，或者说是一个paxos round的执行过程。proposer 提出一个提案前，首先要和足以形成多数派的 acceptors 进行通信，获得他们进行的最近一次批准活动的编号（prepare 过程），之后根据回收的信息决定这次提案的 value，形成提案开始投票。当获得多数 acceptors 批准后，提案获得通过，由 proposer 将这个消息告知 learner。这个简略的过程经过进一步细化后就形成了 Paxos 算法：通过一个决议分为两个阶段1：Phase1.准备阶段： (a)proposer 选择一个提案编号 n 并将 prepare 请求发送给 acceptors 中的一个多数派； (b)acceptor 收到 prepare 消息后，如果提案的编号大于它已经回复的所有 prepare 消息，则 acceptor 将自己上次的批准回复给 proposer， 并承诺不再批准小于 n 的提案；Phase2. 批准阶段： (a)当一个 proposor 收到了多数 acceptors 对 prepare 的回复后，就进入批准阶段。它要向回复 prepare 请求的acceptors 发送 accept 请 求，包括编号 n 和根据 P2c 决定的 value（如果根据 P2c 没有决定 value，那么它可以自由决定 value）。（为什么要将批准过的值返还给proposor） (b)在不违背自己向其他 proposer 的承诺的前提下，acceptor 收到 accept 请求后即批准这个请求。这个过程在任何时候中断都可以保证正确性。例如如果一个 proposer 发现已经有其他 proposers 提出了编号更高的提案，则有必要中断这个过程。因此为了优化，在上述 prepare 过程中，如果一个 acceptor 发现存在一个更高编号的草案，则需要通知 proposer，提醒其中断这次提案。两阶段的消息传递过程可由下图表示5：Message flow: Basic Paxos(one instance, one successful round) Client Proposer Acceptor Learner | | | | | | | X-| | | | | | Request | X-|-|-| | | Prepare(N) | |-|-| | | Accept!(N,Vn) | |-| Accepted(N,Vn) | | | | | | Request | X-|-|-| | | Prepare(N) | |-|-| | | Accept!(N,Vn) | |-| Accepted(N,Vn) |0时,fast paxos在文中证明了这样的vval值只有一个）。 If k = 0,P可以任意挑选一个来自client的value作为提案提出 else，将V中的那个唯一的value作为提案提出B、proposer原则 在提案编号为i (rnd = i)的提案没有被大多数acceptor（某quorum）批准之前，若收到某A的Nack【j】或者reject【j】,ji，说明该实例中已经有更改编号的提案发生，应设置crnd = h+M,（提案编号的递增可以自己定义）并重复prepare过程。C、acceptor原则 任何一个acceptor必须批准它收到的第一个value 如果某acceptor在处理某proposer(proposer_id = x)的proposer提出的提案编号为i的提案过程中，收到了来自其他proposer(proposer_id = y)的编号更高的提案消息prepare【j】(ji)，则该acceptor利用reject【j】或者Nack【j】提醒proposer(proposer_id = x)有更高编号的提案发生，中断原有的round i。如果x= y ，即同一个proposesr提出了更高编号的提案消息（prepare【j】），则acceptor接受编号更高j的提案消息(promise【j】)，忽略提案编号为i的提案消息(accept【I,value】)。1.5.2 一个简单提案提出(round)运行流程（不考虑被中断或被忽略） 收到来自客户端的请求 假设proposer_id为1的proposer开始提出一个提案来处理这个来自客户端的请求， 该proposer发出phase 1a 消息，内容至少含有【crnd】,即prepare【11】,自身二元组更新为【11，NULL】。 如果是初始化状态下，则每个acceptor都将原有的三元组结构更新为【11，0，NULL】，表示该acceptor不再处理提案编号小于11的其它提案。并且回复promise【11，NULL】给proposer_id = 1。如果是非初始化状态下(即vval不为NULL)，每个acceptor回复promise【11，vval】给proposer_id = 1，即回复phase 1b消息。 如果该proposer_id收到来自大多数（a quorum of）的acceptor回复的promise消息。它按照1.5.1中pick a value的原则选择适当的value值，记做vval_s，并组成一个内容至少包含【11，vval_s】的accept phase2a消息发给所有的acceptor。并将自身的二元组更新为【11,vval_s】 如果是初始状态，收到accept消息的所有acceptor接受该提案，并发送投票结果给proposer和所有learner。非初始状态，在简单模型下，所有的acceptor接受该提案，并发送结果给proposer和所有learner。将自身的三元组更新为【11，11，vval_s】。 如果某Learner收到来自收到来自大多数（a quorum of）的acceptor的accepted，至少含有【11,vval_s】消息。该learner学习vval_s。1.5.3 考虑中断和忽略根据1.5.1的acceptor的原则可知，一个round有可能被中断和被忽略。现在举例来说明： A、 在1.5.2描述的模型中，如果在步骤到步骤之间，另一个proposer（比如proposer_id = 2,则它的初始化提案编号为12）开始了步骤，传送了一个至少包含【12】的prepare消息，并且由于网络传输的不确定性，【12】比【11】更早的抵达某个acceptor，则当【11】抵达时，由于两个prepare不是由同一个proposer提出，这个acceptor将会显式地拒绝这个prepare消息。并给proposer_id = 1的proposer发送reject【12】（或者nack【12】）消息。则【11】被中断了。(为什么要中断) B、 如果在【11】编号的提案的表决之前，proposer_id = 1的proposer又提出一个新的prepare消息（这是被允许的），这个新提案的编号可能为【21】（本例中，举例新编号的递增差值是M，则11+M = 21）。并且【11】的消息在网络传输中丢失了，那么当某acceptor先收到【12】，再收到【11】时，由于这两个prepare都是由同一个proposer提出，那么该acceptor将直接忽略消息【11】。二、发生活锁如1.5.3所述的情况A所示，如果两个proposer同时提出决议，并且互相中断，将会形成活锁。在参考文献3。三、选举leader为了解决活锁的问题，lamport在fast paxos文章中推荐使用竞争leader的方式来进行算法。在这种情况下，只有确认自己成为了leader的proposer才能开始一个新的提案。就避免了被别人中断的情况发生，从而防止了相互中断形成活锁。四、算法过程的动画演示 在公司做paxos专题的时候做了一个带动画的ppt，演示basic paxos算法的基本过程，感兴趣可以在这里下载。五、后续：“分布式一致性Paxos算法学习笔记（四）：算法回顾” 笔记四将对算法进行一次回顾。References1Leslie Lamport.Fastpaxos. DistributedComputing,19(2):79103,2006.2Leslie Lamport. Paxos made simple.2001,11,13/wiki/Paxos_algorithm声明：Paxos算法学习笔记系列是本人原创，转载请注明出处：/ychellboy以下文字出自小夏同学的论文：2.1.3 Proposer行为分析(1.1) 向所有的Acceptors发送Prepare(N_A)请求；(1.2) 如果收到Reject(N_H)信息，那么重新发送Prepare(N_H+1)；(2.1) 如果收到Acceptors集合的任意一个Majority的Promise(N_A, V_A)回复，那么如果所有的V_A均为空，Proposer自由选取一个V_A，回发Accept(N_A, V_A)；否则回发Accept(N_A, V_i)；(2.2) 如果收到Nack(N_H)，回到(1.1)过程，发送Prepare(N_H+1)；(3.1) 如果收到任意一个Majority所有成员的Accepted信息（表明选举完成），向所有Proposers发送自身成为leader的消息；(3.2) 向Learner发送value值。其中：N_A为该次提案的编号；N_H为当前提案的最高编号；V_i为V_A中提案编号最高的value；2.1.4 Acceptor行为描述(1.1)接收Prepare(N_A)，如果N_AN_H，那么回复Promise(N_A, V_A)，并置N_H=N_A；否则回复Reject(N_H)(2.1)接收Accept(N_A, V_A)，如果N_AN_H，那么回复Nack(N_H)信息（暗示了该Proposer提完案后至少有一个其余的Proposer广播了具有更高编号的提案）；否则设置this.V_A=V_A，并且回复Accepted信息。其中：Promise(N_A, V_A)：向Proposer保证不再接受编号不大于N_H的提案；Accepted向Proposer发送提案被通过信息；V_A为Acceptor之前审批过的提案（允许为空）；N_H为Acceptor之前接收提案的最高编号。2.1.5 Learner行为描述相对来说，Learner的行为理解更简单一些：学习value，开始执行任务。2.1.6 整体描述算法在执行过程中，实例和实例之间是异步的；角色和角色之间既有同步的行为（因为一个完全异步的系统中，一致性问题将是无法被解决的6），又有异步的行为。下表2.1中按照我的理解以全局的角度来说明这其中的关系： 表2.1 一次Paxos实例角色 / 时段Phase 1Phase 2Phase 3Proposer (P)1竞争Leader: 向A发送prepare1接收A的promise2选取一个value并发送accept(*)Acceptor (A)1接收处理P的prepare2回复reject 或promise1接收处理accept2回复accepted或nack3通知L(*)Learner (L)无无1接收广播学习value或2创建Proposer对象学习value分布式一致性Paxos算法学习笔记（四）：算法回顾 这段时间一直在赶论文，唉，真是昏天黑地 在写论文的时候居然把Paxos算法里的提案和决议搞混了！赶紧看blog里是不是也弄错了，还好之前的几篇都没错，这才松了口气。所以决定第四篇笔记对Paxos算法做个回顾。 1. 几个重要的概念 实例(instance)：每一个Paxos的实例都将执行Paxos算法的两个阶段过程，并最终选出唯一的决议(value)。 提案(proposal)：未经批准的决议称为提案，由于在Paxos算法中，每一个Proposer在一个没有关闭(closed，即还没最终选出决 议)的实例中都可以提出自己的提案，因此在一个实例的执行过程中，可能会出现多个提案。而最终只能有一个提案被批准通过，成为该实例的决议 (value)。 决议(value)：被最终批准通过的提案中的value称为决议，一个Paxos实例只能选出一个决议。决议和实例是一一对应的。 2. 两阶段过程 paxos的两阶段过程就不再描述了，有图有真相！如下图： 3. 各角色的行为描述 Learner行为描述： learner的主要任务就是监听来自acceptors的消息，用以最终确认并学习决议 (value)，即被批准的提案。当learner收到来自大多数(majority)acceptors的接受消息后，就可以确定该实例 (instance)的value已经被最终无歧义的确认。这个时候便可以执行决议里的操作。 决议序列在所有learner上顺序都是一致的，每一个提案的发起将会触发一次Paxos过程，每个这样的过程是一个Paxos的实例。而在实际应用中常 使用单增的整数来标识每一个实例，即iid(instance id)。iid从1开始，而所有从1开始到当前iid的实例都必须是已经被确认过的，即这些决议都已经被执行过。比如：learner A已经确认了前10个实例，这时iid为11的决议还没有被通过，而iid为12和13的提案已经得到大多数acceptors的接受。此时就会产生一个 决议序列缺口(gap)，在这种情况下，A不能跳过11直接确认12和13，而是去询问acceptors是否已经通过11的决议。只有当iid为11的 决议被确认后，iid为12和13的决议才能被确认学习。 Acceptor行为描述： acceptor会维护一个状态记录表，表的每一行维护这样四个数据, iid表示实例id。B是一个整数，用来表示同意或接受过的该提案的最高编号。V表示该提案对应的决议，里面保存着客户端发送过来的数据。VB表示已经接 受过的提案的编号。 (Phase 1.b) 接收Prepare(i，b)消息，i为实例id号，b为提案编号。对于同一个i，如果bB，那么回复Promise(i, b, V, VB)，并设B=b；否则，回复Reject(i，b)，其中b=B。 (Phase 2.b) 接收Accept(i, b, v)，如果bB，那么回复Nack(b)信息，其中b=B(暗示该proposer提出提案后至少有一个其它的proposer广播了具有更高编号的提案)；否则设置V=v，VB=b，并且回复Accepted(i，b，v)消息。其中：Promise(i, b, V, VB)表示向proposer保证对于该实例不再接受编号不大于b的相同iid的提案；Accepted表示向learner和proposer发送该提案被通过的消息。 Proposer行为描述： (Phase1.a) 向所有的acceptors发送Prepare(i, b)请求； (Phase2.a) 如果收到Reject(i，b)消息，那么重新发送Prepare(i，b+n)，n为一个整型值，不同的proposer具有不同的n值，使得proposer之间保持一个偏序关系，保证不同的proposer不会使用相同的b值，即提案编号； (Phase2.a) 如果收到acceptors集合的任意一个majority的 Promise(i, b, V, VB)回复，那么如果所有的V均为空，proposer可以自由选取一个v(value)，一般为用户提出的请求，回发Accept(i, b, v)；否则回发Accept(i，b，V)； (Phase2.b) 如果收到Nack(b)，回到(Phase1.a)发送Prepare(i，b+n)； (Phase2.b) 如果收到任意一个majority所有成员的Accepted(i，b，v)消 息(表明投票已经完成)。这个过程learner也能收到Accepted消息，learner查看i是否为当前需要确认的iid，如果是则立即执行这个 被批准的决议v；否则将该Accepted保存下来。 Phase2.b阶段完成后，各个角色上对应该实例的状态都将变为closed状态，即该实例已经选出决议，proposer不能再提出新的提案。这样保 证一个实例只能选出一个决议。在实际应用过程中，为了简化实现，