MultiQueues: Simple Relaxed Concurrent Priority Queues

Authors :: Roman Dementiev
Peter Sanders
Hamza Rihani
Source :: SPAA
Publication Year :: 2015
Publisher :: ACM, 2015.
Abstract: 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.

Subjects :: Priority inheritance
Semantics (computer science)
Simple (abstract algebra)
Computer science
Concurrent data structure
Computer Science::Programming Languages
Sequential data
Parallel computing
Priority queue
Priority ceiling protocol

Database :: OpenAIRE
Journal :: Proceedings of the 27th ACM symposium on Parallelism in Algorithms and Architectures
Accession number :: edsair.doi...........e4edaa4e5224b089f9575765c8224f14

Tools