Conditional-Fault Diagnosability of Multiprocessor Systems with an Efficient Local Diagnosis Algorithm under the PMC Model
Cheng‐Kuan Lin, Tzu-Liang Kung, J. Tan · IEEE Transactions on Parallel and Distributed Systems · 2011
Diagnosis is an essential subject for the reliability of multiprocessor systems. Under the PMC diagnosis model, Dahbura and Masson [12] proposed a polynomial-time algorithm with time complexity O(N^{2.5}) to identify all the faulty processors in a system with N processors. In this paper, we present a novel method to diagnose a conditionally faulty system by applying the concept behind the local diagnosis, introduced by Somani and Agarwal [30], and formalized by Hsu and Tan [18]. The goal of local diagnosis is to identify the fault status of any single processor correctly. Under the PMC diagnosis model, we give a sufficient condition to estimate the local diagnosability of a given processor. Furthermore, we propose a helpful structure, called the augmenting star, to efficiently determine the fault status of each processor. For an N-processor system in which every processor has an O(\log N) degree, the time complexity of our algorithm to diagnose any given processor is O((\log N)^2), provided that each processor can construct an augmenting star structure of full order in time O((\log N)^2) and the time for a processor to test another one is constant. Therefore, the time totals to O(N(\log N)^2) for diagnosing the whole system.