A work-optimal deterministic algorithm for the asynchronous certified write-all problem
Grzegorz Greg Malewicz · 2003
In their SIAM J. on Computing paper [33] from 1992, Martel et al. posed a question for developing a work-optimal deterministic asynchronous algorithm for the fundamental loadbalancing and synchronization problem called Certified Write-All. In this problem, introduced in a slightly different form by Kanellakis and Shvartsman in a PODC’89 paper [20], p processors must update n memory cells and only then signal the completion of the updates. It is known that solutions to this problem can be used to simulate synchronous parallel programs on asynchronous systems with worst-case guarantees for the overhead of a simulation. Such simulations are interesting because they may increase productivity in parallel computing since synchronous parallel programs are easier to reason about than asynchronous ones are. This paper presents the first solution to the question of Martel et al. Specifically, we show a deterministic asynchronous algorithm for the Certified Write-All problem. Our algorithm has the work complexity of O(n + p 4 log n). This work complexity is asymptotically optimal for a nontrivial number of processors p ≤ (n / log n) 1/4. In contrast, all known deterministic algorithms require superlinear in n work when p = n 1/r, for any fixed r ≥ 1.