Heidi Howard 的论文说了啥？

概述

《Distributed consensus revised》是 Heidi Howard 写于 2019年4月份的博士论文。该论文主要是针对 Paxos 算法的改进，主要改进的地方是在减少和 quorums 交互的情况下使算法对某一个提议达成共识。传统的 Paxos 算法实现上，无论哪个阶段都需要满足节点的大多数。论文中提到到的 a b c 改进算法只需 phase one 和 phase two 阶段有交集，并且每个改进的算法都在依次减少这个交集中的 quorums 数量。且在此算法基础上，每个节点在提交提案的时候都能 skip phase one 和共享 epochs 下高效地到达共识。

下面将对论文中提及到的Quorum intersection、Promise、value selection 和 Epochs 改进分别做个大概的描述，具体的改进描述大家可以参考论文。除此以外，读者需要对 classic paxos 算法有一定的了解。

01

Quorum intersection Revised

我们知道，Classic Paxos 是两阶段提交协议 —— 分为 phase one 和 phase two，且无论是 phase one 与 phase one、phase two 与 phase two 还是 phase one 与 phase two 之间，他们的 quorum 必须满足节点的大多数。用数学表示的话就是要有交集：

其中，Q1表示 phase one 阶段，Q2表示 phase two 阶段。这是 classic paxos 算法必须满足的条件。论文中提及的 revision A 改进就是去掉了 phase one 之间和 phase two 之间的 quorum 交集要求，只保留了 phase one 和 phase two 两阶段之间的 quorum 保留交集要求就能达到 classic paxos 算法的效果，

在 revision A 的基础上，论文将通过 epoch 继续缩小 quorum 数量的范围。Classic Paxos 算法在 phase one 阶段提交提议的时候都会带一个提案号 —— epoch，并且当前次的 epoch 要大于前一次的 epoch。为了缩小 quorum 数量范围，论文中提出只需要保证当前次 phase one 阶段的 quorum 和前一次的 phase two 阶段的 quorum 有交集，即可以保证 Paxos 算法的一致性。

02

Promise Revised

Classic Paxos 在进行 phase two 阶段提议前，提议者必须收到大部分 quorum 的 promises 。在论文中提及的 revision B 改进，在进行 phase two 阶段提议前，也是必须满足这样的条件，不同的是 quorum 的范围缩小了，只需满足上一轮次 phase two 阶段 quorum 的 promises 。让我们考虑一下，假如一个提议者在 phase one 阶段发送了一个提案号为 e 的 prepare —— prepare(e)，并且从一个接收者处收到 (e,f,v) 的 promise。此时，这个提议者就知道，如果有个提案号是 f 的提议被采纳，那么这个提议的就是 v。这时此提议者就无需再等待其他 quorum 且提案号也是 f 的 promises。因为，一个相同的提案号不可能有相同的值。此外，我们无需等待其他提案号小于 f 的 quorum 的 promises。上面，就是论文中提及的 revision C 改进。

03

Value select Revised

无论是 classic paxos 还是到目前为止改进方案，在 select value 的时候都是选择提案号 epoch 最大的那个提议；如果最大的 epoch 的提议值是空的话，那么提议者就可以选择自身备选的提议。论文中提到两种 value selection revised 方法，分别为 Epoch agnostic algorithm 和 Epoch dependent algorithm 。

先来说说 Epoch agnostic algorithm 方法。前面说过，以前的 value select 策略都是从 promises 中选择 epoch最大的提议值，而这个策略却完全不一样。他用一个集合用来记录不同 quorum 返回的 promise 是否符合待提议的要求。这些要求是他下面两个辅助定理做为依据支撑的：

本质上尝试逐个否定 phase two 阶段中每个 quorum 元素的方式，来排除一些提议候选值。这个方法正确性的直觉是：真正被 chosen 的候选值是不会被否定掉的。

Epoch agnostic algorithm 方案只能针对 quorum，跟 epoch 完全无关的情况，Epoch dependent algorithm 方法就是加上 epoch 维度的改进版。

04

Epochs Revised

到目前为止，proposer 的 epoch 都是唯一的，相互不重叠。之所以能做到这样，是因为第一通过了预分配机制，第二是在 phase one 阶段的 vote epoch 机制。论文中提及的是第三种，就是每个 proposer 可以使用相同的 epoch 提议。怎么做到的呢？

如果使用相同的 eooch 提议，会有三个问题。只要解决这三个问题改进的 paxos 算法就能使用。

第一，不同的 proposer 使用相同的 epoch 提议，那么提议的值就会被 phase two 阶段且没有交集的 quorums 接收。然而，这在paxos 算法中是不允许的。怎么解决？解决方法很简单，那就要 phase two 阶段的 quorums 有交集。

第二，被 phase two 阶段某个 quorum 接收的提议可能会被相同的 epoch 的提议重写，这样就会导致值冲突。解决方法是只接收提议的 epoch 大于当前已接收提议的 epoch 或是接收完全相同的提议。

第三，对于 proposers 来说，他们在 phase one 阶段有可能会收到相同的 epoch 但是不同的提议(value)，这个时候 proposer 的过程就会无法进行下去。对于这种情况，论文给出的解决方法是加强 phase one 和 phase two 之间 quorums 的交集。论文中第一个问题的解决方法是要求 phase two 之间的 quorum 需要有交集，在这个问题的解决方法中，phase one 阶段的 quorums 需要和这个交集也需要有交集。

总结

文章只是对论文各个改进点做了总结描述，没有对整篇论文做深层的逻辑推理，感兴趣的读者可以下载该论文，通过论文中大量的伪代码和交互图自行推论。