Diagnosability analysis in graph-theoretic modelof computer systems

Abstract

Fault diagnosis at the system level is an important aspect in fault-tolerant computing systems consisting of a large number of interconnected processors. In this thesis, we are concerned with fault diagnosis of a system in which each unit is capable of testing other units. As an approach to fault diagnosis in a system, we introduce a problem of determining in a system with $n$ units whether at least one out of given $m(\le{n})$ units can be identified as faulty or fault-free provided the number of faulty units present does not exceed t. We characterize such an identifiable set of m units for $m \le 2$. For the simple characterization of an identifiable set, we propose a new matching, called S-matching, in a digraph as an extension of a matching and develop an algorithm for finding a maximum S-matching in a digraph. This algorithm can be applied to finding a maximum matching in a bipartite graph. The proposed S-matching techniques greatly simplify the characterization of an identifiable set U with $\mid{U} \mid \le 2$. Using the identifiable set U with $\mid{U} \mid \le 2$, we investigate measures of diagnosability such as one-step t-diagnosability, sequential t-diagnosability, t/t-diagnosability and intermittent t-diagnosability. We present simplified characterizations of one-step t-diagnosable systems and t/t-diagnosable systems, and algorithms for determining these diagnosabilities for a given system. For the sequentially t-diagnosable systems which have not been fully characterized, we extend the sufficient conditions by constructing these systems. We also give an alternative characterization of intermittently t-diagnosable systems.