View in EDS

A local edge diagnosability measure for multiprocessor systems.

Saved in:
Bibliographic Details
Title: A local edge diagnosability measure for multiprocessor systems.
Authors: Guo, Chen1,2 (AUTHOR), Mo, Qiuli1,3 (AUTHOR), Peng, Shuo1,2 (AUTHOR), Xiao, Zhifang1,2 (AUTHOR) xiaozhifang@jgsu.edu.cn
Source: Discrete Applied Mathematics. Dec2025, Vol. 377, p260-268. 9p.
Subjects: Fault diagnosis, Multiprocessors, Diagnosis, Failure analysis, Multistage interconnection networks, Algorithms, Graph theory
Abstract: System-level fault diagnosis in multiprocessor systems, initially proposed by Preparata, Metze, and Chien, primarily focuses on studying the global diagnostic capability of the systems. However, due to the significant differences that may exist in the topology and topological characteristics, the diagnostic capabilities of individual processors or single links differ, particularly in interconnection networks with low symmetry. In this paper, we introduce the concept of local edge diagnosability as a novel metric for evaluating diagnostic capability when faults occur on specific edges. We then explore the properties of local edge diagnosticity under the HPMC (Hybrid Preparata, Metze, and Chien) model and present the necessary and sufficient conditions for determining the distinguishability of a pair of hybrid faulty sets. Additionally, we determine that the local edge diagnosability of general graphs at a particular edge is equal to the minimum degree of its two endpoints minus one under specific conditions. Finally, we propose an efficient and accurate local edge diagnosis algorithm for hypercubes, validating its correctness and time complexity. [ABSTRACT FROM AUTHOR]
Copyright of Discrete Applied Mathematics is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
Description
Abstract:System-level fault diagnosis in multiprocessor systems, initially proposed by Preparata, Metze, and Chien, primarily focuses on studying the global diagnostic capability of the systems. However, due to the significant differences that may exist in the topology and topological characteristics, the diagnostic capabilities of individual processors or single links differ, particularly in interconnection networks with low symmetry. In this paper, we introduce the concept of local edge diagnosability as a novel metric for evaluating diagnostic capability when faults occur on specific edges. We then explore the properties of local edge diagnosticity under the HPMC (Hybrid Preparata, Metze, and Chien) model and present the necessary and sufficient conditions for determining the distinguishability of a pair of hybrid faulty sets. Additionally, we determine that the local edge diagnosability of general graphs at a particular edge is equal to the minimum degree of its two endpoints minus one under specific conditions. Finally, we propose an efficient and accurate local edge diagnosis algorithm for hypercubes, validating its correctness and time complexity. [ABSTRACT FROM AUTHOR]
ISSN:0166218X
DOI:10.1016/j.dam.2025.06.036