Randomized priority queues for fast parallel access

Applications like parallel search or discrete event simulation often
assign priority or importance to pieces of work. An effective way
to exploit this for parallelization is to use a priority queue data
structure for scheduling the work; but a bottleneck free
implementation of parallel priority queue access by many processors
is required to make this approach scalable. We present simple and
portable randomized algorithms for parallel priority queues on
distributed memory machines with fully distributed storage.
Accessing O(n) out of m elements on an n-processor network
with diameter d requires amortized time O(d + log m/n)
with high probability for many network types. On logarithmic
diameter networks, the algorithms are as fast as the best previously
known EREW-PRAM methods. Implementations demonstrate that the approach is
already useful for medium scale parallelism.