Simple constant-time consensus protocols in realistic failure models
Simple constant-time consensus protocols in realistic failure models
复制标题
现实故障模型中的简单恒定时间共识协议
DOI：
10.1145/65950.65956
复制
发表时间：
1989
期刊：
影响因子：
--
通讯作者：
D. Shmoys
中科院分区：
文献类型：
--
作者：
B. Chor;Michael Merritt;D. Shmoys
使用简单的协议，它显示了如何在各种故障和遗漏故障模型中以恒定的预期时间达成共识。值得注意的是，所考虑的最强模型是完全异步的。所有结果均基于分布式翻转硬币，这是大部分处理器可用的。最后，对于共识的随机协议，还给出了几乎匹配的下限。
Using simple protocols, it is shown how to achieve consensus in constant expected time, within a variety of fail-stop and omission failure models. Significantly, the strongest models considered are completely asynchronous. All of the results are based on distributively flipping a coin, which is usable by a significant majority of the processors. Finally, a nearly matching lower bound is also given for randomized protocols for consensus.