James Aspnes and Maurice Herlihy. Fast randomized consensus using shared memory. Journal of Algorithms 11(3):441–461, September 1990.
We give a new randomized algorithm for achieving consensus among asynchronous processes that communicate by reading and writing shared registers. The fastest previously known algorithm has exponential expected running time. Our algorithm is polynomial, requiring an expected O(n4) operations. Applications of this algorithm include the elimination of critical sections from concurrent data structures and the construction of asymptotically unbiased shared coins.
@article(AspnesH1990consensus,
title="Fast randomized consensus using shared memory",
author="James Aspnes and Maurice Herlihy",
journal={Journal of Algorithms},
volume=11,
number=3,
pages={441--461},
month=sep,
year=1990
)