Agreement in Synchronous Systems
Consensus and Interactive Consistency in Synchronous Systems
Consensus（共识）是一种分布式系统中的一致性协议，它的目标是使得所有进程都能够达成一致的决定。Consensus 只有propose(v)一种操作并返回一个值，该值即为所有进程达成的一致决定。我们称 consensus in the crash failure model 为 CC，以下是 CC 在$ CSMP_{n,t}[\emptyset] $和$ CAMP_{n,t}[\emptyset] $下的具体定义：
- CC-validity：进程 decide 的值一定是某个进程 propose 的值。
- CC-agreement：没有不同的进程 decide 了不同的值。
- CC-termination：如果一个进程是 non-faulty 的，那么该进程一定会 decide 一个值。
Consensus objects 是一种 one-shot object，即若$CONS$是一个 consensus object，那么每个进程只能够对$CONS$执行一次propose(v)操作。此外，我们将可以被 proposed 的值的集合记为$V$，如果$|V|=2$，那么我们称该 consensus 为 binary consensus。
A Simple Unfair Consensus Algorithm
下面我们来介绍一种不公平共识算法。由于最多有 t 个进程可能会崩溃，所以如果我们选取 t+1 个进程，那么总会有一个 non-faulty 进程的值可供我们 decide。因此，算法的基本思想就是每个进程都保存一个本地变量$est_i$来储存他的 decision value 的估计值，初始化为$v_i$，随后，每个进程执行 t+1 轮同步回合，第 r 轮由进程$p_r$主导，它 broadcast 自己的估计值，受到消息的进程更新他们的估计值。注意到，每一回合都至多存在一个 $est_i$ 在该系统中。具体的伪代码如下：
func CONS.propose(v):
est_i = v_i
for r in {1, ..., t+1}:
begin synchronous round r:
if r == i:
broadcast(est_i)
if receive(est_j) from p_j:
est_i = est_j
if r == t+1:
return est_i
end synchronous round我们假设 proposed value 所占 bit 位为 b，那么该算法的空间复杂度（消息传递 bit 数）为$ (n-1)(t+1)b $。同时需要注意，该算法仅可能 decide $p_1 \cdots p_{t+1}$中的 proposed value，因此该算法是不公平的，不过我们可以很简单的做一个预处理，将进程的 proposed value 随机交换，那么就可以使得该算法是公平的。
A Simple Fair Consensus Algorithm
上文中我们通过在系统最多同时存在一个 proposed value 来轻易的解决了问题，但是更常见的是引入一个 deterministic rule 来决定每个进程看见的 proposed value。在这里，我们将选取最小值作为 deterministic rule。具体来说，每个进程都 broadcast 它们的估计值，并接受所有其他进程的估计值，随后，每个进程都将自己的估计值更新为所有估计值中的最小值。此外，我们可以引入一个新的变量$ prev\_est_i $来保存进程所 broadcast 过的最小值，这样我们可以优化空间复杂度，仅当$ est_i \not= prev\_est_i $时，进程才 broadcast 自己的估计值。需要注意的是，由于一个 faulty 进程可能只 broadcast 进程的一个任意子集，因此 t+1 轮同步回合是必要的。具体的伪代码如下：
func CONS.propose(v):
est_i = v_i
prev_est_i = none
for r in {1, ..., t+1}:
begin synchronous round r:
if est_i != prev_est_i:
broadcast(est_i)
let recval_i = {est_j | receive(est_j) from p_j}
prev_est_i = est_i
est_i = min(recval_i, est_i)
if r == t+1:
return est_i
end synchronous round该算法的空间复杂度上界为$ n(n-1)b \times min(t+1, |V|) $。
Interactive Consistency(Vector Consensus)
Interactive Consistency 是一种进程 agree on 输入向量（input vector）的一致性抽象，因此，它也被称为 Vector Consensus（向量共识）。我们称 interactive consistency in the crash failure model 为 ICC，以下我们给出具体定义：
- ICC-validity：记$ D_i[1..n] $是进程$ p_i $的 decision vector，那么$ \forall j \in \{1, ..., n\}: D_i[j] \in \{v_j, \perp\} $，此外，如果$ p_j $是 non-faulty 的，那么$ D_i[j] = v_j $。
- ICC-agreement：没有不同的进程 decide 了不同的 vector。
- ICC-termination：如果一个进程是 non-faulty 的，那么该进程一定会 decide 一个 vector。
我们注意到，如果$ D_i[j] = \perp $并且$ p_i $是 non-faulty 的，那么意味着$ p_j $是 faulty 的并且已经 crash。但是如果$ D_i[j] \not= \perp $，那么我们无法判断$ p_j $是否是 non-faulty 的。此外，我们可以轻易看出在 ICC 中实现 Consensus 是非常容易的。
Interactive Consistency 的一个使用例子就是构建原子回合（Atomic Rounds）。如果进程$p_i$在第$r$轮中崩溃，且其本该 broadcast 的消息要么被所有 non-crashed 进程接收到，要么没有进程接收到，那么我们称进程$p_i$在第$r$轮的崩溃是原子的，如果一个回合中每一个这样的崩溃都是原子的，那么我们称这一回合是一个原子回合。而基于 ICC 上构建其也很简单，记$ \rho $为回合数，那么只需每回合 broadcast 的 $m_i^\rho $作为每个进程的 proposed value，然后根据$ D[j] $判断即可。
Expediting Decision in Synchronous Systems
我们在上文已经实现了一个公平的 consensus，不过是否可能实现一个少于 t+1 轮的 consensus 算法？更具体点，如果实际的崩溃进程为 f，能否实现一个小于 t+1 的，关于 f 的轮数的算法？下面我们就来介绍一个这样的算法，它能够在$ min(f+2, t+1) $轮内达成 consensus。一个直观的关于 f+2 的解释是在 f+1 回合后，我们至少有一个进程执行了一回合并发现没有任何错误，这样它可以马上 decide，但是它不知道其他进程是否已知，所以需要一个额外的回合来 broadcast。需要注意，t 是算法开始前系统已知的，而 f 并不是。
An Early Decision Predicate
在之前的算法，如果进程$ p_i $没有从$ p_j $收到任何消息，它无法判断进程$ p_j $是已经崩溃了还是不需要发送消息。所以，我们对每个进程需要进行如下改动：
- 每个进程在每一回合都 broadcast 一个消息知道其崩溃或者已经 decide。
- 在同一回合，任何一个消息都可以表明其发送者是否要在其被发送后进行 decide。
有了这些规则，$p_i$就可以避免受到$p_j$状况的不确定性，假设$r$为第一次$p_i$没有收到$p_j$的消息的回合，那么我们知道$p_j$要么在$r-1$或$r$回合崩溃，要么在$r-1$回合已经 decide。且，如果$p_j$在$r-1$回合 decide，那么它便已经发送给$p_i$全部的它曾接收到的信息。
下面我们介绍用于 early decision 的谓词，并假设没有进程在$r-1$回合之前 decide。
- $UP^r$：开始第$r$回合的进程集合。
- $R_i^r$：进程$p_i$在第$r$回合的接收到消息的进程集合。
- $R_i^0$：n 个进程的集合。
我们可以轻易的看出，没有进程知道$UP^r$，但是每个进程都知道$R_i^r$与$R_i^{r-1}$。并且我们能根据上述规则立刻得出下面的重要结论：
$$ \forall r \geq 1: R_i^r \subseteq UP^r \subseteq R_i^{r-1} $$
因此，当$R_i^r = R_i^{r-1}$时，我们可以知道$UP^r = R_i^r$，意味着$p_i$在回合$r$接收到消息的每个进程都在回合$r$开始时 alive。现在我们便可以看出，若$ R_i^r = R_i^{r-1} $，那么$p_i$就可以了解到所有的在$r$回合开始 alive 的进程的所有$\langle k,v \rangle$对。而其余的，将永远不会在未来的回合被这些进程所学习到，因此，进程$p_i$可以在$r$回合 decide。我们将此谓词记为$DIFF(i, r) \equiv (nbr_i[r] - nbr_i[r-1] = 0)$。
我们可以很容易的将其应用到上述介绍过的算法之中，因此具体伪代码略去。
此外，我们现在考虑另一个谓词$ COUNT(i, r) \equiv (faulty_i[r] < r), faulty_i[r] = n - nbr_i[r] $，它也是一个正确的 early decision 谓词。这是因为，当第一次回合$r$，回合数大于进程$p_i$所知的崩溃进程数时，在$p_i$看来，已经崩溃的进程数是小于它已经执行过的回合数，即，存在某一回合，没有进程崩溃，意味着$p_i$已经在该回合获得到了所有它能够获得的$\langle k,v \rangle$对。因此，该谓词也是正确的。
不过我们现在考虑一个问题，这两个谓词之间是否有好坏之分呢？答案是肯定的，我们可以证明存在这样一个 failure pattern，它使得$DIFF$谓词第一次在第$r$回合成立，而$COUNT$谓词不成立。这是由于$DIFF$谓词是一个差分谓词，即，它根据实际的 failure pattern 进行判断，而$COUNT$谓词仅仅基于自从回合开始，被$p_i$所知的崩溃进程数。根据定义可知，无论实际的 failure pattern 如何，其只考虑每回合都存在一个进程崩溃的极端情况，而$DIFF$谓词则考虑了实际的 failure pattern 并得以做出一个更早的 decision。因此，$DIFF$谓词是一个更好的谓词。
k-Set Agreement
下面我们来介绍 k-Set Agreement，它是一种比 Consensus 更弱的一致性协议，简单来说它允许进程选择有限个不同的 decision value。我们可以称 Consensus 是 1-Set Agreement 的特例。k-Set Agreement 的定义与 Consensus 类似，除了 agreement 条件变为了：
- SA-agreement：最多有 k 个不同的值被 decide。
在执行$\lfloor \frac{t}{k} \rfloor +1 $回合后，一个进程决定它所见到的最小的值。我们的具体目的就在于在最后一回合，最多有 k 个不同的值在系统中。具体的伪代码如下：
func propose(v_i):
est_i = v_i
for r in {1, ..., floor(t/k)+1}:
begin synchronous round r:
broadcast(est_i)
est_i = min({est_j | receive(est_j) from p_j})
if r == floor(t/k)+1:
return est_i
end synchronous round算法的正确性证明如下：
算法的 validity 和 termination 是 trivial 的，我们主要考虑 agreement 的证明。我们令$ t = \alpha \times k + \beta,\ \alpha = \lfloor \frac{t}{k} \rfloor,\ \beta = (t\ mod\ k) $，我们将证明在回合$ r = \alpha + 1 $，最多有$ \beta + 1 $个不同的值在系统中，由于$ \beta + 1 \leq k $，因此该算法是正确的。
我们首先观察到，如果有$y$个进程在回合$r$崩溃，那么系统中最多存在$y+1$个不同的值。这是因为没有崩溃的进程统一了一个估计值，而$y$个崩溃的进程各向一个进程 broadcast 了自己的值，更进一步，我们假设$y$个崩溃进程的估计值都不同且小于非崩溃进程的估计值，即，$w_1 < w_2 < w_3 < \cdots < w_y < w $，因此，我们考虑最坏的情况：从第1个回合到第$ \alpha = \lfloor \frac{t}{k} \rfloor $每回合都有$k$个进程崩溃，这基于鸽巢原理，如若不然，那么在某一回合中，系统中最多存在$ k $个不同的值，就可以实现共识，与假设矛盾。这样在最后一回合，我们最多有$ \beta $个进程崩溃，由于$ \beta = (t\ mod\ k) < k $，因此最多有$ \beta + 1 \leq k $个不同的值在系统中。这就证明了 agreement，进而证明了算法的正确性。