4.3 Article

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

期刊

DISCRETE APPLIED MATHEMATICS
卷 309, 期 -, 页码 46-67

出版社

ELSEVIER
DOI: 10.1016/j.dam.2021.11.006

关键词

Comparison model; Interconnection network; Local diagnosis; Conditional diagnosability; Diagnosis algorithm

资金

  1. National Natural Science Foundation of China [61402317, 61502286]
  2. Natural Science Foundation of Shanxi Province, People's Republic of China [201901D111253]
  3. Scientific and Technological Innovation Team of Shanxi Province, People's Republic of China [201805D131007]
  4. Taiyuan University of Science and Technology Doctoral Fund, People's Republic of China [20202058]

向作者/读者索取更多资源

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.
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.

作者

我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。

评论

主要评分

4.3
评分不足

次要评分

新颖性
-
重要性
-
科学严谨性
-
评价这篇论文

推荐

暂无数据
暂无数据