M. Pease
R. Shostak
L. Lamport
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 ≥ 3m + 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.
- 1 DAvIEs, D, AND WAKEH~Y, J. Synchronization and matching m redundant systems IEEE Trans on Comptrs. C-27, 6 (June 1978), 531-539.Google Scholar
- 2 DIFFIE, W, AND BELLMAN, M. New dtrections in cryptography. IEEE Trans Inform. Theory IT-22, 6 (Nov 1976), 644-654Google Scholar
- 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. Google Scholar
- 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.Google Scholar
Index Terms
- Reaching Agreement in the Presence of Faults
Recommendations
Reaching Fault Diagnosis Agreement under a Hybrid Fault Model
The goal of the fault diagnosis agreement (FDA) problem is to make each fault-free processor detect/locate a common set of faulty processors. The problem is examined on processors with mixed fault model (also referred to as hybrid fault model). An ...
Reaching Approximate Agreement with Mixed-Mode Faults
In a fault-tolerant distributed system, different non-faulty processes may arrive atdifferent values for a given system parameter. To resolve this disagreement, processesmust exchange and vote upon their respective local values. Faulty processes ...
Byzantine Agreement in the Presence of Mixed Faults on Processors and Links
In early stage, the Byzantine agreement (BA) problem was studied with single faults on processors in either a fully connected network or a nonfully connected network. Subsequently, the single fault assumption was extended to mixed faults (also referred ...
Comments