毕业答辩ppt模板-东南大学.ppt

Paxos算法详解Thebasicalgorithmofpaxos网络组：胡术、杨诚、杨铮,角色介绍,A(rnd,vrnd,vval),A(rnd,vrnd,vval),A(rnd,vrnd,vval),A(rnd,vrnd,vval),A(rnd,vrnd,vval),P,P,P,P,L,L,L,L,C(crnd,cval),C(crnd,cval),C(crnd,cval),P:proposer,也可以是客户端，提交议案。C:coordinator,协调者，A:acceptor,选举者，L:learner,学习者，Aroundincludetwophases:(i)phase1(ii)phase2crnd:某C开始的rounds中的最高的roundnumbercval:某C在roundcrnd中提出的value。rnd:某A参加过的rounds中最高的roundnumbervrnd:某A批准过的rounds中最高的roundnumbervval:某A在roundvrnd中批准的value。Quorum:amajorityoftheacceptors所有的消息可能丢失或者延时，但是不会出错。,message,Phase1a:preparePhase1b:promisePhase2a:acceptPhase2b:accepted,1、C要提出一个value并获得批准的过程叫做一个round,它两个阶段：phase1和phase2.2、C开始某个roundi,发送phase1ai给所有的A,如果收到某A的rejectj(ji),重新发送phase1aj+x（为方便举例，令x=1）,并设置crnd=j+1,cval=0。3、Pickavalue:收到来自某quorum的phase1bj+1,vrnd,vval消息回复。令K为来自该quorum消息中所有vrnd的最大值,V为来自该quorum的消息中vrnd=k的消息对应的vval值的集合（当k0时,fastpaxos在文中证明了这样的vval值只有一个）。Ifk=0,C可以任意挑选一个来自P的value作为value_selse，将V中的那个唯一的value作为我们的挑选value_s将value_s和roundnumberj+1作为phase2a的内容发送给所有的A,并设置cval=value_s,若收到某A的Nackh,hj，设置crnd=h+1并重复上述prepare过程。否则，若收到来自某quorum的phase2b消息，则说明对该value_s的选举已经完成。,任何一个A必须批准它收到的第一个value。A在roundi的prepare过程(phase1)收到phase1a:(a)如果i=rnd,令rnd=i，发送phase1b消息。Phase1b:rnd,vrnd,vvalA在roundi的phase2收到phase2ai,vval_i:(a)如果i=rnd,令rnd=vrnd=i,vval=vval_i,发送phase2b故而在其它的C开始更高roundnumber的过程时,Round有可能被中断，。,CReceivephase1bfromaquorum,pickanyvalueproposedbyp.,C(0,null),初始化(round1),A(0,0,null),A(0,0,null),A(0,0,null),A(0,0,null),A(0,0,null),P,P,P,P,L,L,L,L,C(0,null),C(0,null),C(1,null),Phase1a1,because10A(1,0,null),because10A(1,0,null),because10A(1,0,null),because10A(1,0,null),Phase1b1,0,null,C(1,value_s),A(1,1,value_s),A(1,1,value_s),A(1,1,value_s),A(1,1,value_s),A(1,1,value_s),Phase2b,Phase2b,Lreceivephase2bfromaquorum,thenlearnvalue_s,Lreceivephase2bfromaquorum,thenlearnvalue_s,Lreceivephase2bfromaquorum,thenlearnvalue_s,Lreceivephase2bfromaquorum,thenlearnvalue_s,because10A(1,0,null),Phase2a1,Value_s,正常运行(round2asanexample),A(1,1,value_s),A(1,1,value_s),A(1,1,value_s),A(1,1,value_s),A(1,1,value_s),P,P,P,P,L,L,L,L,C(1,value_s),C(0,null),C(0,null),Phase1a1,Reject1,Phase1a2,Phase1b2,1,value_s,C(1,null),C(2,null),Phase2a2,value_s,Phase2b,Phase2b,A(2,1,value_s),A(2,1,value_s),A(2,1,value_s