ON DIAGNOSABILITY OF LARGE FAULT SETS IN REGULAR TOPOLOGY-BASED COMPUTER-SYSTEMS

The classical t-diagnosability approach has its limitation when dealin g with large fault sets in large multiprocessor systems. This is due t o limited diagnosability of large multiprocessor systems connected usi ng regular interconnection structures. We propose an alternative appro ach to system diagnosis by allowing a few upper bounded number of unit s to be diagnosed incorrectly. This measure is called t/k-diagnosabili ty. Using this new measure, it is possible to increase the degree of d iagnosability of large system considerably. The t/k-diagnosis guarante es that all the faulty units (processors) in a system are detected (pr ovided the number of faulty units does not exceed t) while at most k u nits are incorrectly diagnosed. We provide necessary and sufficient co nditions for t/k-diagnosability and discuss their implication. To demo nstrate the power of this approach, we analyze the diagnosability of l arge systems connected as hypercube, star-graph, and meshes. It is sho wn that a substantial increase in the degree of diagnosability of thes e structures is achieved, compared with the degree of diagnosability a chieved using the classic t-diagnosability approach, at the cost of a comparably small number of incorrectly diagnosed units.