License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2021.28
URN: urn:nbn:de:0030-drops-158030
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15803/
Go to the corresponding LIPIcs Volume Portal

Hwang, Steven Munsu ; Woelfel, Philipp

Strongly Linearizable Linked List and Queue

pdf-format:
LIPIcs-OPODIS-2021-28.pdf (0.7 MB)

Abstract

Strong linearizability is a correctness condition conceived to address the inadequacies of linearzability when using implemented objects in randomized algorithms. Due to its newfound nature, not many strongly linearizable implementations of data structures are known. In particular, very little is known about what can be achieved in terms of strong linearizability with strong primitives that are available in modern systems, such as the compare-and-swap (CAS) operation.
This paper kick-starts the research into filling this gap. We show that Harris’s linked list and Michael and Scott’s queue, two well-known lock-free, linearizable data structures, are not strongly linearizable. In addition, we give modifications to these data structures to make them strongly linearizable while maintaining lock-freedom. The algorithms we describe are the first instances of non-trivial, strongly linearizable data structures of their type not derived by a universal construction.

BibTeX - Entry

@InProceedings{hwang_et_al:LIPIcs.OPODIS.2021.28,
  author =	{Hwang, Steven Munsu and Woelfel, Philipp},
  title =	{{Strongly Linearizable Linked List and Queue}},
  booktitle =	{25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
  pages =	{28:1--28:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-219-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{217},
  editor =	{Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/15803},
  URN =		{urn:nbn:de:0030-drops-158030},
  doi =		{10.4230/LIPIcs.OPODIS.2021.28},
  annote =	{Keywords: Strong linearizability, compare-and-swap, linked list, queue, lock-freedom}
}

Keywords: Strong linearizability, compare-and-swap, linked list, queue, lock-freedom
Collection: 25th International Conference on Principles of Distributed Systems (OPODIS 2021)
Issue Date: 2022
Date of publication: 28.02.2022

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