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.2018.17
URN: urn:nbn:de:0030-drops-98061
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9806/
Go to the corresponding LIPIcs Volume Portal

Daian, Eli ; Losa, Giuliano ; Afek, Yehuda ; Gafni, Eli

A Wealth of Sub-Consensus Deterministic Objects

pdf-format:
LIPIcs-DISC-2018-17.pdf (0.5 MB)

Abstract

The consensus hierarchy classifies shared an object according to its consensus number, which is the maximum number of processes that can solve consensus wait-free using the object. The question of whether this hierarchy is precise enough to fully characterize the synchronization power of deterministic shared objects was open until 2016, when Afek et al. showed that there is an infinite hierarchy of deterministic objects, each weaker than the next, which is strictly between i and i+1-processors consensus, for i >= 2. For i=1, the question whether there exist a deterministic object whose power is strictly between read-write and 2-processors consensus, remained open.
We resolve the question positively by exhibiting an infinite hierarchy of simple deterministic objects which are equivalent to set-consensus tasks, and thus are stronger than read-write registers, but they cannot implement consensus for two processes. Still our paper leaves a gap with open questions.

BibTeX - Entry

@InProceedings{daian_et_al:LIPIcs:2018:9806,
  author =	{Eli Daian and Giuliano Losa and Yehuda Afek and Eli Gafni},
  title =	{{A Wealth of Sub-Consensus Deterministic Objects}},
  booktitle =	{32nd International Symposium on Distributed Computing  (DISC 2018)},
  pages =	{17:1--17:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Ulrich Schmid and Josef Widder},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9806},
  URN =		{urn:nbn:de:0030-drops-98061},
  doi =		{10.4230/LIPIcs.DISC.2018.17},
  annote =	{Keywords: shared memory, distributed algorithms, wait-free, set consensus}
}

Keywords: shared memory, distributed algorithms, wait-free, set consensus
Collection: 32nd International Symposium on Distributed Computing (DISC 2018)
Issue Date: 2018
Date of publication: 04.10.2018

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