Skip to Main content Skip to Navigation

On the Uncontended Complexity of Anonymous Consensus

Abstract : Consensus is one of the central distributed abstractions. By enabling a collection of processes to agree on one of the values they propose, consensus can be used to implement any generic replicated service in a consistent and fault-tolerant way. In this paper, we study \emph{uncontended} complexity of anonymous consensus algorithms, counting the number of memory locations used and the number of memory updates performed in operations that encounter no contention. We assume that contention-free operations on a consensus object perform ``fast'' reads and writes, and resort to more expensive synchronization primitives, such as CAS, only when contention is detected. We call such concurrent implementations \emph{interval-solo-fast} and derive the first nontrivial tight bounds on space complexity of anonymous interval-solo-fast consensus.
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download
Contributor : Alessia Milani Connect in order to contact the contributor
Submitted on : Tuesday, July 28, 2015 - 12:19:22 PM
Last modification on : Friday, April 9, 2021 - 4:28:06 PM
Long-term archiving on: : Thursday, October 29, 2015 - 10:52:27 AM


Files produced by the author(s)


  • HAL Id : hal-01180864, version 1


Claire Capdevielle, Colette Johnen, Petr Kuznetsov, Alessia Milani. On the Uncontended Complexity of Anonymous Consensus. [Research Report] University of Bordeaux LaBRI, UMR 5800, F-33400 Talence, France Telecom ParisTech. 2015. ⟨hal-01180864⟩



Record views


Files downloads