### Reaching Agreement in the Presence of FaultsReaching Agreement in the Presence of Faults

Access Restriction
Subscribed

 Author Pease, M. ♦ Shostak, R. ♦ Lamport, L. Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1980 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science 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, $\textit{n}$ ≥ $3\textit{m}$ + 1, where $\textit{m}$ is the number of faulty processors and $\textit{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 $\textit{n}$ ≥ $\textit{m}$ ≥ 0. This weaker assumption can be approximated in practice using cryptographic methods. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1980-04-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 27 Issue Number 2 Page Count 7 Starting Page 228 Ending Page 234

#### Open content in new tab

Source: ACM Digital Library