Access Restriction

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

   Open content in new tab
Source: ACM Digital Library