Impossibility of Distributed Consensus with One Fault Process.

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 01, 1982
Accession Number
ADA120161

Entities

People

  • Michael J. Fischer
  • Michael S. Paterson
  • Nancy Lynch

Organizations

  • Yale University

Tags

Communities of Interest

  • C4I
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Abstracts
  • Agreements
  • Algorithms
  • Asynchronous Systems
  • Computations
  • Computer Networks
  • Computer Science
  • Computers
  • Contrast
  • Data Processing
  • Data Storage Systems
  • Distributed Data Processing
  • Information Processing
  • Information Systems
  • Message Systems
  • Military Research
  • Sequences

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.