一、背景故事

一个发生在名叫Paxos的希腊岛屿上的故事，这个岛屿不存在一个中心化机构，但需要按照民主议会投票制定法律。对应到分布式系统上，议员就是各个节点，制定的法律就是系统的各个状态。每个节点（议员）都可能提出提案（Proposal），Paxos用提案来推动整个算法，使系统决议出同一个提案，提案包括提案编号(Proposal Number)/(Ballot)和提案值(Proposal Value)。
各个节点需要通过消息传递不断提出提案，最终整个系统接受同一个提案，进入一个一致的状态，即对某个提案达成共识。
最终状态：Paxos算法认为，集群中超过半数的节点同意接受该提案，那么对该提案的共识达成，称该提案被批准(Chosen)，也叫被选定。
注：在基本的Paxos算法中，一旦某个提案被批准，提议者都必须将该值作为后续提案值。

二、角色

Paxos算法角色：客户端、提议者、接受者、学习者
客户端：客户端向分布式系统发送一个请求，并等待响应。
提议者(Proposer)：提议者收到客户端的请求，提出相关的提案，试图让接受者接受提案，并在发生冲突时进行协调，推动算法运行。
接受者(Acceptor)：也叫投票者(Voters)，即投票接受或拒绝提议者的提案，若超过半数的接受者接受提案，则该提案被批准。
学习者(Learner)：学习者只能”学习“被批准的提案，不参与决议提案。一旦客户端的请求得到接受者的同意，学习者就可以学习到提案值，执行其中的请求操作并向客户端发送响应。

三、两阶段协议（2-phase)

1.提案编号

为了区分提案的先后顺序，使用提案编号（分布式系统时间戳可能并不准确）——<n, server_id> <轮次，服务器id> 轮次n单调递增，和服务器id组成全局唯一的提案编号。
为了容错性，即让进程在宕机恢复后仍知道当前的提案编号，需在本地持久化存储提案信息。

2.最基本的Paxos算法——Basic Paxos

Basic Paxos主要包括两个阶段，分别对应两轮RPC消息传递，每个阶段都分为ab两个部分，ab部分分别对应RPC的请求阶段和响应阶段。

（1）第一阶段

a. 发送RPC请求的阶段phase 1a, Prepare阶段。

b.响应RPC请求的阶段phase 1b, Promise阶段。

（2）第二阶段

a.发送RPC请求的阶段phase 2a, Accept/Propose阶段.
前提：当提议者收到超过半数的接受者的Promise()响应

接受提案——接受者单独决定，批准提案——满足超过半数接受者接受提案。
承诺、接受、批准区别：承诺是第一阶段Promise，针对提案编号，承诺不再接受小于该提案编号的提案。接受是第二阶段Accept，接受提案值，只跟单独一个接受者有关。批准Chosen是超过半数的接受者接受提案，共同商定的最终提案值。

四、案例

1.情况1：提案已被批准——后提议者会使用上一次的提案值，只修改提案编号
2.情况2：提案未被批准，但后提议者可见——后提议者仍会使用上一次的提案值
注：只要有一个Promise()响应中返回了提案值，就要用它来替换提案值。
3.情况3：提案未被批准，后提议者不可见——后提议者没有收到任何Promise信息，自行决定提案值，最终提案值为后提议者的提案值。

五、活锁

即两个提案者轮流提案，一直处于Perpare阶段
解决方法：即时超时。

六、学习提案

Leslie Lamport在论文中提到，学习提案的方案有一个确定，即每个接受者都将消息转发给每个学习者，需要发送的消息数量=接受者数量*学习者数量。
优化方法有两个方向，一是减少需要接受消息的学习者的数量，二是减少需要发送消息的接受者的数量。
1.减少接收消息的学习者数量
（1）选出一个权威的学习者，接受者只将已接受的消息发送给它，由权威者判断被批准的提案，然后将批准提案转发给剩下的学习者，这种方法消息的数量=接受者的数量+学习者的数量。（类似GFS中副本传递中流水线机制，权威者 = primary chunkserver）。
缺点是权威的学习者宕机，需要选举新的权威，增加算法复杂度。
（2）将消息转发给一部分学习者。增加了权威学习者的容错性。
2.减少发送消息的接受者数量
可以将发送消息的任务交给提议者，由提议者将批准后的消息转发给所有学习者，学习者不需要进行判断接受的哪个是批准值。这样消息的数量=学习者的数量。论文中没有提及这种做法。