# A modular approach to shared-memory consensus, with applications to the probabilistic-write model

James Aspnes.
A modular approach to shared-memory consensus, with applications to the probabilistic-write model.
*Distributed Computing* 25(2):179–188, May 2012. (PODC 2010 special issue.)
An earlier version appeared in
*Twenty-Ninth Annual ACM SIGACT-SIGOPS Symposium on Principles of
Distributed Computing*, July 2010, pp. 460–467.

## Abstract

We show that consensus can be solved by an alternating sequence of adopt-commit objects (Gafni, 1998; Alistarh et al. 2009), which detect agreement, and conciliators, which ensure agreement with some probability. We observe that most known randomized consensus algorithms have this structure.

We give a deterministic implementation of an m-valued adopt-commit object for an unbounded number of processes that uses lg m + Θ(log log m) space and individual work. We also give a randomized conciliator for any number of values in the probabilistic-write model with n processes that guarantees agreement with constant probability while using one multi-writer register, O(log n) expected individual work, and Θ(n) expected total work. Combining these objects gives a consensus protocol for the probabilistic-write model that uses O(log n) individual work and O(n log m) total work. No previous protocol in this model uses sublinear individual work or linear total work for constant m.

- PODC 2010 proceedings version: PDF. Erratum.
- Full version:
**PDF**.
- Slides from James Aspnes's PODC 2010 talk: PDF.

## BibTeX

Download@article{Aspnes2012modular,
author = {James Aspnes},
title = {A modular approach to shared-memory consensus, with applications to the probabilistic-write model},
month=may,
year = 2012,
journal="Distributed Computing",
volume=25,
number=2,
pages={179--188}
}

Consolidated BibTeX file

Return to James Aspnes's publications

Return to James Aspnes's home page