James Aspnes, Hagit Attiya, and Keren Censor. Randomized consensus in expected O(n log n) individual work. In Twenty-Seventh annual ACM Symposium on Principles of Distributed Computing, August 2008, pp. 325–334.
This paper presents a new randomized algorithm for achieving consensus among asynchronous processes that communicate by reading and writing shared registers, in the presence of a strong adversary. The fastest previously known algorithm requires a process to perform an expected O(n log² n) read and write operations in the worst case. In our algorithm, each process executes at most an expected O(n log n) read and write operations. It is shown that shared coin algorithms can be combined together to yield an algorithm with O(n log n) individual work and O(n²) total work.
@inproceedings{AspnesAC2008,
author = {James Aspnes and Hagit Attiya and Keren Censor},
title = {Randomized consensus in expected {$O(n \log n)$} individual work},
month=aug,
year = 2008,
booktitle = {PODC '08: Proceedings of the Twenty-Seventh ACM Symposium on Principles of Distributed Computing},
pages = {325--334}
}