Simple constant-time consensus protocols in realistic failure models

ABSTRACT

Using simple protocols, it is shown how to achieve consensus in constant expected time, within a variety of fail-stop and omission failure models. Significantly, the strongest models considered are completely asynchronous. All of the results are based on distributively flipping a coin, which is usable by a significant majority of the processors. Finally, a nearly matching lower bound is also given for randomized protocols for consensus.

REFERENCES

• 1: Werner Alexi , Benny Chor , Oded Goldreich , Claus P. Schnorr, RSA and Rabin functions: certain parts are as hard as the whole, SIAM Journal on Computing, v.17 n.2, p.194-209, April 1988 [doi>10.1137/0217013]
• 2: Baruch Awerbuch, Complexity of network synchronization, Journal of the ACM (JACM), v.32 n.4, p.804-823, Oct. 1985 [doi>10.1145/4221.4227]
• 3: AWERBUCH, B., BLUM, M., CHOR, B., GOLDWASSER, S., AND MICALI, S. How to implement Bracha's O(log n) Byzantine agreement algorithm. Unpublished manuscript.
• 4: 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]
• 5: Gabriel Bracha, An O(log n) expected rounds randomized byzantine generals protocol, Journal of the ACM (JACM), v.34 n.4, p.910-920, Oct. 1987 [doi>10.1145/31846.42229]
• 6: Gabriel Bracha , Sam Toueg, Asynchronous consensus and broadcast protocols, Journal of the ACM (JACM), v.32 n.4, p.824-840, Oct. 1985 [doi>10.1145/4221.214134]
• 7: CHOR, B., AND COAN, B. A simple and efficient randomized Byzantine agreement algorithm. IEEE Trans. Sofiw. Eng. SE-11, 6 (1984), 531-539.
• 8: Benny Chor , Michael Merritt , David B. Shmoys, Simple constant-time consensus protocols in realistic failure models (extended abstract), Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.152-162, August 1985, Minaki, Ontario, Canada [doi>10.1145/323596.323610]
• 9: B. A. Coan, Achieving consensus in fault-tolerant distributed computer systems: protocols, lower bounds, and simulations, Massachusetts Institute of Technology, Cambridge, MA, 1987
• 10: 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]
• 11: DWORK, C., SHMOYS, D., AND STOCKMEYER, L. Flipping persuasively in constant expected time. In Proceedings of the 27th Symposium on Foundations of Computer Science. IEEE, New York, 1986, pp. 222-232.
• 12: Paul Feldman , Silvio Micali, Optimal algorithms for Byzantine agreement, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.148-161, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62225]
• 13: FISCHER, M. J., AND LYNCH, N.A. On describing the behaviour and implementation of distributed systems. Theoret. Comput. Sci. 13 ( 1981 ), 17-43.
• 14: Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM (JACM), v.32 n.2, p.374-382, April 1985 [doi>10.1145/3149.214121]
• 15: GOLDWASSER, S., AND MICALI, S. Probabilistic encryption. J. Comput. Syst. Sci. 28, 2 (1984), 270-299.
• 16: S. Goldwasser , S. Micali , C. Rackoff, The knowledge complexity of interactive proof systems, SIAM Journal on Computing, v.18 n.1, p.186-208, Feb. 1989 [doi>10.1137/0218012]
• 17: KARLIN, A. R., AND YAO, A.C. Probabilistic lower bounds for Byzantine agreement and clock synchronization. Unpublished manuscript.
• 18: 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]
• 19: MERmTT, M. Unpublished manuscript.
• 20: M. Pease , R. Shostak , L. Lamport, Reaching Agreement in the Presence of Faults, Journal of the ACM (JACM), v.27 n.2, p.228-234, April 1980 [doi>10.1145/322186.322188]
• 21: PINTER, S. Distributed Computation Systems. Ph.D. dissertation, Boston Univ., Boston, Mass., 1983.
• 22: RABIN, M.O. Randomized Byzantine generals. In Proceedings of the 24th Annual Symposium on Foundations of Computer Science. IEEE, New York, 1983, pp. 403-409.
• 23: Eric C. Rosen, Vulnerabilities of network control protocols: an example, ACM SIGSOFT Software Engineering Notes, v.6 n.1, p.6-8, January 1981 [doi>10.1145/1005920.1005923]
• 24: 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]
• 23: YAO, A.C. Theory and applications of trapdoor functions. In Proceedings of the 23rd 1EEE Symposium on Foundation of Computer Science. IEEE, New York, 1982, pp. 80-91.

INDEX TERMS

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

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

General Terms:
Algorithms, Performance, Reliability, Security, Theory