Paxos算法简介

Paxos有三个成员：

• Proposer：提案的提出者
• Acceptor：提案的接受者，批准是否同意
• Learner：Accepter告诉Learner哪个提案被选定，那么Learner就学习这个提案的value

生成提案：

1，proposer生成一个提案M_{n，然后向某个Accepter集合成员发送请求，要求该集合中的Accepter做出如下回应，该请求为提案的Prepare请求：}

• 向Proposer保证，不会再批准任何编号小于M_n的提案
• 如果Acceptor已经批准过任何提案，那么就向Proposer反馈已经批准的编号小于M_n但为最大编号的那个提案值。

2，如果Proposers收到了来自半数以上的Acceptor的响应结果，那么就可以产生编号为M_n，值为V_n的提案，这里的V_n有两种情况，第一种是所有响应中编号最大的提案的value，第二种是在此之前Acceptor并没有收到任何提案，所以value的值由Proposer自定。

优化：

问题：在上面的提案生成到批准的过程中，会出现死循环的情况，当Proposer1提出提案m1，Acceptor批准后，在此之前并无提案，需要Proposer1进行value的设置，这时Proposer2发出提案m2，因为m2的编号大于m1，所以Acceptor批准提案，然后Proposer2设置value，这时Proposer1设置好value后，发现提案已经改变，不会接受小于m2的提案，于是Proposer1继发出m3提案，然后进入上面的循环。

方案：选举出一个主Proposer，所有的提案由主Proposer进行发出，这样就可以避免上述中的循环

为什么半数以上的成员同意就可以认为是一致性：

这里用到了数学上的数学归纳法，当一个集合S，有两个自己和S1和S2，两个子集合都和有半数以上的元素，那么两个子集合的交集必定包含一个公共元素，那么保证这个公共元素的不变性，也就保证了所有的一致性。

Paxos算法简介

原文：https://www.cnblogs.com/codingLiu/p/12726194.html