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)\) per operation in worst-case executions, where \(p\) is the number of processes that access the queu...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2023-05
Main Authors: Naderibeni, Hossein, Ruppert, Eric
Format: Article
Language:English
Subjects:
Complexity
Queues
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422