Reaching Approximate Agreement in the Presence of Faults.

Abstract

This paper considers a variant on the Byzantine GEnerals problem, in which processes start with arbitrary real values rather than Boolean values or values from some bounded range, and in which approximate, rather than exact, agreement is the desired goal. Algorithms are presented to reach approximate agreement in asynchronous, as well as synchronous systems. The asynchronous agreement algorithm is an interesting contrast to a result of Fischer, Lynch, and Patterson, who show that exact agreement in not attainable in an asynchronous system with a provable convergence rate that depends on the ration between the number of faults and the number of processes. Lower bounds on the convergence rate for algorithms of this form are proven, and the algorithms presented are shown to be optimal. Keywords: Agreement protocols; fault-tolerance; Byzantine Generals; Approximate agreement; Distributed systems.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 1985
Accession Number
ADA156541

Entities

People

  • D. Dolev
  • E. W. Stark
  • N. A. Lynch
  • S. S. Pinter
  • W. E. Weihl

Organizations

  • Massachusetts Institute of Technology

Tags

DTIC Thesaurus Topics

  • Agreements
  • Algorithms
  • Asynchronous Systems
  • Classification
  • Computations
  • Computer Science
  • Contracts
  • Contrast
  • Convergence
  • Diameters
  • Distributed Computing
  • Fault Tolerance
  • Information Processing
  • Military Research
  • Real Numbers
  • Security
  • Standards

Readers

  • Computer Networking
  • International Relations and European Studies
  • Mathematical Modeling and Probability Theory.