Distributed computing column
Cynthia Dwork · ACM SIGACT News · 1996
In PODC'96 Jim Aspnes and William Hurwood [3] presented a beautiful paper on the cooperative collect problem.In many shared-memory applications processes repeatedly require up-to-date, or fresh, information about all values stored in a particular set of registers.In the simplest version of this problem all values are present at the start and each process gathers the values only once, so freshness is not an issue.In the full (repeated) version the values may change at any time.If each process reads every register itself, then even in the simple version of the problem not only is the total number of reads high (Q(n2)), but the communication costs increase dramatically with the degree of concurrency, due to bus congestion and contention.Nonetheless, the trivial solution has been used throughout the literature on wait-free shared-memory applications, including nearly all algorithms for consensus, snapshots, coin flipping, bounded round numbers, timestamps, and multi-writer registers.Saks, Shavit, and Woll [12] abstracted the problem and developed an elegant randomized solution, which they analyzed in