A Wait-free Queue with Polylogarithmic Step Complexity
share
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 Ω(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.
READ FULL TEXT