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

Tai Ling Ye, Sun Yuan Hsieh

Research output: Contribution to journalArticlepeer-review

17 Citations (Scopus)


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
Issue number4
Publication statusPublished - 2013 Dec

All Science Journal Classification (ASJC) codes

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


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

Cite this