Concurrent operations on priority queues

Reviewer: Frank Lawrence Friedman

Jones discusses the use of skew heaps for the concurrent manipulation of shared queues. He produces a concurrent version of the top-down algorithm for a skew heap from the Sleator-Tarjan recursive version, using previously published transformations. He also discusses the correctness and serializability of the algorithm and shows how new operations on the queue are possible after O(1) time. Jones discusses applications to problems in graph theory and simulation. He presents a brief discussion of other possible algorithms for use in an MIMD environment with fine-grained concurrency control and gives reasons for the rejection of these algorithms. He makes the transformations from the recursive skew-heap algorithm to the concurrent version by noting that (1) the recursive call is the last operation in the recursive procedure (this allows a mechanical transformation to an iterative version) and (2) the iterative version never holds references to more than three items of the tree at any time. The author gives a Concurrent Pascal-S version of the algorithm and presents the results of testing this algorithm using repeated hold operations. The results of these tests suggest that significant speedup is possible for large queues and simple applications, but only in cases where the priority queue operations are more expensive than the operations in the main process.