A Single-Enqueuer Wait-Free Queue Implementation



We study wait-free linearizable Queue implementations in asynchronous shared-memory systems from other consensus number 2 objects, such as Fetch&Add and Swap. The best previously known implementation allows at most two processes to perform dequeue operations. We provide a new implementation, when only one process performs enqueue operations and any number of processes perfrom dequeue operations. A nice feature of this implementation is the fact that both enqueue and dequeue operations take constant time.