# Faster randomized consensus with an oblivious adversary

James Aspnes.
Faster randomized consensus with an oblivious adversary.
*Distributed Computing* 28(1):21–29, February 2015. (PODC 2012 special issue). An earlier version appeard in *2012 ACM Symposium on Principles of Distributed Computing*, July 2012, pp. 1–8.

## Abstract

Two new algorithms are given for randomized consensus in a shared-memory model with an oblivious adversary. Each is based on a new construction of a conciliator, an object that guarantees termination and validity, but that only guarantees agreement with constant probability. The first conciliator assumes unit-cost snapshots and achieves agreement among n processes with probability 1-ε in O(log^{*} n + log(1/ε)) steps for each process. The second uses ordinary multi-writer registers, and achieves agreement with probability 1-ε in O(log log n + log(1/ε)) steps. Combining these constructions with known results gives randomized consensus for arbitrarily many possible input values using unit-cost snapshots in O(log* n) expected steps and randomized consensus for up to (log n)^{O(log log log n)} possible input values using ordinary registers in O(log log n) expected steps.

- PODC 2012 proceedings version: PDF.
- Slides from James Aspnes's PODC 2012 talk: PDF.
- Journal version:
**PDF**.

## BibTeX

Download@article{Aspnes2015,
author = {James Aspnes},
title = {Faster randomized consensus with an oblivious adversary},
month = feb,
year = 2015,
journal = {Distributed Computing},
volume = 28,
number = 1,
pages={21--29}
}

Consolidated BibTeX file

Return to James Aspnes's publications

Return to James Aspnes's home page