ON PROBABILISTIC DIAGNOSIS OF MULTIPROCESSOR SYSTEMS USING MULTIPLE SYNDROMES

Abstract

This paper addresses the distributed self-diagnosis of a multiprocessor/multicomputer system based on fault syndromes formed by comparison testing. We show that by using multiple fault syndromes, it is possible to achieve significantly better diagnosis than by using a single fault syndrome, even when the amount of time devoted to testing is the same. We derive a multiple syndrome diagnosis algorithm that in terms of the level of diagnostic accuracy achieved, is globally suboptimal, but optimal among all diagnosis algorithms of a certain type to be defined. Our diagnosis algorithm produces good results, even with sparse interconnection networks and interprocessor tests with low fault coverage. It is also proven that our diagnosis algorithm produces 100% correct diagnosis as N, the number of nodes in the system, approaches infinity, provided that the interconnection network has connectivity greater than or equal to 2 and that the number of syndromes produced grows faster than log N. Our solution and another multiple syndrome diagnosis solution by Fussell and Rangarajan are comparatively evaluated, both analytically and with simulations.