1980/04/01 by Marshall C. Pease, M. Pease, R. Shostak +3 · 2,376 citations
Computer Science · Engineering · Mathematics · #Arithmetic #Computer science #Cooperative Communication and Network Coding #Cryptography and Data Security #Mathematics #Parallel computing #Physics #Power (physics) #Programming language #Relay #Set (abstract data type) #Value (mathematics) #Wireless Communication Security Techniques
paper · pdf · doi:10.1145/322186.322188
published in Journal of the ACM 27(2), 228-234 (Association for Computing Machinery)
openalex publication_date 1980/04/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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.