Easy Impossibility Proofs for Distributed Concensus Problems.

Abstract

Easy proofs are given, of the impossibility of solving several consensus problems (Byzantine agreement, weak agreement, Byzantine firing squad, approximate agreement and clock synchronization) in certain communication graphs. It is shown that, in the presence of m faults, no solution to these problems exists for communication graphs with fewer than 3m+1 nodes or less than 2m+1 connectivity. While some of these results had previously been proved, the new proofs are much simpler, provide considerably more insight, apply to more general needs of computation, and (particularly in the case of clock synchronization) significantly strengthen the results. Keywords: Consensus, Byzantine agreement, Clock synchronization, Distributed computing and fault tolerance.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 1985
Accession Number
ADA157411

Entities

People

  • M. J. Fischer
  • M. Merritt
  • N. A. Lynch

Organizations

  • Yale University

Tags

DTIC Thesaurus Topics

  • Accuracy
  • Agreements
  • Computations
  • Computer Science
  • Contracts
  • Coverings
  • Detection
  • Distributed Computing
  • Fault Tolerance
  • Marine Corps
  • Military Research
  • Network Protocols
  • Network Topology
  • Precision
  • Sequences
  • Technical Information Centers

Fields of Study

  • Mathematics

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Graph Algorithms and Convex Optimization.