Improved precise fault diagnosis algorithm for hypercube-like systems based on the comparison diagnosis model

Tai Ling Ye, Dun Wei Cheng, Sun Yuan Hsieh

Research output: Contribution to journalArticle

1 Citation (Scopus)

Abstract

Multiprocessor systems are being increasingly adopted and the system reliability is an important perspective for multiprocessor systems. The fault diagnosis has become crucial for achieving high reliability in multiprocessor systems. The precise fault diagnosis diagnoses all processors correctly. In the comparison-based model, it allows a processor to perform diagnosis by contrasting the responses from a pair of neighboring processors through sending the identical assignment. On the basis of comparison-based model, Sengupta and Dahbura ("On self-diagnosable multiprocessor systems: diagnosis by the comparison approach," IEEE Transaction on Computers, vol. 41, no. 11, pp. 1386-1396, 1992) put forward the MM model, any processor c diagnoses two processors c1 and c2 if c has direct communication links to them. Sengupta and Dahbura also designed an O(N5)-time precise fault diagnosis algorithm to diagnose faulty processors for general topologies by using the MM Model, where N is the cardinality of processor set in multiprocessor systems. Lately, Ye and Hsieh ("A scalable comparison-based diagnosis algorithm for hypercube-like net-works," IEEE Transaction on Reliability, vol. 62, no. 4, pp. 789-799, 2013) devised an precise fault diagnosis algorithm to diagnose all faulty processors for hypercube-like networks by using the MM model with O(N(log2N)2) time complexity. On the basis of Hamiltonian cycle properties, we improve the aforementioned results by presenting an O(N)-time precise fault diagnosis algorithm to diagnose all faulty processors for hypercube-like networks by using the MM Model.

Original languageEnglish
Article number1650009
JournalJournal of Interconnection Networks
Volume16
Issue number3-4
DOIs
Publication statusPublished - 2016 Dec 1

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Improved precise fault diagnosis algorithm for hypercube-like systems based on the comparison diagnosis model'. Together they form a unique fingerprint.

Cite this