On diagnosability of large multiprocessor networks

We consider problems of fault diagnosis in multiprocessor systems. Preparata, Metze and Chien [F.P. Preparata, G. Metze, R.T. Chien, On the connection assignment problem of diagnosable systems, IEEE Trans. Comput. EC 16 (12) (1967) 848–854] 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 faulty processors based on the test results. A system is said to be tt-diagnosable if faulty units can be identified, provided the number of faulty units present does not exceed tt. We explore here diagnosis problems for nn-cube systems and give bounds for diagnosability of the nn-cube. We also describe a simple diagnosis algorithm AA which is linear in time and which can be used for sequential diagnosis as well as for incomplete diagnosis in one step. In particular, the algorithm applied to arbitrary topology based interconnection systems GG with NN processors improves previously known ones. It has sequential diagnosability tA(G)≥⌈2N12⌉−3, which is optimal in the worst case.