A wait-free queue with polylogarithmic step complexity

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)\) $\mathrm{\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)\) $O(logp)$ steps per enqueue and \(O(\log ^2 p +\log q)\) $O({log}^{2}p+logq)$ 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))\) $O(logplog(p+q))$ amortized step complexity per operation.