Wait-Free Consensus Using Asynchronous Hardware
Wait-Free Consensus Using Asynchronous Hardware
复制标题
使用异步硬件的无等待共识
DOI：
--
复制
发表时间：
1994
期刊：
影响因子：
--
通讯作者：
Ming Li
中科院分区：
文献类型：
--
作者：
B. Chor;A. Israeli;Ming Li
研究了异步共享内存模型中的无等待一致性问题。在这个模型中，处理器通过共享寄存器进行通信，共享寄存器允许原子读和写操作（但不支持原子测试和设置）。众所周知，确定性协议无法解决无等待共识问题。给出了一个随机解。该协议简单、有建设性，可以容忍多达$n-1$个处理器崩溃（其中$n$是处理器的数量），其预期运行时间为$O(n^2)$。
This paper studies the wait-free consensus problem in the asynchronous shared memory model. In this model, processors communicate by shared registers that allow atomic read and write operations (but do not support atomic test-and-set). It is known that the wait-free consensus problem cannot be solved by deterministic protocols. A randomized solution is presented. This protocol is simple, constructive, tolerates up to $n-1$ processors crashes (where $n$ is the number of processors), and its expected run-time is $O(n^2)$.