Towards practical deteministic write-all algorithms
Bogdan S. Chlebus, Stefan Dobrev, Dariusz Rafal Kowalski, Grzegorz Greg Malewicz, Alex Allister Shvartsman, Imrich Vrt’o · 2001
The problem of performing t tasks on n asynchronous or undependable processors is a basic problem in parallel and distributed computing. We consider an abstraction of this problem called the Write-All problem— using n processors write 1's into all locations of an array of size t. The most efficient known deterministic asynchronous algorithms for this problem are due to Anderson and Woll. The first class of algorithms has work complexity of Ο(t . n ε), for n ≰ ty and any ε > 0, and they are the best known for the full range of processors (n = t). To schedule the work of the processors, the algorithms use sets of q permutations on [q] (q ≰ n) that have certain combinatorial properties. Instantiating such an algorithm for a specific ε either requires substantial pre-processing (exponential in 1/ε2) to find the requisite permutations, or imposes a prohibitive constant (exponential in 1/ε3) hidden by the asymptotic analysis. The second class deals with the specific case of t = nu, u ≰ 2, and these algorithms have work complexity of Ο(t log t). They also use sets of permutations with the same combinatorial properties. However instantiating these algorithms requires exponential in n preprocessing to find the permutations. To alleviate this costly instantiation Kanellakis and Shvartsman proposed a simple way of computing the permutation schedules. They conjectured that their construction has the desired properties but they provided no analysis.