1 Search Results for "Capdevielle, Claire"

Document
DOI: 10.4230/LIPIcs.OPODIS.2015.12
On the Uncontended Complexity of Anonymous Consensus

Authors: Claire Capdevielle, Colette Johnen, Petr Kuznetsov, and Alessia Milani

Published in: LIPIcs, Volume 46, 19th International Conference on Principles of Distributed Systems (OPODIS 2015)

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.
Cite as

Claire Capdevielle, Colette Johnen, Petr Kuznetsov, and Alessia Milani. On the Uncontended Complexity of Anonymous Consensus. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{capdevielle_et_al:LIPIcs.OPODIS.2015.12,
  author =	{Capdevielle, Claire and Johnen, Colette and Kuznetsov, Petr and Milani, Alessia},
  title =	{{On the Uncontended Complexity of Anonymous Consensus}},
  booktitle =	{19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
  pages =	{12:1--12:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-98-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{46},
  editor =	{Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.12},
  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}
}
  • Refine by Author
  • 1 Capdevielle, Claire
  • 1 Johnen, Colette
  • 1 Kuznetsov, Petr
  • 1 Milani, Alessia

  • Refine by Classification

  • Refine by Keyword
  • 1 consensus
  • 1 interval contention
  • 1 lower bounds
  • 1 solo-fast
  • 1 space and time complexity

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2016

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact