A Local Diagnosis Algorithm for Hypercube-like Networks under the BGM Diagnosis Model

Article type: Research Article

Authors: Lin, Cheng-Kuan | Kung, Tzu-Liang | Hung, Chun-Nan | Teng, Yuan-Hsiang^{; *}

Affiliations: Department of Computer Science, National Yang Ming Chiao Tung University, Hsinchu City, Taiwan 30010, R.O.C. | Department of Computer Science and Information Engineering, Asia University, Taichung City, Taiwan 413, R.O.C. | Department of Information Management, Da-Yeh University, Changhua, Taiwan 51591, R.O.C. | Department of Computer Science and Information Engineering, Providence University, Taichung City, Taiwan 433, R.O.C. yhteng@pu.edu.tw

Correspondence: [*] Address for correspondence: Department of Computer Science and Information Engineering, Providence University, Taichung City, Taiwan 433, R.O.C.

Abstract: System diagnosis is process of identifying faulty nodes in a system. An efficient diagnosis is crucial for a multiprocessor system. The BGM diagnosis model is a modification of the PMC diagnosis model, which is a test-based diagnosis. In this paper, we present a specific structure and propose an algorithm for diagnosing a node in a system under the BGM model. We also give a polynomial-time algorithm that a node in a hypercube-like network can be diagnosed correctly in three test rounds under the BGM diagnosis model.

Keywords: system diagnosis, diagnosability, local diagnosis, BGM model, hypercube-like network

DOI: 10.3233/FI-222114

Journal: Fundamenta Informaticae, vol. 185, no. 4, pp. 357-373, 2022