Paxos算法详解 The basic algorithm of paxos 网络组：胡术、杨诚、杨铮

角色介绍 P L L P L P L P C(crnd,cval) C(crnd,cval) C(crnd,cval) A(rnd,vrnd,vval) P L C(crnd,cval) A(rnd,vrnd,vval) L P C(crnd,cval) A(rnd,vrnd,vval) L P C(crnd,cval) A(rnd,vrnd,vval) L A(rnd,vrnd,vval) P

P:proposer,也可以是客户端，提交议案。 C:coordinator,协调者， A:acceptor,选举者， L:learner,学习者， A round include two phases: (i)phase 1 (ii)phase 2 crnd:某C开始的rounds中的最高的round number cval:某C在round crnd中提出的value。 rnd:某A参加过的rounds中最高的round number vrnd:某A批准过的rounds中最高的round number vval:某A在round vrnd中批准的value。 Quorum:a majority of the acceptors 所有的消息可能丢失或者延时，但是不会出错。

message Phase 1a:prepare Phase 1b:promise Phase 2a:accept Phase 2b:accepted

1、C要提出一个value并获得批准的过程叫做一个round,它两个阶段：phase1和phase2. 2、C开始某个round i,发送phase 1a[i]给所有的A,如果收到某A的reject[j](j>i),重新发送phase 1a[j+x]（为方便举例，令x = 1）,并设置[crnd = j+1,cval = 0]。 3、Pick a value: 收到来自某quorum的phase 1b[j+1,vrnd,vval]消息回复。令K为来自该quorum消息中所有vrnd的最大值,V为来自该quorum的消息中vrnd = k的消息对应的vval值的集合（当k>0时,fast paxos在文中证明了这样的vval值只有一个）。 If k = 0,C可以任意挑选一个来自P的value作为value_s else，将V中的那个唯一的value作为我们的挑选value_s 将value_s和round number j+1 作为phase 2a的内容发送给所有的A,并设置cval = value_s,若收到某A的Nack[h],h>j，设置crnd = h+1并重复上述prepare过程。否则，若收到来自某quorum的phase2b消息，则说明对该value_s的选举已经完成。

任何一个A必须批准它收到的第一个value。 A在round i的prepare过程(phase 1)收到phase1a: (a)如果i<rnd,且round rnd的C(beginner)不是round i的C’(beginner),即C!=C’，则通知round i的C’拒绝(reject[rnd])它的prepare请求。如果C = C’，则忽略这个prepare请求。(important!) (b)如果i >= rnd,令rnd = i，发送phase 1b消息。 Phase 1b:[ rnd,vrnd,vval] A在round i的phase 2收到phase 2a[i,vval_i]: (a)如果i<rnd, 即C!=C’，则通知round i的C’拒绝(Nack[rnd])它的accept请求。如果C = C’，则忽略这个accept请求。(important!) (b)如果i>=rnd,令rnd = vrnd = i,vval = vval_i,发送phase2b 故而在其它的C开始更高round number的过程时,Round有可能被中断， 。

L receive phase2b from a quorum,then learn value_s Phase2a[1,Value_s] 初始化(round 1) Phase2b Phase2b L receive phase2b from a quorum,then learn value_s A(0,0,null) Phase2a[1,Value_s] C Receive phase1b from a quorum,pick any value proposed by p. Phase1a [ 1] because 1>0 A(1,0,null) P Phase1b[1,0,null] A(1,1,value_s) C(1,value_s) L C(1,null) C(0,null) A(0,0,null) A(1,1,value_s) because 1>0 A(1,0,null) L receive phase2b from a quorum,then learn value_s L P C(0,null) because 1>0 A(1,0,null) A(0,0,null) A(1,1,value_s) L receive phase2b from a quorum,then learn value_s L because 1>0 A(1,0,null) A(1,1,value_s) P C(0,null) A(0,0,null) L L receive phase2b from a quorum,then learn value_s because 1>0 A(1,0,null) A(1,1,value_s) A(0,0,null) P

正常运行(round 2 as an example) A(2,1,value_s) A(1,1,value_s) P A(2,2,value_s) Phase 2b Phase 2b L C(1,value_s) Reject [1] A(1,1,value_s) Phase 1a[2] A(2,1,value_s) Phase 1b[2,1,value_s] A(2,2,value_s) Phase1a[1] Phase 2a[2,value_s] C(2,null) L P C(1,null) C(0,null) A(1,1,value_s) A(2,1,value_s) A(2,2,value_s) L C(0,null) P A(1,1,value_s) A(2,1,value_s) A(2,2,value_s) L A(1,1,value_s) A(2,1,value_s) P A(2,2,value_s)

出现活锁的情况