James Aspnes. Time- and space-efficient randomized consensus. Journal of Algorithms 14(3):414–431, May 1993. An earlier version appeared in Ninth ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, August 1990, pp. 325–331.
A protocol is presented which solves the randomized consensus problem for shared memory. The protocol uses a total of O(p² + n) worst-case expected increment, decrement and read operations on a set of three shared O(log n)-bit counters, where p is the number of active processors and n is the total number of processors. It requires less space than previous polynomial-time consensus protocols, and is faster when not all of the processors participate in the protocol. A modified version of the protocol yields a weak shared coin whose bias is guaranteed to be in the range 1/2 ± epsilon regardless of scheduler behavior, and which is the first such protocol for the shared-memory model to guarantee that all processors agree on the outcome of the coin.
@article(Aspnes1993,
title="Time- and space-efficient randomized consensus",
author="James Aspnes",
journal={Journal of Algorithms},
volume=14,
number=3,
pages={414--431},
month=may,
year=1993
)