James Aspnes and Orli Waarts. Randomized consensus in expected O(n log² n) operations per processor. SIAM Journal on Computing 25(5):1024–1044, October 1996. An earlier version appeared in Thirty-Third IEEE Symposium on Foundations of Computer Science, October 1992, pp. 137–146.
This paper presents a new randomized algorithm for achieving consensus among asynchronous processors that communicate by reading and writing shared registers. The fastest previously known algorithm requires a processor to perform an expected O(n² log n) read and write operations in the worst case. In our algorithm, each processor executes at most an expected O(n log² n) read and write operations, which is close to the trivial lower bound of Ω(n).
All previously known polynomial-time consensus algorithms were structured around a shared coin protocol in which each processor repeatedly adds random ±1 votes to a common pool. Consequently, in all of these protocols, the worst case expected bound on the number of read and write operations done by a single processor is asymptotically no better than the bound on the total number of read and write operations done by all of the processors together. We succeed in breaking this tradition by allowing the processors to cast votes of increasing weights. This grants the adversary greater control since he can choose from up to n different weights (one for each processor) when determining the weight of the next vote to be cast. We prove that our shared coin protocol is correct nevertheless using martingale arguments.
@article(AspnesW1996,
title="Randomized consensus in expected {$O(n \log^2 n)$} operations per processor",
author="James Aspnes and Orli Waarts",
journal={SIAM Journal on Computing},
volume=25,
number=5,
pages={1024--1044},
month=oct,
year=1996
)