A Wait-free Queue with Polylogarithmic Step Complexity

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(\log p)$ steps per enqueue and $O({\log }^{2}p+\log q)$ steps per dequeue, where $q$ is the size of the queue. A bounded-space version of the implementation has $O(\log p\log (p+q))$ amortized step complexity per operation.

18 pages, 6 figures, to be published in Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing