Name
Title | ||
|---|---|---|
Symmetric PMC model of diagnosis, b-matchings in graphs and fault identification in t-diagnosable systems |
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1016/j.tcs.2021.08.025 | THEORETICAL COMPUTER SCIENCE |
Keywords | DocType | Volume |
Communication systems, System level diagnosis, SPMC model, Diagnosis of multiprocessor systems, Diagnosability, Fault tolerant computing | Journal | 891 |
ISSN | Citations | PageRank |
0304-3975 | 0 | 0.34 |
References | Authors | |
0 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Qiang Zhu | 1 | 287 | 13.43 |
| Krishnaiya Thulasiraman | 2 | 13 | 2.05 |
| Kshirasagar Naik | 3 | 1 | 0.70 |
| Sridhar Radhakrishnan | 4 | 341 | 43.65 |
| Min Xu | 5 | 20 | 8.77 |