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