Optimal Fast List-Ranking and Prefix Algorithms
February 05, 1995
In this seminar paper (1995), written during my graduate studies in computer science, I explore the foundational prefix-sum problem (prefix sums) in a parallel setting.
This post is a summary and a didactic reworking of the following two papers:
- Richard Cole, Uzi Vishkin. Deterministic Coin Tossing with Applications to Optimal Parallel List Ranking. Information and Control, 1986, No. 70, p. 32-53 x
- Richard Cole, Uzi Vishkin. Faster Optimal Parallel Prefix Sums and List Ranking. Information and Control, 1989, No. 81, p. 334-352
Chapter 1 introduces the notation and terminology used, as well as the list-ranking and prefix-sum problems. It also outlines the standard baseline algorithms for both. Chapter 2 discusses an optimal algorithm for the prefix-sum problem and uses so-called deterministic coin tossing to break symmetry in otherwise indistinguishable situations. Chapter 3 explains deterministic coin tossing via the $r$-ruling set problem. Chapter 4 then applies the techniques from the previous chapters to derive an optimal algorithm for the list-ranking problem.