Determining the conditional diagnosability of k-ary n-cubes under the MM* model

Sun Yuan Hsieh, Chi Ya Kao

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Citations (Scopus)

Abstract

Processor fault diagnosis plays an important role for measuring the reliability of multiprocessor systems, and the diagnosability of many well-known interconnection networks has been investigated widely. Conditional diagnosability is a novel measure of diagnosability, which is introduced by Lai et al., by adding an additional condition that any faulty set cannot contain all the neighbors of any vertex in a system. The class of k-ary n-cubes contains as special cases many topologies important to parallel processing, such as rings, hypercubes, and tori. In this paper, we study some topological properties of the k-ary n-cube, denoted by Qk n. Then we apply them to show that the conditional diagnosability of Qk n under the comparison diagnosis model is tc(Qk n) = 6n-5 for k ≥ 4 and n ≤ 4.

Original languageEnglish
Title of host publicationStructural Information and Communication Complexity - 18th International Colloquium, SIROCCO 2011, Proceedings
Pages78-88
Number of pages11
DOIs
Publication statusPublished - 2011 Aug 10
Event18th Colloquium on Structural Information and Communication Complexity, SIROCCO 2011 - Gdansk, Poland
Duration: 2011 Jun 262011 Jun 29

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6796 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other18th Colloquium on Structural Information and Communication Complexity, SIROCCO 2011
CountryPoland
CityGdansk
Period11-06-2611-06-29

Fingerprint

K-ary N-cubes
Diagnosability
Failure analysis
Topology
Processing
Interconnection Networks
Multiprocessor Systems
Topological Properties
Parallel Processing
Fault Diagnosis
Hypercube
Model
Torus
Ring
Vertex of a graph

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Hsieh, S. Y., & Kao, C. Y. (2011). Determining the conditional diagnosability of k-ary n-cubes under the MM* model. In Structural Information and Communication Complexity - 18th International Colloquium, SIROCCO 2011, Proceedings (pp. 78-88). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6796 LNCS). https://doi.org/10.1007/978-3-642-22212-2_8
Hsieh, Sun Yuan ; Kao, Chi Ya. / Determining the conditional diagnosability of k-ary n-cubes under the MM* model. Structural Information and Communication Complexity - 18th International Colloquium, SIROCCO 2011, Proceedings. 2011. pp. 78-88 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{b121dda600984a4fa7bb0514d46484a8,
title = "Determining the conditional diagnosability of k-ary n-cubes under the MM* model",
abstract = "Processor fault diagnosis plays an important role for measuring the reliability of multiprocessor systems, and the diagnosability of many well-known interconnection networks has been investigated widely. Conditional diagnosability is a novel measure of diagnosability, which is introduced by Lai et al., by adding an additional condition that any faulty set cannot contain all the neighbors of any vertex in a system. The class of k-ary n-cubes contains as special cases many topologies important to parallel processing, such as rings, hypercubes, and tori. In this paper, we study some topological properties of the k-ary n-cube, denoted by Qk n. Then we apply them to show that the conditional diagnosability of Qk n under the comparison diagnosis model is tc(Qk n) = 6n-5 for k ≥ 4 and n ≤ 4.",
author = "Hsieh, {Sun Yuan} and Kao, {Chi Ya}",
year = "2011",
month = "8",
day = "10",
doi = "10.1007/978-3-642-22212-2_8",
language = "English",
isbn = "9783642222115",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "78--88",
booktitle = "Structural Information and Communication Complexity - 18th International Colloquium, SIROCCO 2011, Proceedings",

}

Hsieh, SY & Kao, CY 2011, Determining the conditional diagnosability of k-ary n-cubes under the MM* model. in Structural Information and Communication Complexity - 18th International Colloquium, SIROCCO 2011, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6796 LNCS, pp. 78-88, 18th Colloquium on Structural Information and Communication Complexity, SIROCCO 2011, Gdansk, Poland, 11-06-26. https://doi.org/10.1007/978-3-642-22212-2_8

Determining the conditional diagnosability of k-ary n-cubes under the MM* model. / Hsieh, Sun Yuan; Kao, Chi Ya.

Structural Information and Communication Complexity - 18th International Colloquium, SIROCCO 2011, Proceedings. 2011. p. 78-88 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6796 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Determining the conditional diagnosability of k-ary n-cubes under the MM* model

AU - Hsieh, Sun Yuan

AU - Kao, Chi Ya

PY - 2011/8/10

Y1 - 2011/8/10

N2 - Processor fault diagnosis plays an important role for measuring the reliability of multiprocessor systems, and the diagnosability of many well-known interconnection networks has been investigated widely. Conditional diagnosability is a novel measure of diagnosability, which is introduced by Lai et al., by adding an additional condition that any faulty set cannot contain all the neighbors of any vertex in a system. The class of k-ary n-cubes contains as special cases many topologies important to parallel processing, such as rings, hypercubes, and tori. In this paper, we study some topological properties of the k-ary n-cube, denoted by Qk n. Then we apply them to show that the conditional diagnosability of Qk n under the comparison diagnosis model is tc(Qk n) = 6n-5 for k ≥ 4 and n ≤ 4.

AB - Processor fault diagnosis plays an important role for measuring the reliability of multiprocessor systems, and the diagnosability of many well-known interconnection networks has been investigated widely. Conditional diagnosability is a novel measure of diagnosability, which is introduced by Lai et al., by adding an additional condition that any faulty set cannot contain all the neighbors of any vertex in a system. The class of k-ary n-cubes contains as special cases many topologies important to parallel processing, such as rings, hypercubes, and tori. In this paper, we study some topological properties of the k-ary n-cube, denoted by Qk n. Then we apply them to show that the conditional diagnosability of Qk n under the comparison diagnosis model is tc(Qk n) = 6n-5 for k ≥ 4 and n ≤ 4.

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

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

U2 - 10.1007/978-3-642-22212-2_8

DO - 10.1007/978-3-642-22212-2_8

M3 - Conference contribution

AN - SCOPUS:79961133998

SN - 9783642222115

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 78

EP - 88

BT - Structural Information and Communication Complexity - 18th International Colloquium, SIROCCO 2011, Proceedings

ER -

Hsieh SY, Kao CY. Determining the conditional diagnosability of k-ary n-cubes under the MM* model. In Structural Information and Communication Complexity - 18th International Colloquium, SIROCCO 2011, Proceedings. 2011. p. 78-88. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-642-22212-2_8