期刊
THEORETICAL COMPUTER SCIENCE
卷 891, 期 -, 页码 35-49出版社
ELSEVIER
DOI: 10.1016/j.tcs.2021.08.025
关键词
Communication systems; System level diagnosis; SPMC model; Diagnosis of multiprocessor systems; Diagnosability; Fault tolerant computing
资金
- National Natural Science Foundation of China [61672025]
This paper introduces a new testing model called the symmetric PMC (SPMC) model, and proves that the diagnosability of an n-dimensional hypercube under the SPMC model is almost twice its diagnosability under the PMC model. Additionally, it shows that the fault diagnosis problem for a t-diagnosable system under the SPMC model reduces to determining a maximum weighted b-matching in its diagnosis graph.
A major breakthrough in the diagnosis of t-diagnosable systems occurred when Dahbura and Mason developed a diagnosis algorithm under the PMC model using the matching theory in bipartite graphs. In this paper we introduce a new testing model called the symmetric PMC(SPMC) model. Our main contributions are as follows: We prove that the diagnosability of an n-dimensional hypercube under the SPMC model is almost twice its diagnosability under the PMC model. We then show that the fault diagnosis problem for a t-diagnosable system under the SPMC model reduces to that of determining a maximum weighted b-matching in its diagnosis graph. Algorithm LABEL is then given to identify all the faulty vertices using the maximum b-matching of the diagnosis graph. Finally, using certain results from the theory of partitions of integers we establish the worst case complexity of our t-diagnosis algorithm. The complexity is much better than the worst case complexity of the Dahbura-Mason algorithm for the t-diagnosable problem under the PMC model. (C) 2021 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据