### Space-Optimal Wait-Free Queues

Ted Herman and Valeriu Damian-Iordache
### Abstract

The paper presents
a wait-free construction for a bounded-length queue.
The total space requirement is *Dk+O(kn)*
where *D* is a bound on the queue length, *k* is the size
of a queue item, and *n* is the number of processes
that concurrently execute operations on the queue. Thus in
the case *D>n*, the construction is optimal with
respect to space. The construction uses only atomic
read/write and compare-and-swap
operations on single memory words.