(t, k)-diagnosis for matching composition networks

Guey Yun Chang; Gen Huey Chen; Gerard J. Chang

doi:10.1109/TC.2006.1

(t, k)-diagnosis for matching composition networks

Guey Yun Chang, Gen Huey Chen, Gerard J. Chang

Research output: Contribution to journal › Review article › peer-review

43 Scopus citations

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 Möbius cubes. It is shown that matching composition networks of n dimensions are (Ω(2log n/n),n)-diagnosable, where n > 5.

Original language	English
Pages (from-to)	88-92
Number of pages	5
Journal	IEEE Transactions on Computers
Volume	55
Issue number	1
DOIs	https://doi.org/10.1109/TC.2006.1
State	Published - Jan 2006

Keywords

(t, k)-diagnosis
Diagnosability
Matching composition network
Multiprocessor system
PMC model
Precise diagnosis strategy
Sequential diagnosis

Access to Document

10.1109/TC.2006.1

Cite this

@article{1f83fd0ff14f40979d13d55ed5d9a20f,

title = "(t, k)-diagnosis for matching composition networks",

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 M{\"o}bius cubes. It is shown that matching composition networks of n dimensions are (Ω(2log n/n),n)-diagnosable, where n > 5.",

keywords = "(t, k)-diagnosis, Diagnosability, Matching composition network, Multiprocessor system, PMC model, Precise diagnosis strategy, Sequential diagnosis",

author = "Chang, {Guey Yun} and Chen, {Gen Huey} and Chang, {Gerard J.}",

note = "Funding Information: The work of Gerard J. Chang was supported in part by the National Science Council of Taiwan under grant NSC93-2213-E0002-028.",

year = "2006",

month = jan,

doi = "10.1109/TC.2006.1",

language = "???core.languages.en_GB???",

volume = "55",

pages = "88--92",

journal = "IEEE Transactions on Computers",

issn = "0018-9340",

number = "1",

}

TY - JOUR

T1 - (t, k)-diagnosis for matching composition networks

AU - Chang, Guey Yun

AU - Chen, Gen Huey

AU - Chang, Gerard J.

N1 - Funding Information: The work of Gerard J. Chang was supported in part by the National Science Council of Taiwan under grant NSC93-2213-E0002-028.

PY - 2006/1

Y1 - 2006/1

N2 - (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 Möbius cubes. It is shown that matching composition networks of n dimensions are (Ω(2log n/n),n)-diagnosable, where n > 5.

AB - (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 Möbius cubes. It is shown that matching composition networks of n dimensions are (Ω(2log n/n),n)-diagnosable, where n > 5.

KW - (t, k)-diagnosis

KW - Diagnosability

KW - Matching composition network

KW - Multiprocessor system

KW - PMC model

KW - Precise diagnosis strategy

KW - Sequential diagnosis

UR - http://www.scopus.com/inward/record.url?scp=33947703655&partnerID=8YFLogxK

U2 - 10.1109/TC.2006.1

DO - 10.1109/TC.2006.1

M3 - 回顧評介論文

AN - SCOPUS:33947703655

SN - 0018-9340

VL - 55

SP - 88

EP - 92

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

IS - 1

ER -

(t, k)-diagnosis for matching composition networks

Abstract

Keywords

Access to Document

Fingerprint

Cite this