Impossibility of Distributed Consensus with One Faulty 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. (Author)

Open PDF

Document Details

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

Entities

People

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

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

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

Fields of Study

  • Mathematics

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.