A Generic Consensus Algorithm for Shared Memory

The shared memory model matches important classes of modern applications, such as fault-tolerant and highly available data centric services. Consensus is an important building block able to realize such reliable distributed systems. However, there exists no deterministic solution to consensus in asynchronous systems prone to failures. Failure and leader detectors are elegant abstractions which encapsulate the extra synchrony necessary to circumvent this impossibility. In this paper, we present a generic consensus algorithm for asynchronous shared memory systems able to be instantiated with two fundamental detectors, namely ◇S and Ω. The algorithm is wait-free, tolerating up to n - 1 failures, and optimal, regarding the synchrony required and the number of registers it uses.