# Randomized consensus in expected O(n log² n) operations per processor

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.

## Abstract

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.

## BibTeX

Download@article(AspnesW1996,
title="Randomized consensus in expected {$O(n \log^2 n)$} operations per processor",
author="James Aspnes and Orli Waarts",
journal=sicomp,
volume=25,
number=5,
pages={1024--1044},
month=oct,
year=1996
)

Consolidated BibTeX file

Return to James Aspnes's publications

Return to James Aspnes's home page