Reaching Agreement in the Presence of Faults (original) (raw)
Published: 01 April 1980 Publication History
Abstract
The problem addressed here concerns a set of isolated processors, some unknown subset of which may be faulty, that communicate only by means of two-party messages. Each nonfaulty processor has a private value of information that must be communicated to each other nonfaulty processor. Nonfaulty processors always communicate honestly, whereas faulty processors may lie. The problem is to devise an algorithm in which processors communicate their own values and relay values received from others that allows each nonfaulty processor to infer a value for each other processor. The value inferred for a nonfaulty processor must be that processor's private value, and the value inferred for a faulty one must be consistent with the corresponding value inferred by each other nonfaulty processor.
It is shown that the problem is solvable for, and only for, n ≥ 3_m_ + 1, where m is the number of faulty processors and n is the total number. It is also shown that if faulty processors can refuse to pass on information but cannot falsely relay information, the problem is solvable for arbitrary n ≥ m ≥ 0. This weaker assumption can be approximated in practice using cryptographic methods.
References
[1]
DAvIEs, D, AND WAKEH~Y, J. Synchronization and matching m redundant systems IEEE Trans on Comptrs. C-27, 6 (June 1978), 531-539.
[2]
DIFFIE, W, AND BELLMAN, M. New dtrections in cryptography. IEEE Trans Inform. Theory IT-22, 6 (Nov 1976), 644-654
[3]
RIVEST, R.L., SHArerS, A, Am) ADLEMAN, L A A method for obtaming dtgltal signatures and pubhc-key cryptosystems. Comm. ACM 21, 2 (Feb 1978), 120-126.
[4]
WENSLEY, J H., ET ^L. SIFT: destgn and analysis of a fault-tolerant computer for aircraft control Proc. IEEE 66, 10 (Oct. 1978), 1240-1255.
Information & Contributors
Information
Published In
Journal of the ACM Volume 27, Issue 2
April 1980
196 pages
Copyright © 1980 ACM.
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 01 April 1980
Published in JACM Volume 27, Issue 2
Permissions
Request permissions for this article.
Check for updates
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations
- Downloads (Last 12 months)959
- Downloads (Last 6 weeks)116
Reflects downloads up to 14 Nov 2024
Other Metrics
Citations
- Hao RDing CDai XFan HXiang J(2025)High-performance BFT consensus for Metaverse through block linking and shortcut loopComputer Communications10.1016/j.comcom.2024.107990229(107990)Online publication date: Jan-2025
- Kong ZXu HPan C(2024)R-DOCO: Resilient Distributed Online Convex Optimization Against Adversarial AttacksMathematics10.3390/math1221343912:21(3439)Online publication date: 3-Nov-2024
- Dong HLiu S(2024)Asynchronous Consensus Quorum Read: Pioneering Read Optimization for Asynchronous Consensus ProtocolsElectronics10.3390/electronics1303048113:3(481)Online publication date: 23-Jan-2024
- Mišić VNaderi Mighan SMišić JChang X(2024)Decentralization Is Good or Not? Defending Consensus in Ethereum 2.0Blockchains10.3390/blockchains20100012:1(1-19)Online publication date: 23-Jan-2024
- Cao LGao W(2024)Resilient Distributed Optimization Algorithm Based on Trusted Nodes against Malicious Attacks2024 43rd Chinese Control Conference (CCC)10.23919/CCC63176.2024.10662289(5943-5948)Online publication date: 28-Jul-2024
- Guba ZFinta IBudai ÁFarkas LZimborás ZPályi A(2024)Resource analysis for quantum-aided Byzantine agreement with the four-qubit singlet stateQuantum10.22331/q-2024-04-30-13248(1324)Online publication date: 30-Apr-2024
- Almeida P(2024)Approaches to Conflict-free Replicated Data TypesACM Computing Surveys10.1145/369524957:2(1-36)Online publication date: 9-Sep-2024
- Kowalski VMostefaoui APerrin MGramoli V(2024)Invited Paper: Causal Mutual Byzantine BroadcastProceedings of the 2024 Workshop on Advanced Tools, Programming Languages, and PLatforms for Implementing and Evaluating algorithms for Distributed systems10.1145/3663338.3663679(1-8)Online publication date: 17-Jun-2024
- Hajiaghayi MKowalski DOlkowski JKuznetsov PGelles ROlivetti D(2024)Nearly-Optimal Consensus Tolerating Adaptive Omissions: Why a Lot of Randomness is Needed?Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662826(321-331)Online publication date: 17-Jun-2024
- Civit PDzulfikar MGilbert SGuerraoui RKomatovic JVidigueira MKuznetsov PGelles ROlivetti D(2024)DARE to Agree: Byzantine Agreement With Optimal Resilience and Adaptive CommunicationProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662792(145-156)Online publication date: 17-Jun-2024
- Show More Cited By
View Options
View options
View or Download as a PDF file.
eReader
View online with eReader.
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Full Access
Media
Figures
Other
Tables
Affiliations
M. Pease
Computer Science Laboratory, SRI International, 333 Ravenswood Avenue, Menlo Park, CA
R. Shostak
Computer Science Laboratory, SRI International, 333 Ravenswood Avenue, Menlo Park, CA
L. Lamport
Computer Science Laboratory, SRI International, 333 Ravenswood Avenue, Menlo Park, CA