Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10343691 | Microprocessors and Microsystems | 2005 | 7 Pages |
Abstract
Comparison-based diagnosis is an effective approach to system-level fault diagnosis. Under the Maeng-Malek comparison model (MM* model), Sengupta and Dahbura proposed an O(N5) diagnosis algorithm for general diagnosable systems with N nodes. Thanks to lower diameter and better graph embedding capability as compared with a hypercube of the same size, the crossed cube has been a promising candidate for interconnection networks. In this paper, we propose a fault diagnosis algorithm tailored for crossed cube connected multicomputer systems under the MM* model. By introducing appropriate data structures, this algorithm runs in O(Nlog22N) time, which is linear in the size of the input. As a result, this algorithm is significantly superior to the Sengupta-Dahbura's algorithm when applied to crossed cube systems.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Networks and Communications
Authors
Xiaofan Yang, Graham M. Megson, David J. Evans,