(t; k)-Diagnosis for matching composition networks

Author

Guey-Yun Chang ; Chen, Gen-Huey ; Chang, Guey-Yun

Author_Institution

Dept. of Comput. Sci. & Inf. Eng., Nat. Taiwan Univ., Taipei, Taiwan

Volume

55

Issue

1

fYear

2006

Firstpage

88

Lastpage

92

Abstract

(t, k)-diagnosis, which is a generalization of sequential diagnosis, requires at least k faulty processors identified and replaced in each iteration provided there are at most t faulty processors, where t ≥k This paper proposes a (t,k) diagnosis algorithm 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 matching composition networks of n dimensions are (Ω(2ⁿ·logn/n),n)-diagnosable, where n > 5.

Keywords

fault diagnosis; multiprocessing systems; multiprocessor interconnection networks; (t,k)-diagnosis algorithm; Mobius cubes; composition network matching; crossed cubes; faulty processors; hypercubes; interconnection network; multiprocessor system; sequential diagnosis; twisted cubes; Communication channels; Fault diagnosis; Hypercubes; Multiprocessing systems; Multiprocessor interconnection networks; Sequential diagnosis; System testing; Topology; Tree graphs; (t; Index Terms- Diagnosability; PMC model; k){hbox{-}}{rm diagnosis}.; matching composition network; multiprocessor system; precise diagnosis strategy; sequential diagnosis;

fLanguage

English

Journal_Title

Computers, IEEE Transactions on

Publisher

ieee

ISSN

0018-9340

Type

jour

DOI

10.1109/TC.2006.1

Filename

1545754