We present a randomized parallel list ranking algorithm for distributed memory multiprocessors. A simple version requires, with high probability, (Formula presented) communication rounds (h-relations with (Formula presented) local computation. An improved version requires, with high probability, only (Formula presented) communication rounds where (Formula presented). Note that k < ln*(n) is an extremely small number. For n ≤ 1010100 and p ≥ 4, the value of k is at most 2. For a given number of processors, p, the number of communication rounds required is, for all practical purposes, independent of n. For n ≤ 1010100 and 4 ≤ p ≤ 2048, the number of communication rounds in our algorithm is bounded, with high probability, by 118. We conjecture that the actual number of communications rounds will not exceed 50.

Additional Metadata
Citation
Dehne, F, & Song, S.W. (Siang W.). (1996). Randomized parallel list ranking for distributed memory multiprocesors.