Document Open Access Logo

Strongly Linearizable Linked List and Queue

Authors Steven Munsu Hwang, Philipp Woelfel

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2021.28.pdf
  • Filesize: 0.67 MB
  • 20 pages

Document Identifiers

Author Details

Steven Munsu Hwang
  • University of Calgary, Canada
Philipp Woelfel
  • University of Calgary, Canada

Funding

We acknowledge the support of the Natural Sciences and Engineering Research Council of Canada (NSERC) under Discovery Grant RGPIN-2019-04852, and the Canada Research Chairs program.

Cite As Get BibTex

Steven Munsu Hwang and Philipp Woelfel. Strongly Linearizable Linked List and Queue. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 28:1-28:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.OPODIS.2021.28

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Shared memory algorithms
Keywords
  • Strong linearizability
  • compare-and-swap
  • linked list
  • queue
  • lock-freedom

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. H. Attiya, A. Castañeda, and D. Hendler. Nontrivial and universal helping for wait-free queues and stacks. Journal of Parallel and Distributed Computing, 121:1-14, 2018. Google Scholar
  2. O. Denysyuk and P. Woelfel. Wait-freedom is harder than lock-freedom under strong linearizability. In International Symposium on Distributed Computing, pages 60-74, 2015. Google Scholar
  3. M.J. Fischer, N.A. Lynch, and M. Paterson. Impossibility of distributed consensus with one faulty process. Journal of the Association for Computing Machinery, 32(2):374-382, 1985. URL: https://doi.org/db/journals/jacm/FischerLP85.html,10.1145/3149.214121.
  4. G. Giakkoupis, M.J. Giv, and P. Woelfel. Efficient randomized DCAS. In Proceedings of the 53rd Symposium on Theory of Computing, pages 1221-1234. ACM, 2021. Google Scholar
  5. W. Golab, L. Higham, and P. Woelfel. Linearizable implementations do not suffice for randomized distributed computation. In Proceedings of the 43rd Symposium on Theory of Computing, pages 373-382, New York, NY, USA, 2011. Association for Computing Machinery. Google Scholar
  6. T.L. Harris. A pragmatic implementation of non-blocking linked-lists. In Proceedings of the 15th International Conference on Distributed Computing, pages 300-314, Berlin, Heidelberg, 2001. Springer-Verlag. Google Scholar
  7. M. Helmi, L. Higham, and P. Woelfel. Strongly linearizable implementations: possibilities and impossibilities. In Proceedings of the 2012 ACM symposium on Principles of Distributed Computing, pages 385-394, 2012. Google Scholar
  8. M.P. Herlihy. Wait-free synchronization. ACM Trans. Program. Lang. Syst., 13(1):124-149, January 1991. Google Scholar
  9. M.P. Herlihy and J.M. Wing. Linearizability: A correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst., 12(3):463-492, July 1990. Google Scholar
  10. M. Loui and H. Abu-Amara. Memory requirements for agreement among unreliable asynchronous processes. Advances in Computing research, 4:163-183, 1987. Google Scholar
  11. M.M. Michael and M.L. Scott. Simple, fast, and practical non-blocking and blocking concurrent queue algorithms. In Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing, pages 267-275, New York, NY, USA, 1996. Association for Computing Machinery. Google Scholar
  12. S. Ovens and P. Woelfel. Strongly linearizable implementations of snapshots and other types. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, pages 197-206. ACM, 2019. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact