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.