TY - GEN
T1 - Efficient parallel algorithms can be made robust
AU - Kanellakis, Paris C.
AU - Shvartsman, Alex A.
PY - 1989
Y1 - 1989
N2 - The efficient parallel algorithms proposed for many fundamental problems, such as list ranking, computing preorder numberings and other functions on trees, or integer sorting, are very sensitive to processor failures. The requirement of efficiency (commonly formalized using Parallel-time x Processors 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 of robustness, 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 with at least one surviving processor, our method increases the original algorithm cost by at most a multiplicative factor polylogarithmic in the input size.
AB - The efficient parallel algorithms proposed for many fundamental problems, such as list ranking, computing preorder numberings and other functions on trees, or integer sorting, are very sensitive to processor failures. The requirement of efficiency (commonly formalized using Parallel-time x Processors 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 of robustness, 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 with at least one surviving processor, our method increases the original algorithm cost by at most a multiplicative factor polylogarithmic in the input size.
UR - http://www.scopus.com/inward/record.url?scp=0024942821&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0024942821&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:0024942821
SN - 0897913264
T3 - Proceedings of the Annual ACM Symposium on Principles of Distributed Computing
SP - 211
EP - 221
BT - Proc Eighth ACM Symp Princ Distrib Comput
PB - Publ by ACM
T2 - Proceedings of the Eighth Annual ACM Symposium on Principles of Distributed Computing
Y2 - 14 August 1989 through 16 August 1989
ER -