论文地址：差异生存：Paxos vs Viewstamped复制vs Zab
    也许到目前为止，您已经开始在我们所研究的算法中发现一些常见的模式。一个领导者或初级领导者；小组想要完成的每个目标的两个阶段（某种形式的准备，等待小组大多数成员的确认，然后提交）；依靠quorum intersection属性在小组内保留历史知识；用于区分组生命周期中不同阶段的不断增加的序列号；以及始终与声称最高阶段（epoch）号的成员保持一致的协议。
    Paxos、Viewstamped Replication和Zab在多大程度上是根本不同的，而仅仅使用不同的术语来处理本质上相同的事情呢？如果你认为孤立地深入理解其中任何一个已经够糟糕的话，这类问题真的会让你头晕目眩！幸运的是，van Renesse等人在今天的论文选择中为我们做了很多艰苦的工作。通过精益求精，他们向我们展示了共识家族树，并照亮了真正重要的东西。遗憾的是，它们显然是从最初的Viewstamped Replication paper（VR）而不是Viewstamped Replication reviewed（VRR）开始工作的，因为后者有更清晰的规范和术语，但这并没有减损主要结果。
    以状态转换规范∑表示的协议，如果存在状态空间∑到状态空间∑的映射，则对另一个规范∑进行细化，并且∑中的每个状态转换都可以映射到∑中的状态转换或no-op。规范之间的这种映射称为细化[1]或向后模拟[2]。如果两个协议互相完善，那么我们可能会争辩说它们是相似的。但是如果没有，我们如何描述两个协议之间的相似性和差异呢？
    更非正式地说，如果B细化了A，那么B可以添加一个细节级别，并对允许的行为集添加约束。

    这是家谱。每个箭头表示一个优化关系。

    viveladifference.jpg

    每个细化对应于设计决策，如图1所示，通过遵循这些设计决策的不同路径来导出相同规范。在图1中跨越抽象边界的细化和不跨越抽象边界的细化之间存在着质的区别。当跨越抽象边界时，精化接受一个抽象概念，并用一个更具体的概念替换它。例如，它可以作出一个抽象的决定，并以多数票取代它。在同一个抽象中，细化限制了行为。例如，一个规范可能决定命令的顺序，而一个更严格的规范可能决定命令的顺序。
    从一个可线性化服务的规范开始，我们可以对其进行改进，生成一个主动复制模型，然后传递一个被动复制模型。在活动复制中，每个副本实现一个确定的状态机并处理操作，所有副本按相同的顺序处理操作。在被动复制中，只有主服务器执行操作，然后将结果状态转发给每个备份。
    主动复制的棘手部分是确保复制副本以相同的顺序执行操作，尽管存在复制副本故障、消息丢失以及不可预知的传递和处理延迟。通常采用容错一致性协议，以便副本同意每个i的第i个操作。具体地说，每个副本提出从一致性协议的实例i中的一个客户端接收的操作。只能决定拟议的行动之一。只要每个consensum实例最终终止，服务仍然可用。
    被动复制所需的主顺序（或前缀顺序）属性用一个简单的示例解释：

    考虑一个初始值为3的复制整数变量。一个客户端想要增加变量，而另一个客户端想要加倍。一个主节点同时接收两个操作并提交状态更新4和8。另一个primary以相反的顺序接收操作并提交更新6和更新7。如果没有前缀排序，可能会发生这样的情况：决定的状态是4后跟7，与这两个操作的任何顺序历史都不对应。
    （我仍在考虑将主顺序和被动复制结合在一起。主顺序不能与活动复制同等重要吗？在某些情况下，如果状态更新不是增量的，我们就不能在没有主顺序要求的情况下进行被动复制吗？这些变体会在树中添加更多的分支，但我认为不会影响对具体协议之间差异的最终分析）。
    作者断言VR和Zab使用被动复制，而Paxos使用主动复制。“但是，可以在另一种方法上实现一种方法。”VRR在我看来非常清楚地指定了一种活动复制模型——这就是“服务启动调用”所关心的问题。
    主动复制可以被改进以产生多共识协议，这是Paxos、VR和Zab最具体的共同祖先。
    多共识有两个基本的构建块：（1）一个称为证明者的n个进程的静态集合。其中一小部分可能会崩溃。因此，为了最大限度地容忍f个错误过程，我们要求n≥2f+1必须保持；（2）无穷多轮。在每一轮中，多个一致意见分配给最多一个认证者的角色定序器。回合的序列器为每个插槽最多认证一个命令…一旦大多数认证者在回合内认证该命令，则决定该命令（并且由于认证无法收回，因此该命令将继续决定）。
    多一致性不用于优化被动复制（它不保留prefix order属性）。

    实现前缀排序的一种方法是，主服务器延迟为一个时隙提出命令，直到它知道所有先前时隙的决定为止。但那会很慢。一个更好的解决方案是细化多共识，并获得一个规范，也细化被动复制以及满足前缀排序。我们称此规范为多共识采购订单。多共识PO保证每个决策都是应用于在前一时隙（第一时隙除外）中决定的状态的操作的结果。
    本文中给出的多共识和多共识PO规范指定了可以执行哪些转换，但不指定何时应执行这些转换。最后一轮改进表明，Paxos、Zab和VR可以从它们派生出来。本文第11页的表2是这一过程中发现的主要差异的快速参考版本。
    在这一切的最后，问“我应该用哪一个”是合理的？’. 作者的结论是：
    使用被动复制策略（如在VR和Zab中使用）计算密集型服务更好（前提是状态更新的大小合理）。为了在正常的案例执行和恢复期间为短操作实现可预测的低延迟性能，最好的选择是不指定多数的主动复制策略，例如在Paxos中使用的策略。