License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2015.12
URN: urn:nbn:de:0030-drops-66034
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6603/
Go to the corresponding LIPIcs Volume Portal

Capdevielle, Claire ; Johnen, Colette ; Kuznetsov, Petr ; Milani, Alessia

On the Uncontended Complexity of Anonymous Consensus

pdf-format:
LIPIcs-OPODIS-2015-12.pdf (0.7 MB)

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 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 interval-solo-fast and derive one of the first nontrivial tight bounds on space complexity of anonymous interval-solo-fast consensus.

BibTeX - Entry

@InProceedings{capdevielle_et_al:LIPIcs:2016:6603,
  author =	{Claire Capdevielle and Colette Johnen and Petr Kuznetsov and Alessia Milani},
  title =	{{On the Uncontended Complexity of Anonymous Consensus}},
  booktitle =	{19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
  pages =	{1--16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-98-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{46},
  editor =	{Emmanuelle Anceaume and Christian Cachin and Maria Potop-Butucaru},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6603},
  URN =		{urn:nbn:de:0030-drops-66034},
  doi =		{10.4230/LIPIcs.OPODIS.2015.12},
  annote =	{Keywords: space and time complexity, lower bounds, consensus, interval contention, solo-fast}
}

Keywords: space and time complexity, lower bounds, consensus, interval contention, solo-fast
Collection: 19th International Conference on Principles of Distributed Systems (OPODIS 2015)
Issue Date: 2016
Date of publication: 13.10.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI