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.DISC.2019.38
URN: urn:nbn:de:0030-drops-113454
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11345/
Go to the corresponding LIPIcs Volume Portal

Bonin, Grégoire ; Mostéfaoui, Achour ; Perrin, Matthieu

Brief Announcement: Wait-Free Universality of Consensus in the Infinite Arrival Model

pdf-format:
LIPIcs-DISC-2019-38.pdf (0.4 MB)

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.

BibTeX - Entry

@InProceedings{bonin_et_al:LIPIcs:2019:11345,
  author =	{Gr{\'e}goire Bonin and Achour Most{\'e}faoui and Matthieu Perrin},
  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 =	{Jukka Suomela},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11345},
  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}
}

Keywords: Concurrent object, Consensus, Infinite arrival model, Linearizability, Universal construction, Wait-freedom
Collection: 33rd International Symposium on Distributed Computing (DISC 2019)
Issue Date: 2019
Date of publication: 08.10.2019

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