In: Mavronicolas, M.; Tsigas, Ph.: Lecture Notes in Computer Science, Vol. 1320: Distributed Algorithms, Proc. of 11th International Workshop, WDAG'97, Saarbrücken, Germany, pages 96-110. Springer, September 1997.
Abstract: This work presents new algorithms for the ``Do-All'' problem that consists of performing t tasks reliably in a message-passing synchronous system of p fault-prone processors. The algorithms are based on an aggressive coordination paradigm in which multiple coordinators may be active as the result of failures. The first algorithm is tolerant of Y<p stop-failures and it does not allow restarts. It has the available processor steps complexity S = O((t+p log p/log log p) log Y) and the message complexity M = O((t+p log p/log log p+Y p). Unlike prior solutions, our algorithm uses redundant broadcasts when encountering failures and, for large Y, it has better complexity. This algorithm is used as the basis for another algorithm which tolerates any patters of stop-failures and restarts. This new algorithm is the first solution for the Do-All problem that efficiently deals with processor restarts. Its available processor steps complexity is S = O((t+p log p+Y) minlog p, log Y), and its message complexity is M = O(t+p log p+Y p), where Y is the number of failures.