[Misc] PAXOS 算法 - Gukie/learning GitHub Wiki

refer：

• https://www.cnblogs.com/linbingdong/p/6253479.html (Paxos算法问题)
• https://www.jianshu.com/p/5fea30b25f0a (拜占庭将军问题)

Paxos 算法的角色

• Proposer，提出proposal的node
• Acceptor，接受proposal的node
• Learner， 从Acceptor中学习proposal的node

只有他们三个都达成一致，认定一个 proposal，那个proposal 才算是在分布式环境下被确定为成功落地 主要的思想是：

• 确保发送方提出的proposal是正确的; 这需要通过 半数以上的接收方来决定
• 确保接收方接受到的proposal是正确的; 这需要接收方自己对接受到的proposal进行check

Proposer跟Acceptor交互

阶段一，prepare阶段

• Proposer选择一个编号N的proposal，然后向半数以上的acceptor提交 prepare请求
• 每一个Acceptor接收到编号为N的proposal时，都会检查

• 编号N是否大于 该Acceptor已经响应过的所有的Prepare请求的编号 如果是，该Acceptor就会将已经接受过的编号最大的proposal(如果有的话)返回给proposer，同时承诺不会接受编号小于N的proposal

阶段二，accept 阶段

• 如果Proposer 收到半数以上的Acceptor对其发出的编号为N的prepare请求的响应，那么他就会发送一个包含值的编号为N的accept请求给半数以上的Acceptor. 该请求类似[N,V], 其中N为编号，V为值(如果所有从Acceptor回来的针对prepare的响应都没有值，那么该值由proposer自己定；否则只能是响应中编号最大的那个的value)
• 如果某个Acceptor收到针对编号为N的accept请求，只要改Acceptor没有对编号大于N的prepare请求做个响应，就会接受该proposal

Learner学习被选定的 proposal