|
Abstract : |
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 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. SICOMP 27-1 (1998), pp.247-290, |
