Creative Commons Attribution 4.0 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: https://drops.dagstuhl.de/opus/volltexte/2022/15803/
Hwang, Steven Munsu ; Woelfel, Philipp
Strongly Linearizable Linked List and Queue
| pdf-format: |
|
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 | |
| Seminar: | 25th International Conference on Principles of Distributed Systems (OPODIS 2021) | |
| Issue date: | 2022 | |
| Date of publication: | 28.02.2022 |
