On diagnosability of large fault sets in regular topology-based computer systems

The classical t-diagnosability approach has its limitation when dealing with large fault sets in large multiprocessor systems. This is due to limited diagnosability of large multiprocessor systems connected using regular interconnection structures. We propose an alternative approach to system diagnosis by allowing a few upper bounded number of units to be diagnosed incorrectly. This measure is called t/k-diagnosability. Using this new measure, it is possible to increase the degree of diagnosability of large system considerably. The t/k-diagnosis guarantees that all the faulty units (processors) in a system are detected (provided the number of faulty units does not exceed t) while at most k units are incorrectly diagnosed. We provide necessary and sufficient conditions for t/k-diagnosability and discuss their implication. To demonstrate the power of this approach, we analyze the diagnosability of large systems connected as hypercube, star-graph, and meshes. It is shown that a substantial increase in the degree of diagnosability of these structures is achieved, compared with the degree of diagnosability achieved using the classic t-diagnosability approach, at the cost of a comparably small number of incorrectly diagnosed units.