A Fast Pessimistic Diagnosis Algorithm for Hypercube-Like Networks under the Comparison Model

Journal article (2016)

Authors

Liang-Cheng Ye Guangxi University
Jia-Rong Liang Guangxi University
H.X. Lin Mathematical Physics - EEMCS
Research Group
Mathematical Physics (EEMCS) (TU Delft)
System-level diagnosis Pessimistic diagnosis Hypercube-like networks The comparison model
More Info
expand_more

Published Date

2016

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Delft Institute of Applied Mathematics

Research Group

Mathematical Physics

Abstract

Diagnosis by comparison is a realistic approach to detect faults of multiprocessor systems. This paper considers a pessimistic diagnostic strategy for hypercube-like multiprocessor systems under the comparison model. The pessimistic strategy is a diagnostic process whereby all faulty nodes can be correctly identified and at most one fault-free node may be misjudged as a faulty node. We propose a pessimistic diagnosis algorithm based on the largest component in the faulty system. For a system with N=2n nodes and n≥5 , when the number of faulty nodes is bounded by 2n−2 , the algorithm can correctly identify all nodes except at most one node left undiagnosed. The time complexity of the algorithm is O(Nlog2N) .