Fully Polynomial Byzantine Agreement for n > 3t Processors in t + 1 Rounds
Fully Polynomial Byzantine Agreement for n > 3t Processors in t + 1 Rounds
复制标题
DOI：
10.1137/s0097539794265232
复制
发表时间：
1998-02
期刊：
影响因子：
--
通讯作者：
J. Garay;Yoram Moses
中科院分区：
文献类型：
--
作者：
J. Garay;Yoram Moses
本文提出了一个多项式时间的协议，当n > 3t时，在t + 1轮达到拜占庭协议，其中n是处理器的数量和t是一个先验上界的失败次数。这解决了Pease，Shostak和Lamport在1980年提出的一个开放问题。该协议的早期停止的变体也提出了，达成协议的数量轮，这是成比例的处理器的数量，实际上失败。
This paper presents a polynomial-time protocol for reaching Byzantine agreement in t + 1 rounds whenever n > 3t, where n is the number of processors and t is an a priori upper bound on the number of failures. This resolves an open problem presented by Pease, Shostak, and Lamport in 1980. An early-stopping variant of this protocol is also presented, reaching agreement in a number of rounds that is proportional to the number of processors that actually fail.