Performing Tasks on Synchronous Restartable Message-passing Processors

We consider the problem of performing t tasks in a distributed system of p faultprone processors. This problem, called do-all herein, was introduced by Dwork, Halpern and Waarts. Our work deals with a synchronous message-passing distributed system with processor stop-failures and restarts. We present two new algorithms based on a new aggressive coordination paradigm by which multiple coordinators may be active as the result of failures. The first algorithm is tolerant of f ! p stop-failures and it does not allow restarts. It has available processor steps (work) complexity S = O((t + p log p= log log p) log f) and message complexity M = O(t + p log p= log log p + fp). Unlike prior solutions, our algorithm uses redundant broadcasts when encountering failures and, for p = t and large f , it achieves better work complexity. This algorithm is used as the basis for another algorithm which tolerates stop-failures and restarts. This new algorithm is the first solution for the do-all problem t..