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) : Aspnes, James


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a255978.pdf


Report Date : 24 Jul 1992


Pagination or Media Count : 79


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.


Descriptors :   *VELOCITY , *ALGORITHMS , MODELS , STRUCTURES , THESES , OPERATION , STANDARDS , VALUE , STARTING , NUMBERS , RANDOM WALK


Subject Categories : Operations Research
      Computer Programming and Software


Distribution Statement : APPROVED FOR PUBLIC RELEASE