Measurement and algorithm for conditional local diagnosis of regular networks under the MM* model

Fault diagnosis plays an important role in maintaining the reliability of interconnection networks. Let v be a given node in an interconnection network G. v is conditionally locally t-diagnosable in G if the fault or fault-free status of node v can be identified correctly when the number of faults presented does not exceed t and every node has at least one healthy neighboring node. The conditional local diagnosis can be regarded as a local strategy toward the conditional diagnosis of networks, which puts more emphasis on identifying the status of a particular processor. In this paper, we first show a sufficient condition for a regular network to be conditionally locally t-diagnosable at a given node under the MM* model. As its applications, we derive the conditional diagnosability of hierarchical star network HSn etc. We also design an algorithm under the MM* model to identify the fault or fault-free status of a given processor in a regular network. According to our result, an α-regular network with a balanced three-tiered tree T(v;α,α−1,β) rooted at v is conditionally locally (2α+β−3)-diagnosable at node v and the time complexity of our algorithm to diagnose v is o(α2β2). As an application, we show our algorithm can identify the status of each node of star graph Sn if the fault node number does not exceed 3n−9. Compared with existing algorithms, our algorithm allows more faults to arise in a network.