ISSN:
1432-0452
Keywords:
Parallel computation
;
Fault tolerance
;
Computation complexity
;
Lower bounds
;
Robust algorithms
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Summary The efficient parallel algorithms proposed for many fundamental problems, such as list ranking, integer sorting and computing preorder numberings on trees, are very sensitive to processor failures. The requirement of efficiency (commonly formalized usingParallel-timexProcessors as a cost measure) has led to the design of highly tuned PRAM algorithms which, given the additional constraint of simple processor failures, unfortunately become inefficient or even incorrect. We propose a new notion ofrobustness, that combines efficiency with fault tolerance. For the common case of fail-stop errors, we develop a general and easy to implement technique to make robust many efficient parallel algorithms, e.g., algorithms for all the problems listed above. More specifically,for any dynamic pattern of fail-stop errors on a CRCW PRAMwith at least one surviving processor, our method increases the original algorithm cost by at most a log2 multiplicative factor. Our technique is based on a robust solution of the problem ofWrite-All, i.e., usingP processors, write 1's in all locations of anN-sized array. In addition we show that at least a log/log log multiplicative overhead will be incurred for certain patterns of failures by any algorithm that implements robust solutions toWrite-All withP=N. However, by exploiting parallel slackness, we obtain an optimal cost algorithm when $$P \leqslant \frac{N}{{\log ^2 N - \log N\log \log N}}.$$
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02277667
Permalink