Two-Round Diagnosability Measures for Multiprocessor Systems
In a multiprocessor system, as a key measure index for evaluating its reliability, diagnosability has attracted lots of attentions. Traditional diagnosability and conditional diagnosability have already been widely discussed. However, the existing diagnosability measures are not sufficiently compreh...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2020-01-01
|
| Series: | Complexity |
| Online Access: | http://dx.doi.org/10.1155/2020/9535818 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832566643769737216 |
|---|---|
| author | Jiarong Liang Qian Zhang Changzhen Li |
| author_facet | Jiarong Liang Qian Zhang Changzhen Li |
| author_sort | Jiarong Liang |
| collection | DOAJ |
| description | In a multiprocessor system, as a key measure index for evaluating its reliability, diagnosability has attracted lots of attentions. Traditional diagnosability and conditional diagnosability have already been widely discussed. However, the existing diagnosability measures are not sufficiently comprehensive to address a large number of faulty nodes in a system. This article introduces a novel concept of diagnosability, called two-round diagnosability, which means that all faulty nodes can be identified by at most a one-round replacement (repairing the faulty nodes). The characterization of two-round t-diagnosable systems is provided; moreover, several important properties are also presented. Based on the abovementioned theories, for the n-dimensional hypercube Qn, we show that its two-round diagnosability is n2+n/2, which is n+1/2 times its classic diagnosability. Furthermore, a fault diagnosis algorithm is proposed to identify each node in the system under the PMC model. For Qn, we prove that the proposed algorithm is the time complexity of On2n. |
| format | Article |
| id | doaj-art-d6471edf538040c7910250e5571d2a4e |
| institution | Kabale University |
| issn | 1076-2787 1099-0526 |
| language | English |
| publishDate | 2020-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Complexity |
| spelling | doaj-art-d6471edf538040c7910250e5571d2a4e2025-02-03T01:03:40ZengWileyComplexity1076-27871099-05262020-01-01202010.1155/2020/95358189535818Two-Round Diagnosability Measures for Multiprocessor SystemsJiarong Liang0Qian Zhang1Changzhen Li2School of Computer, Electronics and Information, and with Guangxi Key Laboratory of Multimedia Communications and Network Technology, Guangxi University, Nanning 530004, ChinaSchool of Computer, Electronics and Information, and with Guangxi Key Laboratory of Multimedia Communications and Network Technology, Guangxi University, Nanning 530004, ChinaSchool of Public Policy and Management, Guangxi University, Nanning 530004, ChinaIn a multiprocessor system, as a key measure index for evaluating its reliability, diagnosability has attracted lots of attentions. Traditional diagnosability and conditional diagnosability have already been widely discussed. However, the existing diagnosability measures are not sufficiently comprehensive to address a large number of faulty nodes in a system. This article introduces a novel concept of diagnosability, called two-round diagnosability, which means that all faulty nodes can be identified by at most a one-round replacement (repairing the faulty nodes). The characterization of two-round t-diagnosable systems is provided; moreover, several important properties are also presented. Based on the abovementioned theories, for the n-dimensional hypercube Qn, we show that its two-round diagnosability is n2+n/2, which is n+1/2 times its classic diagnosability. Furthermore, a fault diagnosis algorithm is proposed to identify each node in the system under the PMC model. For Qn, we prove that the proposed algorithm is the time complexity of On2n.http://dx.doi.org/10.1155/2020/9535818 |
| spellingShingle | Jiarong Liang Qian Zhang Changzhen Li Two-Round Diagnosability Measures for Multiprocessor Systems Complexity |
| title | Two-Round Diagnosability Measures for Multiprocessor Systems |
| title_full | Two-Round Diagnosability Measures for Multiprocessor Systems |
| title_fullStr | Two-Round Diagnosability Measures for Multiprocessor Systems |
| title_full_unstemmed | Two-Round Diagnosability Measures for Multiprocessor Systems |
| title_short | Two-Round Diagnosability Measures for Multiprocessor Systems |
| title_sort | two round diagnosability measures for multiprocessor systems |
| url | http://dx.doi.org/10.1155/2020/9535818 |
| work_keys_str_mv | AT jiarongliang tworounddiagnosabilitymeasuresformultiprocessorsystems AT qianzhang tworounddiagnosabilitymeasuresformultiprocessorsystems AT changzhenli tworounddiagnosabilitymeasuresformultiprocessorsystems |