Flipping Persuasively in Constant Time
Authors:
- Cynthia DworkCDCynthia Dwork
- David ShmoysDSDavid Shmoys
- Larry StockmeyerLSLarry Stockmeyer
- 1 June 1990
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 19 (3) , 472-499
Abstract
A persuasive coin is a sufficiently unbiased source of randomness visible to sufficiently many processors in a distributed system. An algorithm is described for achieving a persuasive coin in the presence of an extremely powerful adversary where the number of rounds of message exchange among the processors is constant, independent of the number n of processors in the system as well as the number of faults, provided the total number of faulty processors does not exceed a certain constant multiple of $n/\log n$. As a corollary an $\Omega (n/\log n)$-resilient probabilistic protocol for Byzantine agreement running in constant expected time is obtained. Combining this with a generalization of a technique of Bracha, a probabilistic Byzantine agreement protocol tolerant of almost ${n / 4}$ failures with $O(\log \log n)$ expected running time is obtained.
Keywords
This publication has 18 references indexed in Scilit:
- Simple constant-time consensus protocols in realistic failure modelsJournal of the ACM, 1989
- An O (log n ) expected rounds randomized byzantine generals protocolJournal of the ACM, 1987
- Impossibility of distributed consensus with one faulty processJournal of the ACM, 1985
- Probabilistic encryptionJournal of Computer and System Sciences, 1984
- Authenticated Algorithms for Byzantine AgreementSIAM Journal on Computing, 1983
- Randomized byzantine generals1983
- A lower bound for the time to assure interactive consistencyInformation Processing Letters, 1982
- The Byzantine generals strike againJournal of Algorithms, 1982
- Reaching Agreement in the Presence of FaultsJournal of the ACM, 1980
- How to share a secretCommunications of the ACM, 1979