Graph models and system diagnosis.

Abstract

The connectivity of a system is an important measure of fault tolerance. Typical interconnection networks are sparse and symmetrical. The classical diagnosis theories, such as t-diagnosability, are not appropriate for these systems because the number of faulty elements is limited by the minimum node degree, which is very small for sparse systems. Another disadvantage of the classical approach is the need for a supervisory processor. This processor is a bottleneck in the system, unnecessarily burdening the communication paths. The supervisor processor is also a single-point failure in the system. The theory of local diagnosis overcomes these limitations.

We show a solution to the characterization, diagnosability, and diagnosis problems with the t-in-L$\sb2$ diagnosability theory. In this theory, if there are at most t faulty PEs in the local neighborhood set of x, and at most t(m) faulty PEs in the extended-local neighborhood set of x, then we can uniquely diagnose any graph. The extended-local fault constraint, t(m), is a function of the local fault constraint, t, and the degree of node x.

In this research, we investigate the local diagnosability of multiprocessor systems for permanently faulty processing elements (PEs). There are three system-level diagnosis problems: the characterization problem is to determine the necessary and sufficient conditions for the diagnosability of a system; the diagnosability problem is to determine the maximum value of certain parameters for which the system is diagnosable; and the diagnosis problem is to find an algorithm that identifies all faulty PEs based on a given syndrome. It is assumed that each set of faulty PEs is from some allowable fault set, which is a restricted set of faults.

We develop a general approach for the t-in-L$\sb2$ diagnosis of an arbitrary graph. We apply the approach to the special cases of mesh and hypercube graphs. We also show the applicability of our theory to the diagnosis of the GNSS system.