Wait-Free Consensus
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 0(n log 2 n) expected operations. This bound is close to the trivial lower bound of 9(n), and it substantially improves on the best previously-known bound of O(n2 log n) due to Bracha and Rachman.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 24, 1992
- Accession Number
- ADA255978
Entities
People
- James Aspnes
Organizations
- Carnegie Mellon University