DROPS

Document

DOI: 10.4230/LIPIcs.OPODIS.2023.17

A Wait-Free Deque With Polylogarithmic Step Complexity

Authors: Shalom M. Asbell and Eric Ruppert

Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)

Abstract

The amortized step complexity of operations on all previous lock-free implementations of double-ended queues is linear in the number of processes. This paper presents the first concurrent double-ended queue where the amortized step complexity of each operation is polylogarithmic. Since a stack is a special case of a double-ended queue, this is also the first concurrent stack with polylogarithmic step complexity. The implementation is wait-free and the amortized step complexity is O(log² p + log q) per operation, where p is the number of processes and q is the size of the double-ended queue.

Cite as

Shalom M. Asbell and Eric Ruppert. A Wait-Free Deque With Polylogarithmic Step Complexity. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 17:1-17:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{asbell_et_al:LIPIcs.OPODIS.2023.17,
  author =	{Asbell, Shalom M. and Ruppert, Eric},
  title =	{{A Wait-Free Deque With Polylogarithmic Step Complexity}},
  booktitle =	{27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
  pages =	{17:1--17:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-308-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{286},
  editor =	{Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.17},
  URN =		{urn:nbn:de:0030-drops-195073},
  doi =		{10.4230/LIPIcs.OPODIS.2023.17},
  annote =	{Keywords: Lock-Free, Wait-Free, Double-Ended Queue, Deque, Stack, Space-Bounded, Polylogarithmic, Linearizable}
}

Search Results

Documents authored by Asbell, Shalom M.

A Wait-Free Deque With Polylogarithmic Step Complexity

Abstract

Cite as

Thanks for your feedback!

Could not send message