A Simple Asynchronous Shared Memory Consensus Algorithm Based on Omega and Closing Sets

This paper is on the design of a consensus object in the context of asynchronous shared memory systems where any number of process can suffer a crash failure. These systems are becoming more and more important with the advent of multicore architectures. To circumvent the impossibility of implementing a consensus object in such a context, the paper considers that the base read/write system model is enriched with an eventual leader failure detector (traditionally denoted Ω). This failure detector can easily be used to ensure that all the invocations of the consensus object issued by processes that do not crash eventually terminate(wait-freedom termination property). Hence, when one has to implement a consensus object in such an enriched system model, the main issue consists in designing an object (from base atomic read/write registers) on which the implementation can rely to ensure that no two different values can be decided from the consensus object. This paper presents such an object, called closing set. The main feature of this object is that it takes advantage of the system asynchrony by reducing the number of values that can be deposited: only concurrent deposits of values in an empty set are successful. The paper presents then a simple consensus algorithm based on closing sets. This algorithm is round-based and uses a closing set per round.