<分布式协议与算法实战> Paxos 算法两个部分的课后评论太多了，暂时没看完。
基本介绍
Paxos 算法是第一个被证明完备的分布式系统共识算法。
兰伯特当时提出的 Paxos 算法主要包含 2 个部分:
- Basic Paxos 算法：描述的是多节点之间如何就某个值(提案 Value)达成共识。
- Multi-Paxos 思想：描述的是执行多个 Basic Paxos 实例，就一系列值达成共识。Multi-Paxos 说白了就是执行多次 Basic Paxos ，核心还是 Basic Paxos。
当前最常用的一些共识算法，如 ZAB 协议、Raft 算法、Fast Paxos 算法都是基于 Paxos 算法改进的。
Basic Paxos 算法
Basic Paxos 中存在 3 个重要的角色：
- 提议者(Proposer)：也可以叫做协调者(coordinator)，提议者负责接受客户端的请求并发起提案。提案信息通常包括提案编号 (Proposal ID) 和提议的值 (Value)。
- 接受者(Acceptor)：也可以叫做投票员(voter)，负责对提议者的提案进行投票，同时需要记住自己的投票历史；
- 学习者(Learner)：如果有超过半数接受者就某个提议达成了共识，那么学习者就需要接受这个提议，并就该提议作出运算，然后将运算结果返回给客户端。
在 Basic Paxos 中，一个节点可以身兼多个角色，比如同时作为提议者和接受者。
Basic Paxos 达到共识的方式：一个提案被选定需要被半数以上的 Acceptor 接受。
Basic Paxos 达到共识的过程：
- 提议阶段
- 提议者：提出某个提案 <提案ID，value>，发送给接受者。发送时，只发送提案 ID 即可。
- 接受者：初始化时没有提案，返回无提案；如果当前有提案，若自身收到的最大提案 ID 小于新提案 ID，发送当前节点历史收到过的最大提案 ID (不包括当前提案)，否则拒绝提案。
- 接受阶段
- 提议者：当较多数接受者都可以接受提案时，将 <提案ID，value> 发送给接受者
- 接受者：接受提案内容时，会再次进行提案 ID 比较，可以接受则赋值，否则拒绝。
Basic Paxos 的缺点：
- 如果多个提议者同时提交提案，可能出现因为提案编号冲突，在准备阶段没有大多数通过，协商失败，需要重新协商。
- 2 轮 RPC 通讯(准备阶段和接受阶段) 往返消息多、耗性能、延迟大。
Multi Paxos 思想
Basic Paxos 算法的仅能就单个值达成共识，为了能够对一系列的值达成共识，我们需要用到 Multi Paxos 思想。
- 引入领导者节点，全部由领导者节点提交提案，从而不会出现提案冲突情况。
- 优化两阶段，当领导者处于稳定状态时，省掉准备阶段，直接进入接受阶段。
由于兰伯特提到的 Multi-Paxos 思想缺少代码实现的必要细节(比如怎么选举领导者)，所以在理解和实现上比较困难。但是可以学习 Raft 算法，来理解 Multi-Paxos 的思想。
扩展问题
案例分析
假设有 ABC 三个节点。客户端甲发起提案 <编号1，值1>，AB 节点收到提案，返回历史无提案，客户端甲进入接受阶段。此时，客户端乙发起提案 <编号2，值2>，BC 收到提案，B 返回历史最大提案 1，C 返回历史无提案，客户端乙也进入接受阶段。两个接受阶段后，A 节点值为 1，BC 节点值为 2，数据不一致。
这种情况属于一个异常情况，与实现有关，也是 Basic Paxos 没有约定的，在实现中，客户端重试就可以了。其实，异常情况(比如网络连接失败)虽然会肯定发生，但概率低，持续时间很短，“失败 - 缓存 - 重试”是一种很好的解决办法。
客户端的提案号如何生成
论文提到了思路，独立、递增、存储在可靠性设备中。具体细节实现，可以参考 Hashicorp Raft 的 CurrentTerm 的实现 Raft.setCurrentTerm()、raftState.getCurrentTerm()、raftState.setCurrentTerm()，原子、递增、持久存储。