MultiQueues: Simple Relaxed Concurrent Priority Queues
Hamza Rihani, Peter W. Sanders, Roman Dementiev · 2015
We present a simple, concurrent data structure that approximates the behavior of a priority queue and that gives very good performance guarantees. We also discuss models for the semantics of relaxed priority queues and introduce a technique for "waitfree locking" that allows to convert sequential data structures to relaxed concurrent data structures.