Paxos算法深入分析.docx

Paxos算法深入分析
夏超伦，盛浩，刘森一算法背景问题分析2
Paxos算法处理的问题2



NZ1：某个决议v被批准后，接下来(a)没有任何提案被接受；或者(b)只有包含决议
v的提案被接受。其中：
提案(proposal)：—个有序对V编号，决议>
决议(value)：—个整数
提案被接受：某一个Acceptor向该提案的Proposer发出Accepted信息，并将该提案包含的value加入自己的V_A(list)
决议被批准：含有该决议的提案被Acceptors集合中的任意一个Majority的所有成员接受
Majority：VM(S,2|M|>|S|，例如S=(A,B,C,D,E),其中(A,B,C),(A,C,D)都是majority,而(A,B)不是；通过反证法可以证明S的任意两个majority的交都不为空，即不会存在两个提案被两个完全不同的majority各自批准的非法场景。
PMMgS,假设MeM=0,即|McM|=O。
那么\MiuM|=网|+网|一网c物|=网|+网|一0>\S\o
由于M’MgS,必然有M2M,gS，得\M^M\j<\S\f与假设矛盾，故前提假设不成立。
Proposer行为分析
向所有的Acceptors发送Prepare(N_A)请求；
如果收到Reject(N_H)信息，那么重新发送Prepare(N_H+l)；
如果收到Acceptors集合的任意一个Majority的Promise(N_A,V_A)回复，那么如果所有的V_A均为空,Proposer自由选取一个V_A',回发Accept(N_A,V_A')；否则回发Accept(N_A,V_i)；
如果收到Nack(N_H),回到()过程，发送Prepare(N_H+l)；
如果收到任意一个Majority所有成员的Accepted信息(表明选举完成)，向所有Proposers发送自身成为leader的消息；
向Learner发送value值。其中：
N_A为该次提案的编号；
N_H为当前提案的最高编号；
V_i为V_A中提案编号最高的value；Acceptor行为描述
接收Prepare(N_A),如果N_A>N_H,那么回复Promise(N_A,V_A),并置N_H=N_A；否则回复Reject(N_H)
接收Accept(N_A,V_A),如果N_AvN_H,那么回复Nack(N_H)信息(暗示了该Proposer提完案后至少有一个其余的Proposer广播了具有更高编号的提案)；=V_A,并且回复Accepted信息。其中：
Promise(N_A,V_A)：向Proposer保证不再接受编号不大于N_H的提案；
Accepted向Proposer发送决议被通过信息；
V_A为Acceptor之前审批过的决议(允许为空)；
N_H为Acceptor之前接收提案的最高编号。
Learner行为描述
相对来说，Learner的行为理解更简单一些：学习value,开始执行任务。

算法在执行过程中，实例和实例之间是异步的；角色和角色之间既有同步的行为（因为一个完全异步的系统中，一致性问题将是无法被解决的［6］）,乂有异步的行为。：
—次Paxos实例
角色/时段
Phase1
Phase2
Phase3
Proposer(P)
［1］竞争Leader:向A发送prepare
［1］接收A的promise
［2］选取一个value并发送accept
(*)
Acceptor(A)
［1］接收处理p的prepare
［2］回复reject或promise
［1］接收处理accept⑵回复accepted或nack
［3］通知L
(*)
Learner(L)
无
无
［11接收广播学习value或
［2］创建Proposer对象学习value

该算法巧妙之处在于利用了Majority机制保证了2F+1的容错能力，即具备2F+1个结点的系统最多允许F个结点同时出现故障，并且通过数学归纳的思想步步保障Majority机制。并且从概率上展示了出现错误（无限循环竞争）的极小可能性。
，更详细的代码请见［3］。
PaxosPhase1//proposer状态
anode(maybemorethanone