Optimal Early Stopping in Distributed Consensus (Extended Abstract)
Optimal Early Stopping in Distributed Consensus (Extended Abstract)
复制标题
分布式共识中的最优提前停止（扩展摘要）
DOI：
10.1007/3-540-56188-9_15
复制
发表时间：
1992
影响因子：
3.1
通讯作者：
K. Perry
中科院分区：
文献类型：
--
作者：
P. Berman;J. Garay;K. Perry
分布式共识问题涉及 n 个处理器，每个处理器都保存一个初始二进制值。至多t个处理器可能有故障并忽略任何协议（甚至恶意行为），但要求无故障的处理器最终就其中一个处理器最初持有的值达成一致。本文提出的共识协议可以容忍任意错误，是早期停止的（即，运行的轮数与执行期间实际发生的错误数量 f 成比例），并且在各种措施中都是最佳的。
The Distributed Consensus problem involves n processors each of which holds an initial binary value. At most t processors may be faulty and ignore any protocol (even behaving maliciously), yet it is required that the non-faulty processors eventually agree on a value that was initially held by one of them. This paper presents consensus protocols that tolerate arbitrary faults, are early-stopping (i.e., run for a number of rounds proportional to the number of faults f that actually occur during their execution), and are optimal in various measures.