Towards practical deteministic write-all algorithms

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/ε²) to find the requisite permutations, or imposes a prohibitive constant (exponential in 1/ε³) hidden by the asymptotic analysis. The second class deals with the specific case of t = n^u, 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.

In this paper we show, for the first time, an analysis of the properties of the set of permutations proposed by Kanellakis and Shvartsman. Our result is hybrid as it includes analytical and empirical parts. The analytical result covers a subset of the possible adversarial patterns of asynchrony. The empirical results provide strong evidence that our analysis covers the worst case scenario, and we formally state it as a conjecture. We use these results to analyze an algorithm for t = n^u (u ⪈ 2), tasks, that takes advantage of processor slackness and that has work Ο(t log² t), conditioned on our conjecture. This algorithm requires only Ο(n log n) time to instantiate it. Next we study the case for the full range of processors n ≰ t. We define a family of deterministic asynchronous Write-All algorithms with work Ο(t . n ^ε) contingent upon our conjecture. We show that our method yields a faster construction of Ο(t . n ^ε) Write-All algorithms than the method developed by Anderson and Woll. Finally we show that our approach yields more efficient Write-all algorithms as compared to the algorithms induced by the constructions of Naor and Roth for the same asymptotic work complexity.