使用共享内存的快速随机共识

摘要

我们提出了一个新的随机算法，用于在读写共享寄存器进行通信的异步进程之间达成共识。过去已知的最快的算法时间复杂度为指数运行时间，我们的算法是多项式的，$O(n^4)$。该算法的应用包括从并发数据结构中消除关键部分，以及构建渐进无偏的共享硬币。

Introduction

共识协议：一组$n$个通过将操作应用于共享对象进行通信的异步处理器。

​ 对象：信道、读写寄存器数组等

进程：从输入值开始（0或1），运行到选择决策值后停止

当共识协议是一致、有效、无等待时，就是正确的。

​ 共识协议的一致：没有两个进程选择不同的决策值。

​ 共识协议的有效：决策值是某些进程的输入值。

​ 共识协议的无等待：每个进程都在有限数量步骤后决定。

编码共享数据的并发访问的传统方式：依赖于临界区

​ 临界区：同一时间只允许一个进程操作对象

临界区不适用于异步、容错系统：如果在一个临界区中，错误进程停止或延迟了，非容错进程也会被停止和延迟。反之，如果并发数据对象的实现保证任何进程将在$n$个步骤中完成任何操作，而不受其他停止故障或速度变化的进程的影响，则该实现是免等待的。如果针对对象$X$存在一个共识协议，则我们可以使用$X$构建针对任一并发数据对象的无等待实现。

如果共享对象$X$是提供读写操作的寄存器数组，那就无法达成共识了。如果$X$是提供TAS指令（把给定的内存地址设置为1，然后返回之前的旧值的原子操作）或FAA指令（内存位置增加一个数量的原子操作）的寄存器数组，则可以在两个进程间达成共识，但不能在三个进程间达成共识。然而，在这两种情况下，任意数量的进程之间仍然可以在概率上达成共识。本文提出了两种新的随机共识协议，一种是进程通过读取和写入共享寄存器进行通信，另一种是通过应用FAA操作进行通信。这些协议是一致的，非平凡的，它们保证每个进程在有限的预期步骤数之后决定。读写协议中，目前最快的算法时间复杂度是$2^{O(n^2)}$，本文则改进为$n^2$次写操作和$n^4$次读操作；FAA协议则预期需要$n^2$次FAA操作。

我们描述了一个简单的协议，如果对手调度程序以同步方式运行进程，该协议具有指数级的预期运行时间。每个进程在每轮中掷出一个无偏的硬币，当所有$n$个进程同时掷出”正确”值时，协议停止。在任何特定回合终止的概率为$\frac{1}{2}^n$。因此，在终止之前的预期回合数为$2^n$。加速协议的一种方法是用进程共享的单个无偏硬币替换$n$个独立的硬币翻转。但是，在异步系统中实现无偏的共享硬币被证明是不可能的（见下文第8节）。

类似于Chor，Merritt和Shmoys[13]提出的见解，它足以确保进程有足够的可能性翻转相同的值，并且对手调度程序对选择哪个值的影响足够弱。我们的共识协议的核心是一个弱共享硬币协议，它保证：

1. 进程可能观察到相同的结果；
2. 对手调度程序对该结果的影响很小；
3. 协议在进程数量上具有预期的运行时间多项式。

共识通常被视为一种博弈。进程一方试图与对手调度器达成协议。进程将读和写操作应用到共享寄存器，对手选择操作实际发生的时间。我们的对手非常强大，它拥有关于进程协议、它们的内部状态和共享内存状态的完整信息。它不局限于多项式资源，因此它不能被加密方案所超越。然而，对手无法预测未来的硬币投掷。