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

详细信息    查看全文

• 作者：Qiang Zhu ; Guodong Guo ; Wenliang Tang…
• 关键词：Interconnection networks ; Diagnosis algorithm ; PMC model
• 刊名：Journal of Combinatorial Optimization
• 出版年：2016
• 出版时间：October 2016
• 年：2016
• 卷：32
• 期：3
• 页码：960-969
• 全文大小：421 KB
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Convex and Discrete Geometry
  Mathematical Modeling and IndustrialMathematics
  Theory of Computation
  Optimization
  Operation Research and Decision Theory
  
• 出版者：Springer Netherlands
• ISSN：1573-2886
• 卷排序：32

文摘

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.