An O(lg n) expected rounds randomized Byzantine generals protocol

ABSTRACT

Byzantine Generals protocols enable processes to reliably broadcast messages in the presence of faulty processes. These protocols are run in a system of consists of n processes, t of which are faulty. The protocols are conducted in synchronous rounds of message exchange. We show that, without using cryptography, for t = n/(3 + &dgr;), there is a randomized protocol with &Ogr;(lg n) expected number of rounds. If we allow cryptographic methods, then, for t = n / (2 + &dgr;), there is a randomized protocol with &Ogr;(lg n) expected number of rounds. This is an improvement on the lower bound of t + 1 rounds required for det … … previous result of t/lg n expected nu rounds for randomized protocols.

REFERENCES

• Awer85: B. Awerbach: M. Blum, B. Chor, S. Goldwazser, and S. Micali, Implementing Bracha's O(log n) Byzantine agreement algorithm, submitted to 1985 PODC.
• BenO83: Michael Ben-Or, Another advantage of free choice (Extended Abstract): Completely asynchronous agreement protocols, Proceedings of the second annual ACM symposium on Principles of distributed computing, p.27-30, August 17-19, 1983, Montreal, Quebec, Canada [doi>10.1145/800221.806707]
• BenO83: M. Ben-Or, private communication.
• Brac83: Gabriel Bracha , Sam Toueg, Resilient consensus protocols, Proceedings of the second annual ACM symposium on Principles of distributed computing, p.12-26, August 17-19, 1983, Montreal, Quebec, Canada [doi>10.1145/800221.806706]
• Brac84a: Gabriel Bracha, An asynchronous [(n - 1)/3]-resilient consensus protocol, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.154-162, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806743]
• Brod84a: A. Z. Broder and D. Dolev, Flipping coins in many pockets, ~Sth Annual Symposium on f'oundation of Computer Sciences, Singer Island, Florida, Oct. 1984, pp. 157- 170.
• Brod84b: A.Z. Broder, Private communication.
• Chor84: B. Chor, and B. Coan, A simple and efficient randomized Byzantine agreement algorithm, Fourth S~tmpoeium on Reliability in Distributed Software and Database System, Silver Spring, Maryland, Oct. 1984 pp. 98-106.
• Dole81: D. Dolev, Unanimity in an unknown and unreliable environment, Proceedings 2~nd Annual Symposium on Foundations of Computer Science, Nashville, Tennessee, pp. 159-168, Oct. 1.981.
• Dole82a: D. Dolev, The Byzantine Generals strike again, Journal of Algorithms, vol. 3, no. 1, pp. 14-30, April 1983.
• Dole82b: Danny Dolev , H. Raymond Strong, Polynomial algorithms for multiple processor agreement, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.401-407, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802215]
• Fisc82a: M.J. Fischer and N. A. Lynch, A lower bound on the time to assure interactive consistency, Information Processing Letters, voi. 14, no. 4, pp. 183-186, May 1982.
• Hasta: J. Hastad, On using RSA with low exponent iin a public key network, to be published, MIT.
• Lamp82a: L. Lamport and M. Fischer, Byzantine Generals and Transaction Commit protocols, Opus 62, SRI International, April 1982.
• Lamp82b: Leslie Lamport , Robert Shostak , Marshall Pease, The Byzantine Generals Problem, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.382-401, July 1982 [doi>10.1145/357172.357176]
• Rabi83: M. Rabin, Randomized Byzantine Generals, Proceeding ~4th Syrnpoeium on Foundations of Computer Science, Tuscon, Arizona, pp. 403-409, Nov. 1983.
• Rive78: R. L. Rivest , A. Shamir , L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, v.21 n.2, p.120-126, Feb. 1978 [doi>10.1145/359340.359342]
• Sham79: Adi Shamir, How to share a secret, Communications of the ACM, v.22 n.11, p.612-613, Nov. 1979 [doi>10.1145/359168.359176]
• Yao83: A.C. Yao, On the succession problem for Byzantine generals, Tech. Rep., Computer Science Dept., Stanford University, to appear.

INDEX TERMS

Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

  G. Mathematics of Computing

General Terms:
Algorithms, Reliability, Theory, Verification