Title: Coarse Grained Parallel Selection,
Abstract: We analyze the running time of the Saukas-Song algorithm for selection on a
coarse grained multicomputer without expressing the running time in terms of
communication rounds. This shows that while in the best case the Saukas-Song
algorithm runs in asymptotically optimal time, in general it does not. We
propose other algorithms for coarse grained selection that have optimal
expected running time.