Performing Independent Tasks on Processors Prone to Failures
Bogdan S. Chlebus, Uniwersytet Warszawski, Warsaw, Poland

We will survey the work done on the problem of performing a number of
tasks in a distributed system consisting of fault-prone processors. 
The tasks are assumed to be independent (can be performed in any order),
similar (each takes one step to be completed), and idempotent (can be
performed many times and concurrently). The processors communicate by
exchanging messages, some of the processors may fail. This problem is
usually called DoAll. The efficiency of solutions is measured by work and
communication complexity. Work means either the number of times all the
tasks are performed, including multiplicities but not idling, or the
available processor steps, which include busy waiting. Communication
complexity is measured as the number of point-to-point messages.