# Randomized consensus in expected O(n log n) individual work

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.

## Abstract

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.

- PODC 2008 proceedings version:
**PDF**.

## BibTeX

Download@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}
}

Consolidated BibTeX file

Return to James Aspnes's publications

Return to James Aspnes's home page