Date Added: May 2013
A prominent remedy to multicore scalability issues in concurrent data structure implementations is to relax the sequential specification of the data structure. The authors present Distributed Queues (DQ), a new family of relaxed concurrent queue implementations. DQs implement relaxed queues with linearizable emptiness check and either configurable or bounded out-of-order behavior or pool behavior. Their experiments show that DQs outperform and outscale in micro- and macro-benchmarks all strict and relaxed queue as well as pool implementations that they considered.