Time-optimal message-efficient work performance in the presence of faults

Performing work in parallel by a multitude of processes in a distributed environment is currently a fast growing area of computer applications (due to its cost effectiveness). Adaptation of such applications to changes in system's parallelism (i.e., the availability of processes) is essential for improved performance and reliability. In this work we consider one aspect of coping with dynamic processes failures in such a setting, namely the following scenario formulated by Dwork, Halpern and Waarts [DHW92]: a system of n synchronous processes that communicate only by sending messages to one another. These processes must perform m independent units of work. Processes may fail by crashing and wait-freeness is required, i.e. that whenever at least one process survives, all m units of work will be performed. We consider the notion of fast algorithms in this setting, yet we are not willing to trade improved time for a high cost in communication. Thus, we require message efficiency as well. We therefore put forth the notion of lexicographic efficiency, that is we consider the following two complexity measures in order: The parallel processor step (or S for short) as introduced by Kanellakis and Shvartsman [KS89] in the context of robust PRAM and the number of messages sent (denoted M).