Impossibility of Distributed Consensus with One Fault Process.

reportActive / Technical Report | Accession Number: ADA120161 | Open PDF

Abstract:

The consensus problem involves an asynchronous system of processes, some of which may be unreliable. The problem is for the reliable processes to agree on a binary value. We show that every protocol for this problem has the possibility of nontermination, even with only one faulty process. By way of contrast, solutions are known for the synchronous case, the Byzantine Generals problem.

Author(s):
Fischer, Michael J. ; Lynch, Nancy A. ; Paterson, Michael S.
Author Organization(s):
YALE UNIV NEW HAVEN CT DEPT OF COMPUTER SCIENCE
Descriptive Note:
Technical rept.,
Supplementary Note:
Sponsored in part by Grants NSF-MCS79-24370 and NSF-MCS81-16678.
Pagination:
0015

Security Markings

DOCUMENT & CONTEXTUAL SUMMARY

Distribution:
Approved For Public Release

RECORD

Collection: TR
Identifying Numbers
Report Number(s):
RR-245
Contract/Grant Number(s):
N00014-82-K-0154, DAAG29-79-C-0155
 Subject Terms
Joint Capability Areas:
JCA_8.1.3_Influence Adversary and Competitor Audiences; JCA_8.1_Communicate; JCA_8_Building Partnerships; JCA_5_Command and Control; JCA_6_Net Centric; JCA_6.1_Information Transport; JCA_5.4_Decide; JCA_6.2.1_Information Sharing; JCA_6.2.2_Computing Services; JCA_1.2_Force Preparation; JCA_1_Force Support; JCA_1.2.3_Educating; JCA_5.3_Planning; JCA_6.2_Enterprise Services
Communities of Interest:
Materials and Manufacturing Processes
Descriptor(s):
*DISTRIBUTED DATA PROCESSING, *FAULT TOLERANT COMPUTING, *FAILURE(ELECTRONICS), *ASYNCHRONOUS COMPUTERS, DATA BASES, CONFIGURATIONS, MESSAGE PROCESSING, RELIABILITY(ELECTRONICS), REMOTE SYSTEMS
Field(s)/Group(s):
Numerical Mathematics, Computer Hardware, Computer Systems
Keyword(s):
Protocols, Byzantine generals problem, WUNR049456
Report Date:
1982 Sep 01