一致性问题要求多个process对一个值达成一致。基于消息传递的分布式系统中，在不考虑消息篡改等拜占庭错误的情况下，Paxos可以解决在进程退出，消息延迟，丢失，重复等异常发生的环境中对某个值达成一致的问题。
考虑Paxos最基本的形式：
两个角色：Proposer和Acceptor，Proposer提出Value(决议值)，Acceptor处理是否Accept Value
两个阶段：Prepare和Propose，第一阶段Prepare用于确认第二阶段的Value，第二个阶段Proposer请求Acceptor Accept Value
每个参与Paxos协议的server可以同时担任两个角色。当一个Value被majority的server Accept，则这个Value达成一致。
Acceptor的状态：MaxAcceptRoundNumber，Accept的最大的轮次号，MaxPrepareRoundNumber，Promise(回复PrepareReq OK)的最大的轮次号
算法
Prepare阶段：
Proposer给所有Acceptor发送PrepareReq(RoundNumber)请求，
如果Acceptor的max(MaxAcceptRoundNumber, MaxPrepareRoundNumber)大于RoundNumber，则拒绝PrepareReq(RoundNumber)。Proposer接收到拒绝请求，直接选择一个新的round number，进入下一轮的Prepare阶段。
如果Acceptor的max(MaxAcceptRoundNumber, MaxPrepareRoundNumber)小于RoundNumber，则Promise该PrepareReq(RoundNumber)，并且发送PrepareRes(MaxAcceptRoundNumber,Value)给Proposer。
Accept阶段：
Proposer接收到了majority的Acceptor的PrepareRes(MaxAcceptRoundNumber,Value)后，从所有接收到的PrepareRes中选出最大的MaxAcceptRoundNumber
对应的Value，然后发送AcceptReq(RoundNumber,Value)给所有的Acceptor。Accept接收到AcceptReq (RoundNumber,Value)后，如果max(MaxAcceptRoundNumber, MaxPrepareRoundNumber) 大于RoundNumber，则拒绝AcceptReq(RoundNumber,Value)，否则Accept AcceptReq(RoundNumber,Value)。如果Proposer接收到majority的Acceptor回复没有Accept过任何AcceptReq，则Proposer任意选择一个Value，并且给所有的Acceptor发送AcceptReq(RoundNumber,Value)。
轮和轮之间是并行的。每一轮都有一个coordinator，即发送proposal的server。
算法的正确性的证明关键在于证明：
如果有AcceptReq(m,Vm) 第一次被majority的Acceptor Accept，则对于AcceptReq(j, Vj)，j > m -> Vj=Vm
证明
数学归纳法：
- 对于j = m, 显然Vj=Vm
- 假设j = k, k > m，有Vk = Vm，即第[m,k]轮AcceptReq(j, Vj) 都有Vj=Vm 。只需要证明j = k+1,有Vk+1=Vm
i用来索引Acceptor
显然第k+1轮能够发出AcceptReq(k+1,Vk+1)，说明第k+1轮成功的收到了majority的PrepareRes(Xi, Vxi)，由于Prepare阶段的限制，显然xi < k+1,即xi <= k，从而max(Xi) <= k。由于Accept阶段的限制，只能Accept比本地已经Accept的Req更大的，由于m已经被majority Accept了，故至少有一个PrepareRes(Xi,Vxi)中的Xi >= m, 从而max(Xi) >=m
综上所述有,对于第k+1轮来说，有 m <= max(Xi)<= k，又由于h ∈[m,k]轮的所有的AcceptReq(h,Vh)都有Vh=m(数学归纳法的假设)，即第h轮收集到的PrepareRes中最大的AcceptRoundNumber对应的value(即 Vh)是m，故AcceptReq(k+1, Vk+1)的Vk+1=Vm ,得证。
参考文献