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

摘要

We show that consensus can be solved by an alternating sequence of adopt-commit objects (Gafni in Proceedings of the seventeenth annual ACM symposium on principles of distributed computing, pp 143-152, 1998; Alistarh et al. in ISAAC, Lecture notes in computer science, vol 5878. Springer, Berlin, pp 943-953, 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(logn) expected individual work, and Θ(n) expected total work. Combining these objects gives a consensus protocol for the probabilistic-write model that uses O(logm + logn) individual work and O(n logm) total work. No previous protocol in this model uses sublinear individual work or linear total work for constant m.