LR-algorithm: concurrent operations on priority queues

The heap representation of priority queues is one of the most widely used methods. However, the conventional implementation tends to be inadequate for parallel applications. The paper proposes a new method, the LA-algorithm, which allows concurrent insertions on priority queues. In contrast to the conventional heap implementation, the LR-algorithm directs any two consecutive insertion requests to two different subtrees and thus provides a possibility to perform these insertions in parallel. The LR algorithm was implemented on a Sequent Symmetry shared memory multiprocessor. The obtained performance figures indicate that the algorithm is a promising approach