首页|Measurement and algorithm for conditional local diagnosis of regular networks under the MM* model
Measurement and algorithm for conditional local diagnosis of regular networks under the MM* model
扫码查看
点击上方二维码区域，可以放大扫码查看
原文链接
NSTL
Elsevier
? 2021 Elsevier B.V.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.
NSTL
Elsevier
