Reference
[AspnesH90] Fast randomized consensus using shared memory. In Journal of Algorithms, 11: 441-461, 1990.Downloads: bibAbstract. 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(n 4 ) operations. Applications of this algorithm include the elimination of critical sections from concurrent data structures and the construction of asymptotically unbiased shared coins.
