A scalable comparison-based diagnosis algorithm for hypercube-like networks

Tai Ling Ye, Sun-Yuan Hsieh

Research output: Contribution to journalArticle

14 Citations (Scopus)

Abstract

Comparison-based diagnosis is a realistic approach to detect faults in multiprocessor systems. The Maeng, Malek (MM) model for comparison-based diagnosis defines a strategy based on sending the same input (or task) from a processor to some pair of distinct neighboring processors, and then comparing their responses. Sengupta and Dahbura proposed a further modification of the MM model, called the MM* model, in which any processor v has to test another two processors if v is adjacent to them. Sengupta and Dahbura presented a O(N5)-time diagnosis algorithm for general diagnosable systems under the MM* model, where N is the number of processors in the system. By exploiting the cycle decomposition property, we improve the above result by presenting a O(N(log2N)2) -time diagnosis algorithm for a class of hypercube-like networks under the MM* model.

Original languageEnglish
Article number6631482
Pages (from-to)789-799
Number of pages11
JournalIEEE Transactions on Reliability
Volume62
Issue number4
DOIs
Publication statusPublished - 2013 Dec 1

All Science Journal Classification (ASJC) codes

  • Safety, Risk, Reliability and Quality
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'A scalable comparison-based diagnosis algorithm for hypercube-like networks'. Together they form a unique fingerprint.

  • Cite this