Accession Number:

ADA255978

Title:

Wait-Free Consensus

Descriptive Note:

Doctoral thesis,

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1992-07-24

Pagination or Media Count:

79.0

Abstract:

Consensus is a decision problem in which n processors, each starting with a value not known to the others, must collectively agree on a single value. If the initial values are equal, the processors must agree on that common value- this is the validity condition. A consensus protocol is wait-free if every processor finishes in a finite number of its own steps regardless of the relative speeds of the other processors, a condition that precludes the use of traditional synchronization techniques such as critical sections, locking, or leader election. Wait-free consensus is fundamental to synchronization without mutual exclusion, as it can be used to construct wait-free implementations of arbitrary concurrent data structures. It is known that no deterministic algorithm for wait -free consensus is possible, although many randomized algorithms have been proposed. I present two algorithms for solving the wait- free consensus problem in the standard asynchronous shared-memory model. The first is a very simple, protocol based on a random walk. The second is a protocol based on weighted voting, in which each processor executes 0n log 2 n expected operations. This bound is close to the trivial lower bound of 9n, and it substantially improves on the best previously-known bound of On2 log n due to Bracha and Rachman.

Subject Categories:

  • Operations Research
  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE