Prof. Daniel Hendler

We present asymmetric flat-combining, an extension of flat-combining in which the behavior of producers and consumers differs, and use it to implement a linearizable FIFO queue. Unlike a flat-combining queue where all queue operations are blocking, in our algorithm enqueue operations are wait-free. Moreover, non-combiner threads performing dequeue operations are able to share the computational load instead of just waiting. Our experimental evaluation shows that the new queue algorithm outperforms the flat combining queue and other state of the art queue implementations for most producer-consumer workloads while allowing producer threads to operate in a wait-free manner.