QUANTIFYING FAULT RECOVERY IN MULTIPROCESSOR SYSTEMS

We formalize and quantify various aspects of reliable computing with e mphasis on efficient fault recovery. The mathematical model which prov es to be most appropriate is provided by the theory of graphs. We have developed new measures for fault recovery and observe that the value of elements of the fault recovery vector depend not only on the comput ation graph H and the architecture graph G, but also on the specific l ocation of a fault. In our examples, we choose a hypercube as a repres entative of parallel computer architecture, and a pipeline as a typica l configuration for program execution. We define dependability qualiti es of such a system with or without a fault. These qualities are deter mined by the resiliency triple defined by three parameters: multiplici ty, robustness, and configurability. We also introduce parameters for measuring the recovery effectiveness in terms of distance, time, and t he number of new, used, and moved nodes and edges.