Title :
(t, k) - Diagnosis for Matching Composition Networks under the MM* Model
Author :
Chang, Guey-Yun ; Chen, Gen-Huey ; Chang, Gerard J.
Author_Institution :
Dept. of Comput. Sci. & Inf. Eng., Nat. Taiwan Univ., Taipei
Abstract :
(t, k)-diagnosis, which is a generalization of sequential diagnosis, requires at least k faulty processors identified and repaired in each iteration provided there are at most t faulty processors, where tgesk. In this paper, a (t, k)-diagnosis algorithm under the MM* model is proposed for matching composition networks, which include many well-known interconnection networks, such as hypercubes, crossed cubes, twisted cubes, and Mobius cubes. It is shown that a matching composition network of n dimensions is (Omega((2n*log n)/n), n)-diagnosable
Keywords :
fault diagnosis; fault tolerant computing; multiprocessor interconnection networks; MM* model; Mobius cubes; crossed cubes; faulty processors; hypercubes; interconnection networks; matching composition network; sequential diagnosis generalization; twisted cubes; Computer science; Fault diagnosis; Feeds; Helium; Hypercubes; Multiprocessing systems; Multiprocessor interconnection networks; Sequential diagnosis; System testing; Tree graphs; (t; Diagnosability; MM* model; k){hbox{-}}rm diagnosis.; matching composition network; multiprocessor system; precise diagnosis strategy;
Journal_Title :
Computers, IEEE Transactions on
DOI :
10.1109/TC.2007.250624
