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

Michel Raynal 1 Julien Stainer 1
1 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
Abstract : 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.
Liste complète des métadonnées

Contributor : Julien Stainer <>
Submitted on : Monday, September 17, 2012 - 5:17:46 PM
Last modification on : Friday, November 16, 2018 - 1:39:16 AM


  • HAL Id : hal-00733082, version 1


Michel Raynal, Julien Stainer. A Simple Asynchronous Shared Memory Consensus Algorithm Based on Omega and Closing Sets. CISIS 2012 - Sixth International Conference on Complex, Intelligent, and Software Intensive Systems, 2012, Palerme, Italy. pp.357-364. ⟨hal-00733082⟩



Record views