On diagnosability of large multiprocessor networks

We consider problems of fault diagnosis in multiprocessor systems. Preparata, Metze and Chien (1967) introduced a graph theoretical model for system-level diagnosis, in which processors perform tests on one another via links in the system. Fault-free processors correctly identify the status of tested processors, while the faulty processors can give arbitrary test results. The goal is to identify correctly all faulty processors based on the test results. A system is said to be t-diagnosable if all faulty units can be identified provided the number of faulty units present does not exceed t. Here we explore the diagnosis problems for n-cube systems. We give new upper and lower bounds for the diagnosability of n-cube under sequential diagnosis strategy. We also describe a sequential diagnosis algorithm, which can be applied for arbitrary topology based systems.