《State-Machine Replication for Planet-Scale Systems》中ATLAS协议解读
目的
为了更好地理解ATLAS协议，我们首先通过一个示例来展示ATLAS协议的消息流程，其对应一个常见的leaderless的SMR协议的实现。后面的章节我们详细介绍ATLAS协议。
图一：ATLAS协议消息流程
流程
图一展示了ATLAS协议是如何处理两个冲突命令a和b的，集群中一共有5个节点，可以容忍的故障节点数目为f = 2。在每一个process的视角，一个命令通常会经历几个阶段：START， COLLECT，COMMIT和EXECUTE(一个额外的RECOVER阶段，用于故障处理)。
一个命令a从process 1上调用submit(a)开始它的旅程，我们把process 1称为命令a的initial coordinator。之所以称为initial coordinator，是因为如果发生故障或者process 1变得很慢，其它的process会接替process 1的工作。然后，命令a在process 1上进入到COLLECT阶段，这个阶段的目的是去计算a所依赖的命令的集合，我们使用dep[a]来表示a所依赖的命令集合，这些依赖此后会用于决定相互冲突的命令的执行顺序。为了计算命令的a的依赖dep[a]，process 1发送MCollect消息到一个fast quorum节点的集合，这个MCollect消息包含命令a。MCollect消息至少发往majority节点，但是可以大于majority。在图一的例子中，我们选择process 1的fast quorum是{1，2，3，4}。
每一个在fast quorum中的process返回一个与命令a冲突的命令的集合，判断一个命令和a是否冲突的标准是那些命令在a到达之前已经收到。在图一中，符号 表示命令收到的顺序。例如，在process 4上先收到了b，其他的包含在fast quorum的process上，没有早于a的命令。基于fast quorum的回复，process 1计算dep[a](具体的描述在下一个章节展开)，我们这个例子中，process 1上计算的到dep[a]为
。
如果一个process怀疑一个命令的coordinator故障，其它的process可以尝试接替它的工作。在图一中，process 2怀疑process 1故障了，提升自己成为命令a的另外一个coordinator，通过recover(a)来表示。Process 2和majority的quorum {2，3，4}联系，然后计算自己视角版本的关于命令a的依赖，结果是dep[a] = {b}。
依赖被用于决定相互冲突的命令之间的执行顺序，所有的process必须以相同的顺序执行相互冲突的命令。为了确保这一点，命令a的coordinator必须就dep[a]的值达成共识，达成共识的过程通过single-decree paxos的优化变种来实现，所有的n个process作为paxos中的acceptor角色。在这个具体的例子中，需要这些process就dep[a] =达成共识。使用共识意味着进入ATLAS协议的slow path。
如果一个coordinator可以确保所有可能提出的共识提案值相同，那么就可以走ATLAS协议的fast path，避免通过共识来确定最后的状态。在图一中，process 5协调命令b就是走fast path的一个例子。一个process可以走fast path的条件是，收到了来自fast quorum节点的全部回复。
在共识达成或者选择fast path后，一个命令的coordinator以MCommit消息发送最终的依赖(dep)给其它的process。每一个收到MCommit消息的process存储这个依赖、并将这个命令标记为进入到COMMIT阶段。一个命令只有在它所有的依赖都进入到COMMIT或EXECUTE阶段，才能被执行(进入EXECUTE阶段)。在我们的例子中，因为dep[a] =, 在收到它最终的依赖集合后，process可以立即执行命令a。在图一中，process 1和process 2属于这种情况。但是，因为dep[b] = {a}, process必须延迟命令b的执行，直到命令a已经被执行了。在图一中，process 3、process 4和process 5属于这种情况。这种执行机制保证，冲突的命令a和b在所有的process上是以相同的顺序执行的。
结论
ATLAS协议的优势是，如果容错节点数目f = 1，那么协议始终会走fast path。在实际工程中多以3副本、f = 1的配置为主，所以这个协议的使用价值还是挺高的。
