The Do-All Problem with Byzantine Processor Failures

摘要

Do-All is the abstract problem of using n processors to cooperatively perform m independent tasks in the presence of failures. This problem can be used as the cornerstone in identifying aspects of the trade-off between efficiency and fault-tolerance in cooperative computing and in developing efficient and fault-tolerant algorithms for distributed cooperative applications. Many algorithms have been developed for Do-All in various models of computation, including message-passing, partitionable networks, and shared-memory models and under various failure models. However, to the best of our knowledge, Do-All has not been studied under Byzantine processor failures, where a faulty processor may exhibit completely unconstrained behavior. Byzantine failures model any arbitrary type of processor malfunction, including for example, failures of individual components within the processors. In this work we study the Do-All problem for synchronous message-passing processors prone to Byzantine failures. In particular, we present upper and lower bound results on the efficiency of Do-All for several cases: we consider the case where the maximum number of faulty processors f is known a priori, the case where f is not known, the case where a task that has been executed can be verified (without re-executing it) and the case where task executions cannot be verified. We evaluate our algorithms in terms of their work and message complexities. The work complexity accounts all computational steps taken by the processors and the message complexity accounts all messages sent by the processors during the computation. The work and messages of a faulty processor are counted only until the processor fails to follow the algorithm being executed.