Skip to Main content Skip to Navigation
Reports

From a Store-collect Object and Ω to Efficient Asynchronous Consensus

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 presents an efficient algorithm that builds a consensus object. This algorithm is based on an $\Omega$ failure detector (to obtain consensus liveness) and a store-collect object (to maintain its safety). A store-collect object provides the processes with two operations, a store operation which allows the invoking process to deposit a new value while discarding the previous value it has deposited and a collect operation that returns to the invoking process a set of pairs $(i, val)$ where $val$ is the last value deposited by the process $p_i$. A store-collect object has no sequential specification. While store-collect objects have been used as base objects to design wait-free constructions of more sophisticated objects (such as snapshot or renaming objects), as far as we know, they have not been explicitly used to built consensus objects. The proposed store-collect-based algorithm, which is round-based, has several noteworthy features. First it uses a single store-collect object (and not an object per round). Second, during a round, a process invokes at most once the store operation and the value $val$ it deposits is a simple pair $\langle r, v \rangle$ where $r$ is a round number and $v$ a proposed value. Third, a process is directed to skip rounds according to its view of the current global state (thereby saving useless computation rounds). Finally, the algorithm benefits from the adaptive wait-free implementations that have been proposed for store-collect objects, namely, the number of shared memory accesses involved in a collect operation is $O(k)$ where $k$ is the number of processes that have invoked the store operation. This makes the proposed algorithm particularly efficient and interesting for multiprocess programs made up of asynchronous crash-prone processes that run on top of multicore architectures.
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download

https://hal.inria.fr/hal-00670076
Contributor : Julien Stainer Connect in order to contact the contributor
Submitted on : Tuesday, February 21, 2012 - 11:20:13 AM
Last modification on : Thursday, January 20, 2022 - 5:33:26 PM
Long-term archiving on: : Wednesday, December 14, 2016 - 6:32:26 AM

File

consensus-omega-store-collect-...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00670076, version 1

Citation

Michel Raynal, Julien Stainer. From a Store-collect Object and Ω to Efficient Asynchronous Consensus. [Research Report] PI-1987, 2011. ⟨hal-00670076⟩

Share

Metrics

Record views

180

Files downloads

185