A new structure for a vertex to be locally t-diagnosable in large multiprocessor systems

Meirun Chen, D. Frank Hsu, Cheng Kuan Lin*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

PMC model is the test-based diagnosis which a vertex performs the diagnosis by testing the neighbor vertices via the edges between them. 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 two structures to diagnose a vertex. The local diagnosability of a vertex is upper bounded by its degree in the system. If the local diagnosability of a vertex is equal to its degree then we say it is locally optimal diagnosable. Usually, there is a gap between the local diagnosability and the lower bound guaranteed by the two structures mentioned above. Herein, we propose a new testing structure and corresponding diagnosis algorithm to diagnose a vertex under PMC model to better evaluate the local diagnosability. And this diagnosis algorithm takes linear time. Based on this new structure, we give a sufficient condition for a vertex to be locally optimal diagnosable. As its applications, we consider the sufficient and necessary condition for a vertex of hypercubes (resp. folded hypercubes) with faulty edges to be locally optimal diagnosable.

Original languageEnglish
Pages (from-to)81-90
Number of pages10
JournalTheoretical Computer Science
Volume934
DOIs
StatePublished - 23 Oct 2022

Keywords

  • Diagnosability
  • Folded hypercube
  • Hypercube
  • Local diagnosability
  • PMC model

Fingerprint

Dive into the research topics of 'A new structure for a vertex to be locally t-diagnosable in large multiprocessor systems'. Together they form a unique fingerprint.

Cite this