A Highly Concurrent Priority Queue

✍ Scribed by T. Johnson

• Book ID: 102974652
• Publisher: Elsevier Science
• Year: 1994
• Tongue: English
• Weight: 657 KB
• Volume: 22
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.1994.1097

✦ Synopsis

We present a highly concurrent priority queue algorithm based on the B-link tree, which is a (\mathrm{B}^{+})-tree in which every node has a pointer to its right sibling. The algorithm is built on the concurrent B-link tree algorithms. Since the priority queue is based on highly concurrent search structure algorithms, a large number of insert operations can execute concurrently with little or no interference. We first present an algorithm that executes deletemin operations serially. We extend the serialized-deletemin algorithm to allow both parallel and concurrent deletemin operations. We discuss a decisive operation serializable algorithm that permits concurrent deletemin operations, and an algorithm in which (p) processors cooperate to perform (p) deletemin operations in (O(\log) p) time. 01994 Academic Press, Inc.