Paper Info
Title
The Baskets Queue
Abstract
FIFO Queues have over the years been the subject of significant research. Such queues are used as buffers both in a variety of applications, and in recent years as a key tool in buffering data in high speed communication networks. Overall, the most popular dynamic-memory lock-free FIFO queue algorithm in the literature remains the MS-queue algorithm of Michael and Scott. Unfortunately, this algorithm, as well as many others, offers no more parallelism than that provided by allowing concurrent accesses to the head and tail. In this paper we present the Baskets Queue - a new, highly concurrent lock-free linearizable dynamic memory FIFO queue. The Baskets Queue introduces a new form of parallelism among enqueue operations that creates baskets of mixed-order items instead of the standard totally ordered list. The operations in different baskets can be executed in parallel. Surprisingly however, the end result is a linearizable FIFO queue, and in fact, we show that a basket queue based on the MS-queue outperforms the original MS-queue algorithm in various benchmarks.
Year
DOI
Venue
2007
10.1007/978-3-540-77096-1_29
International Conference On Principles Of DIstributed Systems
Keywords
Field
DocType
baskets queue,cas,original ms-queue algorithm,lock-free,concurrent access,fifo queue,basket queue,compare and swap,linearizable fifo queue,lock-free linearizable dynamic memory,synchronization.,ms-queue algorithm,non-blocking,new form,concurrent data structures,fifo queues,total order
Multilevel queue,Computer science,Non-blocking algorithm,Multilevel feedback queue,Queue,Parallel computing,Real-time computing,Priority queue,Queue management system,Fork–join queue,Double-ended queue,Distributed computing
Conference
Volume
ISSN
ISBN
4878
0302-9743
3-540-77095-X
Citations 
PageRank 
References 
13
0.90
11
Authors
3
Name
Order
Citations
PageRank
Moshe Hoffman1131.58
Ori Shalev248521.68
Nir Shavit33780244.84