A Wait-free Queue with Polylogarithmic Step Complexity

05/12/2023
by   Hossein Naderibeni, et al.
0

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

Please sign up or login with your details

Forgot password? Click here to reset