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 alpha-regular network with a balanced three-tiered tree T(v; alpha, alpha - 1, beta) rooted at v is conditionally locally (2 alpha beta - 3)-diagnosable at node v and the time complexity of our algorithm to diagnose v is o(alpha(2) beta(2)). As an application, we show our algorithm can identify the status of each node of star graph S-n if the fault node number does not exceed 3n - 9. Compared with existing algorithms, our algorithm allows more faults to arise in a network. (C) 2021 Elsevier B.V. All rights reserved.

Automated summary

Fault diagnosis is crucial for maintaining the reliability of interconnection networks. This paper focuses on conditional local diagnosis of given nodes in interconnection networks, proposing an algorithm to identify the fault or fault-free status of nodes and demonstrating the conditional diagnosability of certain network structures. The algorithm presented allows for more faults to be detected compared to existing algorithms.