A Wait-free Queue with Polylogarithmic Step Complexity

DOI10.1145/3583668.3594565arXiv2305.07229OpenAlexW4380873901MaRDI QIDQ6202234

Eric Ruppert, Unnamed Author

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 systems (68M14) Distributed algorithms (68W15)

Cites Work

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

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