A Comparison Diagnosis Algorithm for Conditional Fault Local Diagnosis of Multiprocessor Systems

Yali Lv, Cheng Kuan Lin*, D. Frank Hsu, Jianxi Fan

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

An efficient diagnosis is very important for a multiprocessor system. In this paper, we present a (α, β) -trees combination S(u, X, α, β) and give some conclusions about the local diagnosis. Based on the (α, β) -trees combination, we give a conditional fault local diagnosis algorithm to identify the fault or fault-free status of each processor correctly under the MM model when the number of faulty nodes does not exceed α+ 2 β- 3 and every node has at least one fault-free neighboring node. According to our results, a connected network with a (α, β) -trees combination S(u, X, α, β) for a node u is conditionally locally (α+ 2 β- 3 ) -diagnosable at node u and the time complexity of our algorithm to diagnose u is O(α2β+ αβ2). As an application, we show that our algorithm can identify all the faulty nodes of n-dimensional star graph Sn if the faulty node number does not exceed 3 n- 8. Compared with existing algorithms, our algorithm allows more faulty node in a multiprocessor system.

Original languageEnglish
Title of host publicationNew Trends in Computer Technologies and Applications - 25th International Computer Symposium, ICS 2022, Proceedings
EditorsSun-Yuan Hsieh, Ling-Ju Hung, Sheng-Lung Peng, Ralf Klasing, Chia-Wei Lee
PublisherSpringer Science and Business Media Deutschland GmbH
Pages123-134
Number of pages12
ISBN (Print)9789811995811
DOIs
StatePublished - 2022
Event25th International Computer Symposium on New Trends in Computer Technologies and Applications, ICS 2022 - Taoyuan, Taiwan
Duration: 15 Dec 202217 Dec 2022

Publication series

NameCommunications in Computer and Information Science
Volume1723 CCIS
ISSN (Print)1865-0929
ISSN (Electronic)1865-0937

Conference

Conference25th International Computer Symposium on New Trends in Computer Technologies and Applications, ICS 2022
Country/TerritoryTaiwan
CityTaoyuan
Period15/12/2217/12/22

Keywords

  • Comparison diagnosis model
  • Conditional diagnosis
  • Diagnosis algorithm
  • Local diagnosability

Fingerprint

Dive into the research topics of 'A Comparison Diagnosis Algorithm for Conditional Fault Local Diagnosis of Multiprocessor Systems'. Together they form a unique fingerprint.

Cite this