A Wait-free Queue with Polylogarithmic Step Complexity

DOI10.1145/3583668.3594565MaRDI QIDQ6202234zbMATH OpenOpenAlexFDO

Authors Eric Ruppert

Publication date 26 March 2024

Published in Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2305.07229

zbMATH Keywords

concurrent data structureswait-free queues

Mathematics Subject Classification ID

Distributed algorithms (68W15) Distributed systems (68M14)

Abstract: We present a novel linearizable wait-free queue implementation using single-word CAS instructions. Previous lock-free queue implementations from CAS all have amortized step complexity of $Omega(p)$ per operation in worst-case executions, where $p$ is the number of processes that access the queue. Our new wait-free queue takes $O(logp)$ steps per enqueue and $O(lo{g}^{2}p+logq)$ steps per dequeue, where $q$ is the size of the queue. A bounded-space version of the implementation has $O(logplog(p+q))$ amortized step complexity per operation.

Cites work

• scientific article; zbMATH DE number 3936534 (Why is no real title available?)
• A Single-Enqueuer Wait-Free Queue Implementation
• A time complexity lower bound for randomized implementations of some shared objects
• An almost optimal algorithm for unbounded searching
• An optimistic approach to lock-free FIFO queues
• Efficient fetch-and-increment
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Highly-efficient wait-free synchronization
• Lower bounds on the amortized time complexity of shared objects
• Making data structures persistent
• Non-blocking doubly-linked lists with good amortized complexity
• Nonblocking algorithms and preemption-safe locking on multiprogrammed shared memory multiprocessors
• The amortized analysis of a non-blocking chromatic tree
• The amortized complexity of non-blocking binary search trees
• The future(s) of shared data structures

Cited in

(2)

• A wait-free queue with polylogarithmic step complexity
• Lower bounds on the amortized time complexity of shared objects

This page was built for publication: A Wait-free Queue with Polylogarithmic Step Complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6202234)