A Tree Structure for Local Diagnosis in Multiprocessor Systems Under Comparison Model

Meirun Chen, Cheng Kuan Lin*, Kung Jui Pai

*Corresponding author for this work

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

Abstract

If we only care about the status of a particular vertex, instead of doing global diagnosis, Hsu and Tan introduced the concept of local diagnosis and proposed an extended star structure to diagnose a vertex under comparison model. Usually, there is a gap between the local diagnosability and the lower bound guaranteed by the extended star structure mentioned above. In this paper, we propose a new testing structure and corresponding diagnosis algorithm to diagnose a vertex under comparison model to better evaluate the local diagnosability. The local diagnosability of a vertex is upper bounded by its degree in the system. If the local diagnosability of each vertex equals to its degree in the system then we say this system has the strong local diagnosability property. Based on the new structure, we show that the n-dimensional star graph Sn with faulty links has the strong local diagnosability property provided that each vertex connects to at least three fault-free links. Simulations are presented to show the performance of our tree structure.

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
Pages49-60
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

Fingerprint

Dive into the research topics of 'A Tree Structure for Local Diagnosis in Multiprocessor Systems Under Comparison Model'. Together they form a unique fingerprint.

Cite this