James Aspnes. Wait-Free Consensus. PhD thesis, Carnegie-Mellon University, 1992. Available as CMU-CS-TR-92-164.
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 O(n log² n) expected operations. This bound is close to the trivial lower bound of Ω(n), and it substantially improves on the best previously-known bound of O(n² log n), due to Bracha and Rachman.
@phdthesis(Aspnes1992, title="Wait-Free Consensus", author="James Aspnes", school="Carnegie-Mellon University", year=1992 )