A Wait-free Queue with Polylogarithmic Step Complexity

DOI10.1145/3583668.3594565arXiv2305.07229OpenAlexW4380873901MaRDI QIDQ6202234FDOQ6202234

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)

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.

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)

Cites Work

• Title not available (Why is that?)
• Making data structures persistent
• An almost optimal algorithm for unbounded searching
• A time complexity lower bound for randomized implementations of some shared objects
• Highly-efficient wait-free synchronization
• Nonblocking algorithms and preemption-safe locking on multiprogrammed shared memory multiprocessors
• The future(s) of shared data structures
• An optimistic approach to lock-free FIFO queues
• A Single-Enqueuer Wait-Free Queue Implementation
• The amortized analysis of a non-blocking chromatic tree
• The amortized complexity of non-blocking binary search trees
• Title not available (Why is that?)
• Title not available (Why is that?)
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Efficient Fetch-and-Increment

Cited In (2)

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

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)