概念与定义
先明确一些定义：
- Quorum：在 Classic Paxos 中一直通过多数派（Majority）来保证算法的正确性，对多数派再进一步抽象化，称为“Quorum”，要求任意两个 Quorum 之间有交集（从而间接表达了 majority 的含义）。
- Round：在 Classic Paxos 中，提议者每次提案都用一个全序的编号表示，如果执行顺利，该编号的 Proposal 在经历 Phase1，Phase2 后最终会执行成功。在 Fast Paxos 称这个带编号的 Proposal 的执行过程为“Round”。
- i-Quorum：在 Classic Paxos 执行过程中，一般不会明确区分每次 Round 执行的 Quorum，虽然也可以为每个 Round 指定一个 Quorum。在 Fast Paxos 中会通过 i-Quorum 明确指定 Round i 需要的 Quorum。
- Classic Round：执行 Classic Paxos 的 Round 称为 Classic Round。
- Fast Round：如果领导者发送了 Any 消息，则认为后续通信是一个快速回合；若领导者未发送 Any 消息，还是跟之前一样通信，则后续行为仍然是 Classic Round。根据 Lamport 描述，Classic Round 和快速回合可通过 Round Number 进行加以区分。
Classic Paxos
参与角色
从一般的 Client/Server 来考虑，Client 其实承担了提议者和 Learner 的作用，而 Server 则扮演接受者的角色，因此下面重新描述了 Paxos 算法中的几个角色：
- Client/提议者/Learner：负责提案并执行提案。
- Coordinator：提议者的协调者，可为多个，Client 通过 Coordinator 进行提案。
- 领导者：在众多的 Coordinator 中指定一个作为领导者。
- 接受者：负责对 Proposal 进行投票表决。
算法流程
- Phase 1a： 领导者提交 proposal 到接受者
- Phase 2b：接受者回应已经参与投票的最大提议者编号和选择的值
- Phase 2a：领导者收集接受者的返回值
- Phase 2a.1：如果接受者无返回值，则自由决定一个
- Phase 2a.2：如果有返回值，则选择提议者编号最大的一个
- Phase 2b：接受者把表决结果发送到 Learner
Fast Paxos
很明显，在 Phase2a.1 中，如果领导者可以自由决定一个值，则可以让提议者提交这个值，自己则退出通信过程。只要之后的过程运行正常，领导者始终不参与通信，一直有提议者直接提交值到接受者，从而把 Classic Paxos 的三阶段通信减少为两阶段，这便是 Fast Paxos 的由来。因此，我们形式化下 Fast Paxos 的几个阶段：
- Phase1a：领导者提交提议到接受者
- Phase1b：接受者回应已经参与投票的最大提议者编号和选择的值
- Phase2a：领导者收集接受者的返回值
- Phase2a.1：如果接受者无返回值，则发送一个 Any 消息给接受者，之后接受者便等待提议者提交值
- Phase2a.2：如果有返回值，则根据规则选取一个
- Phase2b：接受者把表决结果发送到学习者（包括领导者）
any 消息
在正常情况下，Leader 若可以自由决定一个值，应该发生一条 Phase2a 消息，其中包含了选择的值，但此时却发送了一条无值的 Any 消息。接受者在接收到 Any 消息后可做一些开始快速回合的初始化工作，等待提议者提交真正的值。Any 消息的意思是接受者可以做任意的处理。
因此，一个快速回合包括两个阶段：由 Any 消息开始的阶段和由提议者提交值的结束阶段，而 Leader 只是起到一个初始化过程的作用，如果没有错误发生，Leader 将退出之后的通信中过程。
冲突
在 Classic Paxos 中，接受者投票的 value 都是 Leader 选择好的，所以不存在同一 Round 中投票多个值的场景，从而保证了一致性。但在快速回合中因为允许多个提议者同时提交不同的值到接受者，这将导致在快速回合中没有任何 value 被作为最终决议，这也称为“冲突”（Collision） 。
提议者提交的回合编号是全序的，不同的提议者提交的回合编号肯定不一样，同一提议者不可能在同一回合中提交不同的值，那为什么还会有同一快速回合中有多个值的情况？原因在于快速回合与经典回合区别，当快速回合开始后，会被分配一个唯一的 Round Number，之后无论多少个提议者提交值都是基于这个 Round Number，而不管提议者提交的 Round 是否全序。比如，快速回合编号为 10，提议者 1 提交了（11，1），提议者 2 提交了（12，2），但对快速回合来说存在（10，1，2）两个值。
因为冲突的存在，会导致 Phase2a.2 的选择非常困难，原因是：
在 Classic Paxos 中，如果接受者返回多个值，只要排序，选择最高的编号对应的值即可，因为 Classic Paxos 中的值都是由 Leader 选择后在 Phase2a 中发送的，因此最高编号的值肯定只有一个。但在 Fast Paxos 中，最高编号的值会发现多个，比如（10，1，2）。假如当前 Leader 正在执行第 i 个 Classic Round(i-Quorum 为 Q) ，得到接受者反馈的最高编号为 k，有两个 value：v、w，说明快速回合 k 存在两个 k-Quorum，Rv,Rw。
这里有一个 O4(v)算法。
O4(v)法
下面定义在 Round k 中 v 或 w 被选择的条件：
如果 v 在 Round k 中被选择，那么存在一个 k-Quorum R，使得对任意的 Acceptor a∈Q∩R，都对 v 作出投票。
这个问题也可表述为：R 中的所有 Acceptor 都对 v 作出投票，并且 \(Q \cup R \ne \phi\)，因为如果 Q∩R=φ，则 Round i 将无法得知投票结果。
因此如果保证下面两个条件：
- 每个 Acceptor 在同一 Fast Round 中仅投票一个 Value
- \(Q \cap R_v \cap R_w \ne \emptyset\)
则 v、w 不可能同时被选择。
换言之：
- Quorum 的概念相当于多数派的抽象化，也就是达成一致的 Acceptor 的集合。
- 进入 Fast Round 之后相当于确定了一个 Round Number，接下来发送到 Acceptor 的 Proposal 都被归纳到这个 Round-Number 之下。
- 第 2 句话的含义是，Round-Number 的产生是一次 Accept 的结果，也就有一个对应的 Quorum（假设为 Quorum-Q)。
- 进而从这个 Quorum-Q 中去分析，得到一个 Quorum-R,它的条件是 R 中的所有 Acceptor 都对同一个 value 作出投票。
确定 Quorum
根据上面描述，为了防止一次 Fast Round 选择多个 Value，Quorum 需要满足下面两个条件：
- 任意两个 Classic Quorum 有交集
- 任意一个 Classic Quorum 与任意两个 Fast Quorum 有交集
不妨设总 Acceptor 数为 N，Classic Round 运行的最大失败 Acceptor 数为 F，Fast Round 允许的失败数为 E，即 N-F 构成 Classic Round 的一个 Quorum，N-E 构成 Fast Round 的一个 Quorum。
上面两个条件等价于：
- N>2F
- N>2E+F
设 Qc，Qf 分别为 Classic Round 和 Fast Round 的 Quorum 大小，经过整理可得两个下限结果：
- |Qc| = |Qf| ≥ N - ⌈N/3⌉ + 1 ≥ ⌊2N/3⌋ + 1
- |Qc| ≥N-⌈N/2⌉+1 = ⌈N/2⌉+1
- |Qf|≥N-⌈N/4⌉≥⌈3N/4⌉
证明请参考：一致性算法中的节点下限。
冲突恢复
作为优化，Acceptor 在投票 Value 时也应该发送到 Leader，这样 Leader 就很容易能发现冲突。Leader 如果在 Round i 发现冲突，可以很容易地开始 Round i+1，从 Phase1a 开始重新执行 Classic Paxos 过程。
但这个其实可以进一步优化，我们首先考虑下面这个事实：如果 Leader 重启了 Round i+1，并且收到了 i-Quorum 个 Acceptor 发送的 Phase1b 消息，则该消息明确了两件事情：
- 报告 Acceptor a 参与投票的最大 Round 和对应的 Value
- 承诺不会对小于 i+1 的 Round 作出投票
假如 Acceptor a 也参与了 Round i 的投票，则 a 的 Phase1b 消息同样明确了上述两件事情，并且会把对应的 Round，Value 在 Phase2b 中发送给 Leader（当然还有 Learner），一旦 Acceptor a 执行了 Phase2b，则也同时表明 a 将不会再对小于 i+1 的 Round 进行投票。
也就是说，Round i 的 Phase2b 与 Round i+1 的 Phase1b 有同样的含义，也暗含着如果 Leader 收到了 Round i 的 Phase2b，则可直接开始 Round i+1 的 Phase2a。
经过整理，产生了一种解决冲突（Recovery）方法：
如果 Leader 在 Round i 中收到了（i+1)-Quorum 个 Acceptor 的 Phase2b 消息，并且发现冲突，则根据 O4(v)取一个 value，直接执行 Round i+1 的 Phase2a；否则，从 Phase1a 开始重新执行 Round i+1.
Fast Paxos 基本是本着乐观锁的思路：如果存在冲突，则进行补偿。其中 Leader 起到一个初始化 Progress 和解决冲突的作用，如果 Progress 一直执行良好，则 Leader 将始终不参与一致性过程。
因此 Fast Paxos 理论上只需要 2 个通信步骤，而 Classic Paxos 需要 3 个，但 Fast Paxos 在解决冲突时有至少需要 1 个通信步骤，在高并发的场景下，冲突的概率会非常高，冲突解决的成本也会很大。
另外，Fast Paxos 把 Client 深度引入算法中，致使其架构远没 Classic Paxos 那么清晰，也没 Classic Paxos 容易扩展。
Multi Paxos 里提议都由 leader 提出，因而不存在一次决议出现多个 value，Fast Paxos 里由 proposer 直接提议，一次决议里可能有多个 proposer 提议、出现多个 value，即出现提议冲突（collision)。leader 起到初始化决议进程（progress）解决冲突的作用，当冲突发生时 leader 重新参与决议过程。
