2026-07-23T14:39:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15803 2024-03-12T12:00:35Z ddc:004 open_access

Strongly Linearizable Linked List and Queue Hwang, Steven Munsu Woelfel, Philipp Strong linearizability compare-and-swap linked list queue lock-freedom 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Steven Munsu Hwang and Philipp Woelfel 2022 Is Part Of LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2021.28 urn:nbn:de:0030-drops-158030 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.28 eng https://creativecommons.org/licenses/by/4.0/legalcode