A diagnosis algorithm by using graph-coloring under the PMC model

Qiang Zhu, Guodong Guo, Wenliang Tang and Cun-Quan Zhang ()
Additional contact information
Qiang Zhu: Xidian University
Guodong Guo: West Virginia University
Wenliang Tang: West Virginia University
Cun-Quan Zhang: West Virginia University

Journal of Combinatorial Optimization, 2016, vol. 32, issue 3, No 21, 960-969

Abstract: Abstract Fault diagnosis is important to the design and maintenance of large multiprocessor systems. PMC model is the most well known and widely studied model in the system level diagnosis of multiprocessor systems. Under the PMC model, a diagnosis algorithm based on some graph-coloring techniques has been proposed in this paper. Given a syndrome $$\sigma $$ σ , the first part of the algorithm can locate all the definitely faulty vertices. Then in the second part of the algorithm a diagnosis graph corresponding to the syndrome can be constructed and the suspicious faulty sets can be determined by finding the maximal independent sets of the diagnosis graph. A weight is assigned to each suspicious faulty vertex set which can measure its occurring probability. The algorithm is shown to be correct, not based on any conjecture and can be applied to the fault identification for any multiprocessor system.

Keywords: Interconnection networks; Diagnosis algorithm; PMC model (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-015-9923-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:32:y:2016:i:3:d:10.1007_s10878-015-9923-5

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-015-9923-5

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().