Bounded Polynomial Randomized Consensus

Abstract

In (A88), Abrahamson presented a solution to the randomized consensus problem of Chor, Israeli and Li (CIL87), without assuming the existence of anatomic coin flip operation. This elegant algorithm uses unbounded memory, and has expected exponential running time. In (AH89), Aspens and Herlihy provide a breakthrough polynomial-time algorithm. However, it too is based on the use of unbounded memory. In this paper, we present a solution to the randomized consensus problem, that is bounded in space and runs in polynomial expected time.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1989
Accession Number
ADA213808

Entities

People

  • Danny Dolev
  • Hagit Attiya
  • Nir Shavit

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Availability
  • Classification
  • Computer Science
  • Computers
  • Consistency
  • Contracts
  • Information Processing
  • Information Systems
  • Military Research
  • Notation
  • Observation
  • Polynomials
  • Probability
  • Random Walk
  • Security
  • Sequences

Fields of Study

  • Mathematics

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Battery Technology and Engineering

Technology Areas

  • Space