A modular approach to shared-memory consensus, with applications to the probabilistic-write model
James Aspnes · 2010
We define two new classes of shared-memory objects: ratifiers, 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.