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.31
URN: urn:nbn:de:0030-drops-66201
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6620/
Go to the corresponding LIPIcs Volume Portal

Attiya, Hagit ; Castaneda, Armando ; Hendler, Danny

Nontrivial and Universal Helping for Wait-Free Queues and Stacks

pdf-format:
LIPIcs-OPODIS-2015-31.pdf (0.6 MB)

Abstract

This paper studies two approaches to formalize helping in wait-free implementations of shared objects. The first approach is based on operation valency, and it allows us to make the important distinction between trivial and nontrivial helping. We show that a wait-free implementation of a queue from common2 objects (e.g., Test&Set) requires nontrivial helping. In contrast, there is a wait-free implementation of a stack from Common2 objects with only trivial helping. This separation might shed light on the difficulty of implementing a queue from Common2 objects.

The other approach formalizes the helping mechanism employed by Herlihy's universal wait-free construction and is based on having an operation by one process restrict the possible linearizations of operations by other processes. We show that objects possessing such universal helping can be used to solve consensus.

BibTeX - Entry

@InProceedings{attiya_et_al:LIPIcs:2016:6620,
  author =	{Hagit Attiya and Armando Castaneda and Danny Hendler},
  title =	{{Nontrivial and Universal Helping for Wait-Free Queues and Stacks}},
  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/6620},
  URN =		{urn:nbn:de:0030-drops-66201},
  doi =		{10.4230/LIPIcs.OPODIS.2015.31},
  annote =	{Keywords: helping, wait-free, nonblocking, queues, stacks, common2}
}

Keywords: helping, wait-free, nonblocking, queues, stacks, common2
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