RANDOMIZED PRIORITY-QUEUES FOR FAST PARALLEL ACCESS

We present simple randomized algorithms for parallel priority queues o n distributed memory machines, Inserting O(n) elements or deleting the O(n) out of m smallest elements using n processors requires O(T-coll + log(m/n)) amortized time with high probability where T-coll bounds t he time for performing prefix sums and randomized touting. The memory requirement is bounded by (m/n)(1 + o(1)) + O(log n) whp. These bounds are an improvement over the best previously known algorithms for many interconnection, networks and even matches the speed of the best know n PRAM algorithms. Generalizations for accessing the k >> n smallest e lements are even more efficient. A portable implementation using MPI d emonstrates that our approach is already useful for medium scale paral lelism. Two parallel selection algorithms for randomly placed data are a spin-off. One runs in time O(T-coll) with high probability, beating a lower bound for the worst case. The other requires only a single re duction operation. (C) 1998 Academic Press.