Impossibility of distributed consensus with one faulty process

• Michael J. Fischer

  Department of Computer Science, Yale University, P.O. Box 2158, Yale Station, New Haven, CT

• Nancy A. Lynch

  Laboratory for Computer Science, Massachusetts Institute of Technology, 545 Technology Square, Cambridge, MA

• Michael S. Paterson

  Department of Computer Science, University of Warwick, Coventry CV4 7AL, England

抄録

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. In this paper, it is shown 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.

収録刊行物

• Journal of the ACM

  Journal of the ACM 32 (2), 374-382, 1985-04

  Association for Computing Machinery (ACM)

キーワード

• Artificial Intelligence
• Hardware and Architecture
• Information Systems
• Control and Systems Engineering
• Software

詳細情報

• CRID: 1363951793936986624
• NII論文ID: 80002541839
• NII書誌ID: AA10634930
• DOI: 10.1145/3149.214121
• ISSN: 1557735X
• ISSN: 00045411
• Web Site: https://dl.acm.org/doi/pdf/10.1145/3149.214121
• データソース種別:
  • Crossref
  • CiNii Articles