A Modular Approach to Shared-Memory Consensus, with Applications to the Probabilistic-Write Model

摘要

We define two new classes of shared-memory objects: rati-flers, which detect agreement, and conciliators, which ensure agreement with some probability. We show that consensus can be solved by an alternating sequence of these objects, and observe that most known randomized consensus algorithms have this structure. We give a deterministic m-valued ratifier for an unbounded number of processes that uses lgm + Θ(loglogm) 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 multiwriter 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(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.