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.
I’ve written an article for JavaSpektrum 2/2025 about Structured Concurrency in Java 24. The article covers JEP 499, Java’s fourth preview of Structured Concurrency, which aims to make concurrent programming...
Concurrent and asynchronous applications can be written in Kotlin with coroutines in a precise and structured way. Unfortunately, concurrency often increases the complexity and it is difficult to create bug-free...
