Randomization Helps to Perform Tasks on Processors Prone to Failures

摘要

The problem of performing t tasks in a distributed system of p processors is studied. The tasks are assumed to be independent, similar (each takes one step to be completed), and idempotent (can beperformed many times and concurrently). The processors communicate by passing messages and each of them may fail. This problem is usually called DO-ALL, it was introduced by Dwork, Halpern and Waarts.