Abstract
Easy proofs are given, of the impossibility of solving several consensus problems (Byzantine agreement, weak agreement, Byzantine firing squad, approximate agreement and clock synchronization) in certain communication graphs.
It is shown that, in the presence ofm faults, no solution to these problems exists for communication graphs with fewer than 3m+1 nodes or less than 2m+1 connectivity. While some of these results had previously been proved, the new proofs are much simpler, provide considerably more insight, apply to more general models of computation, and (particularly in the case of clock synchronization) significantly strengthen the results.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Angluin D (1980) Local and global properties in networks of processors. Proceedings of the 12th STOC, April 30–May 2, 1980, Los Angeles, CA, pp 82–93
Burns J (1980) A formal model for message passing systems, TR-91, Indiana University, Sept
Burns J, Lynch N (1984) The byzantine firing squad problem, (submitted for publication)
Coan B, Dolev D, Dwork C, Stockmeyer L (1985) The distributed firing squad problem, Proceedings of the 17th STOC, May 6–8, 1985, Providence, RI
Dolev D (1982) The byzantine generals strike again. J Algorithms 3:14–30
Dolev D, Halpern J, Strong H (1984) On the possibility and impossibility of achieving clock synchronization. Proceedings of the 16th STOC, April 30–May 2, 1984, Washington, DC, pp 504–510
Dolev D, Lynch NA, Pinter S, Stark E, Weih W (1983) Reaching approximate agreement in the presence of faults, Proceedings of the 3rd Annual IEEE Symposium on Distributed Software and Databases
Itai A, Rodeh M (1981) The lord of the ring or probabilistic methods for breaking symmetry in distributive networks. RJ-3110. IBM Research Report April
Lamport L (1983) The weak byzantine general problem. JACM 30:668–676
Lamport L, Shostak R, Pease M (1982) The byzantine generals problem. ACM Trans Program Lang Syst 4:3 382–401
Mahaney S, Schneider F (1985) Inexact agreement: accuracy, precision, and graceful degradation, Proceedings of the 4th Annual ACM Symposium on Principles of Distributed Computing. August 5–7, 1985, Minacki, Ontario
Pease M, Shostak R, Lamport L (1980) Reaching agreement in the presence of faults. JACM 27:228–234
Author information
Authors and Affiliations
Additional information
Michael J. Fischer is currently Professor of Computer Science at Yale University, New Haven, CT, where he heads the Theory of Computation Group. He is also Editor-in-Chief of the Journal of the Association for Computing Machinery. His research interests include theory of distributed systems, cryptographic protocols, and computational complexity.
Dr. Fischer received the B. S. degree in matheamtics from the University of Michigan, Ann Arbor, in 1963, and the M. A. and Ph. D. degrees in applied mathematics from Harvard University, Cambridge, MA, in 1965 and 1968, respectively. He has taught previously at Carnegie-Mellon University, the Massachusetts Institute of Technology, and University of Washington.
Nancy Lynch is currently Associate professor of Computer Science at M.I.T., and heads the Theory of Distributed Systems group in M.I.T.'s Laboratory for Computer Science. Her interests are in all aspects of distributed computing theory, including formal models, algorithms, analysis, and correctness proofs. Dr. Lynch received the B.S. degree in mathematics from Brooklyn College in 1968 and the Ph. D. degree in mathematics from M.I.T. in 1972. She has served on the faculty of Tufts University, the University of Southern California, Florida International University, Georgia Tech.
Michael Merritt is currently a member of the technical staff with AT&T Bell Laboratories. During the 1984 –85 academic year, he was a visiting lecturer at M.I.T., sponsered by Bell Labs. His research interests include distributed computation, cryptography and security. Dr. Merritt received the B. S. degree in computer science and philosophy from Yale in 1978 and the M. Sc. and Ph. D. degrees in 1980 and 1983, respectively, both in information and computer science from Georgia Tech. He is a member of SIGACT and of Computer Professionals for Social Responsibility.
This paper has appeared in the ACM Conference Proceedings of PODC 1985. © 1985, Association for Computing Machinery, reprinted by permission
Rights and permissions
About this article
Cite this article
Fischer, M.J., Lynch, N.A. & Merritt, M. Easy impossibility proofs for distributed consensus problems. Distrib Comput 1, 26–39 (1986). https://doi.org/10.1007/BF01843568
Issue Date:
DOI: https://doi.org/10.1007/BF01843568