1 Search Results for "Bonin, Grégoire"

Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2019.38
Brief Announcement: Wait-Free Universality of Consensus in the Infinite Arrival Model

Authors: Grégoire Bonin, Achour Mostéfaoui, and Matthieu Perrin

Published in: LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019)

Abstract
In classical asynchronous distributed systems composed of a fixed number n of processes where some proportion may fail by crashing, many objects do not have a wait-free linearizable implementation (e.g. stacks, queues, etc.). It has been proved that consensus is universal in such systems, which means that this system augmented with consensus objects allows to implement any object that has a sequential specification. In this paper, we consider a more general system model called infinite arrival model where infinitely many processes may arrive and leave or crash during a run. We prove that consensus is still universal in this more general model. For that, we propose a universal construction based on a weak log that can be implementated using consensus objects.
Cite as

Grégoire Bonin, Achour Mostéfaoui, and Matthieu Perrin. Brief Announcement: Wait-Free Universality of Consensus in the Infinite Arrival Model. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 38:1-38:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bonin_et_al:LIPIcs.DISC.2019.38,
  author =	{Bonin, Gr\'{e}goire and Most\'{e}faoui, Achour and Perrin, Matthieu},
  title =	{{Brief Announcement: Wait-Free Universality of Consensus in the Infinite Arrival Model}},
  booktitle =	{33rd International Symposium on Distributed Computing (DISC 2019)},
  pages =	{38:1--38:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-126-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{146},
  editor =	{Suomela, Jukka},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.38},
  URN =		{urn:nbn:de:0030-drops-113454},
  doi =		{10.4230/LIPIcs.DISC.2019.38},
  annote =	{Keywords: Concurrent object, Consensus, Infinite arrival model, Linearizability, Universal construction, Wait-freedom}
}
  • Refine by Author
  • 1 Bonin, Grégoire
  • 1 Mostéfaoui, Achour
  • 1 Perrin, Matthieu

  • Refine by Classification
  • 1 Theory of computation → Distributed computing models

  • Refine by Keyword
  • 1 Concurrent object
  • 1 Consensus
  • 1 Infinite arrival model
  • 1 Linearizability
  • 1 Universal construction
  • Show More...

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2019

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