A Scalable Comparison-Based Diagnosis Algorithm for Hypercube-Like Networks
Authors:
- 17 October 2013
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Reliability
- Vol. 62 (4) , 789-799
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.Keywords
This publication has 31 references indexed in Scilit:
- Efficient Fault Identification of Diagnosable Systems under the Comparison ModelIEEE Transactions on Computers, 2007
- A comparison-based diagnosis algorithm tailored for crossed cube multiprocessor systemsMicroprocessors and Microsystems, 2005
- The locally twisted cubesInternational Journal of Computer Mathematics, 2005
- Sequential Diagnosis of Processor Array SystemsIEEE Transactions on Reliability, 2004
- A class of hypercube-like networks2002
- On self-diagnosable multiprocessor systems: diagnosis by the comparison approachIEEE Transactions on Computers, 1992
- Topological properties of hypercubesIEEE Transactions on Computers, 1988
- A O(t/sup 3/+ mod E mod ) fault identification algorithm for diagnosable systemsIEEE Transactions on Computers, 1988
- On Fault Isolation and Identification in t1/t1-Diagnosable SystemsIEEE Transactions on Computers, 1986
- An 0(n2.5) Fault Identification Algorithm for Diagnosable SystemsIEEE Transactions on Computers, 1984