论文标题
与常规寄存器的随机共识
Randomized Consensus with Regular Registers
论文作者
论文摘要
在假设它使用的寄存器是原子寄存器的假设上，证明了Aspnes和Herlihy的众所周知的随机共识算法和Herlihy对异步共享内存系统的赫利希算法也有效。使用原子寄存器，每个读取操作都是瞬时的（因此是不可分割的）。正如Golab等人指出的那样。 （2011年），但是，如果我们替换它在可线化的寄存器实现中使用的原子寄存器，则与原子寄存器一起使用的随机算法不一定有效。 这就提出了以下问题：如果我们用可线化的寄存器代替其原子寄存器，Aspnes和Herlihy的随机共识算法是否仍然对抗强大的对手？我们表明答案是肯定的，实际上，我们表明即使是可线化的寄存器也不是必要的。更确切地说，我们证明，即使算法仅使用常规寄存器，Aspnes和Herlihy的算法也针对强大的对手。
The well-known randomized consensus algorithm by Aspnes and Herlihy for asynchronous shared-memory systems was proved to work, even against a strong adversary, under the assumption that the registers that it uses are atomic registers. With atomic registers, every read or write operation is instantaneous (and thus indivisible). As pointed out by Golab et al. (2011), however, a randomized algorithm that works with atomic registers does not necessarily work if we replace the atomic registers that it uses with linearizable implementations of registers. This raises the following question: does the randomized consensus algorithm by Aspnes and Herlihy still work against a strong adversary if we replace its atomic registers with linearizable registers? We show that the answer is affirmative, in fact, we show that even linearizable registers are not necessary. More precisely, we prove that the algorithm by Aspnes and Herlihy works against a strong adversary even if the algorithm uses only regular registers.
