On the minimal synchronism needed for distributed consensus | Journal of the ACM
- ️StockmeyerLarry
- ️Thu Jan 01 1987
Abstract
Reaching agreement is a primitive of distributed computing. Whereas this poses no problem in an ideal, failure-free environment, it imposes certain constraints on the capabilities of an actual system: A system is viable only if it permits the existence of consensus protocols tolerant to some number of failures. Fischer et al. have shown that in a completely asynchronous model, even one failure cannot be tolerated. In this paper their work is extended: Several critical system parameters, including various synchrony conditions, are identified and how varying these affects the number of faults that can be tolerated is examined. The proofs expose general heuristic principles that explain why consensus is possible in certain models but not possible in others.
References
[1]
AGHILI, H., ASTRAHAN, M., FINKELSTEIN, S., KIM, W., MCPHERSON, J., SCHKOLNICK, M., AND STRONG, R. A prototype for a highly available database system. Rep. RJ 3755, IBM Research Division, San Jose, Calif., 1983.
[2]
ATTIYA, C., DOLEV, D., AND GIL, J. Asynchronous Byzantine consensus. In Proceedings of the 3rd Annual ACM Symposium on Principles of Distributed Computing (Vancouver, B.C., Canada, Aug. 27-29). ACM, New York, 1984, pp. 119-133.
[3]
BEN-OR, M. Another advantage of free choice: Completely asynchronous agreement protocols. In Proceedings of the 2nd Annual ACM Symposium on Principles of Distributed Computing (Montreal, Quebec, Canada, Aug. 17-19). ACM, New York, 1983, pp. 27-30.
[4]
BEN-OR, M. Fast asynchronous Byzantine agreement. In Proceedings of the 4th Annual ACM Symposium on Principles of Distributed Computing (Minaki, Ontario, Canada, Aug. 5-7). ACM, New York, 1985, pp. 149-151.
[5]
BRACHA, G. An asynchronous t(n - 1)/3.I-resilient consensus protocol. In Proceedings of the 3rd Annual ACM Symposium on Principles of Distributed Computing (Vancouver, B.C., Canada, Aug. 27-29). ACM, New York, 1984, pp. 154-162.
[6]
DOLEV, D., AND REmCHUK, R. Bounds on information exchange for Byzantine agreement. In Proceedings of the ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (Ottawa, Canada, Aug. 18-20). ACM, New York, 1982, pp. 132-140.
[7]
DOLEV, D., AND STRONG, H. R. Authenticated algorithms for Byzantine agreement. SIAM J. Comput. 12 (1983), 656-666.
[8]
DOLEV, D., REISCHUK, R., AND STRONG, H.R. Eventual is earlier than immediate. In Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science (Chicago, I11., Nov. 3-5). IEEE, New York, 1982, pp. 196-203.
[9]
DWORK, C., LYNCH, L., AND STOCKMEYER, L. Consensus in the presence of partial synchrony. IBM Res. Rep. RJ 4892, IBM Research Division, San Jose, Calif., Oct. 1985.
[10]
FISCHER, M. J., LYNCH, N. A., AND PATERSON, M.S. Impossibility of distributed consensus with one faulty process. J. ACM 32 (1985), 374-382.
[11]
LAMPORT, L., SHOSTAK, R., AND PEASE, M. The Byzantine generals problem. ACM Trans. Program. Lang. Syst. 4, 3 (July 1982), 382-401.
[12]
PEASE, M., SHOSTAK, R., AND LAMPORT, L. Reaching agreement in the presence of faults, j. ACM 27, 2 (Apr. 1980), 228-234.
[13]
RAmN, M.O. Randomized Byzantine generals. In Proceedings of the 24th Annual IEEE Symposium on Foundations of Computer Science (Tucson, Ariz., Nov. 7-9). IEEE, New York, pp. 403-409.
[14]
TOUEG, S. Randomized Byzantine agreements. In Proceedings of the 3rdAnnualACMSymposium on Principles of Distributed Computing (Vancouver, B.C., Canada, Aug. 27-29). ACM, New York, 1984, pp. 163-178.
Information & Contributors
Information
Published In
Journal of the ACM Volume 34, Issue 1
Jan. 1987
219 pages
Copyright © 1987 ACM.
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 01 January 1987
Published in JACM Volume 34, Issue 1
Permissions
Request permissions for this article.
Check for updates
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- Downloads (Last 12 months)258
- Downloads (Last 6 weeks)49
Reflects downloads up to 10 Feb 2025
Other Metrics
Citations
- Delporte-Gallet CFauconnier HFraigniaud PRabie M(2025)Distributed computing in the asynchronous LOCAL modelTheoretical Computer Science10.1016/j.tcs.2024.1149521025:COnline publication date: 2-Feb-2025
- Raynal M(2025)Invited Paper: Distributed Computability: A Few Results Masters Students Should KnowDistributed Computing and Intelligent Technology10.1007/978-3-031-81404-4_3(24-44)Online publication date: 8-Jan-2025
- Nowak TSchmid UWinkler K(2024)Topological Characterization of Consensus in Distributed SystemsJournal of the ACM10.1145/368730271:6(1-48)Online publication date: 22-Aug-2024
- Amiri MAgrawal DEl Abbadi ALoo BBarcelo PSanchez-Pi NMeliou ASudarshan S(2024)Distributed Transaction Processing in Untrusted EnvironmentsCompanion of the 2024 International Conference on Management of Data10.1145/3626246.3654684(570-579)Online publication date: 9-Jun-2024
- Hammar KStadler R(2024)Intrusion Tolerance for Networked Systems through Two-Level Feedback Control2024 54th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN)10.1109/DSN58291.2024.00042(338-352)Online publication date: 24-Jun-2024
- Barroso-Fernández CJiménez ELópez-Presa JMoreno-Cuesta MXulvi-Brunet R(2024)Optimizing Gossiping for Asynchronous Fault-Prone IoT Networks With Memory and Battery ConstraintsIEEE Access10.1109/ACCESS.2023.334902112(4701-4715)Online publication date: 2024
- Chaurasia BVerma AVerma P(2024)An in-depth and insightful exploration of failure detection in distributed systemsComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2024.110432247:COnline publication date: 18-Jul-2024
- Freitas ARodrigues LDuarte E(2024)vCubeChainAd Hoc Networks10.1016/j.adhoc.2024.103461158:COnline publication date: 1-May-2024
- Allam AGomaa IZayed HTaha M(2024)IoT-based eHealth using blockchain technology: a surveyCluster Computing10.1007/s10586-024-04357-y27:6(7083-7110)Online publication date: 1-Sep-2024
- Raynal M(2024)On Distributed Computing: A View, Physical Versus Logical Objects, and a Look at Fully Anonymous SystemsStabilization, Safety, and Security of Distributed Systems10.1007/978-3-031-74498-3_1(3-19)Online publication date: 20-Oct-2024
- Show More Cited By
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.