FULLY POLYNOMIAL BYZANTINE AGREEMENT FOR N-GREATER-THAN-3T PROCESSORSIN T+1 ROUNDS

Authors
GARAY JA MOSES Y
Citation
Ja. Garay et Y. Moses, FULLY POLYNOMIAL BYZANTINE AGREEMENT FOR N-GREATER-THAN-3T PROCESSORSIN T+1 ROUNDS, SIAM journal on computing, 27(1), 1998, pp. 247-290
Citations number
32
Categorie Soggetti
Computer Science Theory & Methods",Mathematics,"Computer Science Theory & Methods",Mathematics
Journal title
SIAM journal on computing → ACNP
ISSN journal
00975397
Volume
27
Issue
1
Year of publication
1998
Pages
247 - 290
Database
ISI
SICI code
0097-5397(1998)27:1<247:FPBAFN>2.0.ZU;2-5
Abstract
This paper presents a polynomial-time protocol for reaching Byzantine agreement in t + 1 rounds whenever n > 3t, where n is the number of pr ocessors and t is an a priori upper bound on the number of failures. T his 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.