CARNEGIE-MELLON UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE
Pagination or Media Count:
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.
- Operations Research
- Computer Programming and Software