Are Wait-Free Algorithms Fast

Abstract

The time complexity of wait-free algorithms in normal executions, where no failures occur and processes operate at approximately the same speed, is considered. A lower bound of log n on the time complexity of any wait-free algorithm that achieves approximate agreement among n processes is proved. In contrast, there exists a non-wait-free algorithm that solves this problem in constant time. This implies an omega (log n) time separation between the wait-free and non-wait-free computation models. On the positive side, we present an O(log n) time wait-free approximate agreement algorithm; the complexity of this algorithm is within a small constant of the lower bound.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 1991
Accession Number
ADA232829

Entities

People

  • Hagit Attiya
  • Nancy Lynch
  • Nir Shavit

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Agreements
  • Algorithms
  • Asynchronous Systems
  • Classification
  • Computations
  • Computer Science
  • Computers
  • Consensus Algorithms
  • Fault Tolerance
  • Guarantees
  • Intervals
  • Iterations
  • Numbers
  • Real Numbers
  • Security
  • Sequences
  • Uncertainty

Fields of Study

  • Computer science

Readers

  • Educational Psychology
  • Linear Algebra
  • Regression Analysis.