A fundamental advantage of distributed systems over centralized systems is fault-tolerance: correctly functioning processors can successfully complete a computation in the face of failures by other processors. The design and efficiency of fault-tolerant applications increases with the severity of the failures that may occur. Most practical fault-tolerant systems tolerate only very simple failures (such as stopping); there has been no formal characterization of the effects of different types of faulty behavior. The proposed research is a formal study of different types of faulty behaviors, comparing them in several ways. The expected results will greatly expand the utility of existing systems, allowing them to be modified to tolerate more severe failures. This proposal outlines two primary methods by which this research is to advance. The first is the study of translations that automatically convert applications designed to run in systems with benign failures into ones that run in systems with more severe failures. The second method used here is the study of processor knowledge. Techniques from this area promise to lead to more thorough analysis of the effects of failures on the computation and communication necessary to solve certain problems in systems with failures.
