2026-07-25T03:04:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19507 2024-03-06T11:04:10Z ddc:004 open_access

A Wait-Free Deque With Polylogarithmic Step Complexity Asbell, Shalom M. Ruppert, Eric Lock-Free Wait-Free Double-Ended Queue Deque Stack Space-Bounded Polylogarithmic Linearizable 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shalom M. Asbell and Eric Ruppert 2024 Is Part Of LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2023.17 urn:nbn:de:0030-drops-195073 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.17 eng https://creativecommons.org/licenses/by/4.0/legalcode