Diagnosability of Enhanced Hypercubes

Research output: Contribution to journalArticle

71 Citations (Scopus)

Abstract

An enhanced hypercube is obtained by adding 2" -1 more links to a regular hypercube of 2" processors. It has been shown that enhanced hypercubes have very good improvements over regular hypercubes in many measurements such as mean internode distance, diameter and traffic density. This paper proves that in the aspect of diagnosability, enhanced hypercubes also achieve improvements. Two diagnosis strategies, both using the well-known PMC diagnostic model, are studied: the precise (onestep) strategy proposed by Preparata et al. and the pessimistic strategy proposed by Friedman. Under the precise strategy, the diagnosability is shown to be increased to n + 1 in enhanced hypercubes (in regular hypercubes the diagnosability is n under this strategy). Under the pessimistic strategy, the diagnosability is shown to be increased to 2n (in regular hypercubes the diagnosability under this strategy is 2n — 2). Since the failure probability of one node is fairly low nowadays so that the increase of diagnosability by one or two will considerably enhance the system’s self-diagnostic capability, and considering the fact that diagnosability does not “easily" increase as the links in networks do, these improvements are noticeable.

Original languageEnglish
Pages (from-to)1054-1061
Number of pages8
JournalIEEE Transactions on Computers
Volume43
Issue number9
DOIs
StatePublished - 1 Jan 1994

Fingerprint

Diagnosability
Hypercube
Model Diagnostics
Failure Probability
Strategy
Diagnostics
Traffic

Keywords

  • Diagnosability
  • diagnosis
  • fault tolerance
  • graph
  • hypercubes
  • multicomputer networks
  • theory

Cite this

@article{7e1d8c8099a540b1947d0468134de9f5,
title = "Diagnosability of Enhanced Hypercubes",
abstract = "An enhanced hypercube is obtained by adding 2{"} -1 more links to a regular hypercube of 2{"} processors. It has been shown that enhanced hypercubes have very good improvements over regular hypercubes in many measurements such as mean internode distance, diameter and traffic density. This paper proves that in the aspect of diagnosability, enhanced hypercubes also achieve improvements. Two diagnosis strategies, both using the well-known PMC diagnostic model, are studied: the precise (onestep) strategy proposed by Preparata et al. and the pessimistic strategy proposed by Friedman. Under the precise strategy, the diagnosability is shown to be increased to n + 1 in enhanced hypercubes (in regular hypercubes the diagnosability is n under this strategy). Under the pessimistic strategy, the diagnosability is shown to be increased to 2n (in regular hypercubes the diagnosability under this strategy is 2n — 2). Since the failure probability of one node is fairly low nowadays so that the increase of diagnosability by one or two will considerably enhance the system’s self-diagnostic capability, and considering the fact that diagnosability does not “easily{"} increase as the links in networks do, these improvements are noticeable.",
keywords = "Diagnosability, diagnosis, fault tolerance, graph, hypercubes, multicomputer networks, theory",
author = "Dajin Wang",
year = "1994",
month = "1",
day = "1",
doi = "10.1109/12.312114",
language = "English",
volume = "43",
pages = "1054--1061",
journal = "IEEE Transactions on Computers",
issn = "0018-9340",
publisher = "IEEE Computer Society",
number = "9",

}

Diagnosability of Enhanced Hypercubes. / Wang, Dajin.

In: IEEE Transactions on Computers, Vol. 43, No. 9, 01.01.1994, p. 1054-1061.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Diagnosability of Enhanced Hypercubes

AU - Wang, Dajin

PY - 1994/1/1

Y1 - 1994/1/1

N2 - An enhanced hypercube is obtained by adding 2" -1 more links to a regular hypercube of 2" processors. It has been shown that enhanced hypercubes have very good improvements over regular hypercubes in many measurements such as mean internode distance, diameter and traffic density. This paper proves that in the aspect of diagnosability, enhanced hypercubes also achieve improvements. Two diagnosis strategies, both using the well-known PMC diagnostic model, are studied: the precise (onestep) strategy proposed by Preparata et al. and the pessimistic strategy proposed by Friedman. Under the precise strategy, the diagnosability is shown to be increased to n + 1 in enhanced hypercubes (in regular hypercubes the diagnosability is n under this strategy). Under the pessimistic strategy, the diagnosability is shown to be increased to 2n (in regular hypercubes the diagnosability under this strategy is 2n — 2). Since the failure probability of one node is fairly low nowadays so that the increase of diagnosability by one or two will considerably enhance the system’s self-diagnostic capability, and considering the fact that diagnosability does not “easily" increase as the links in networks do, these improvements are noticeable.

AB - An enhanced hypercube is obtained by adding 2" -1 more links to a regular hypercube of 2" processors. It has been shown that enhanced hypercubes have very good improvements over regular hypercubes in many measurements such as mean internode distance, diameter and traffic density. This paper proves that in the aspect of diagnosability, enhanced hypercubes also achieve improvements. Two diagnosis strategies, both using the well-known PMC diagnostic model, are studied: the precise (onestep) strategy proposed by Preparata et al. and the pessimistic strategy proposed by Friedman. Under the precise strategy, the diagnosability is shown to be increased to n + 1 in enhanced hypercubes (in regular hypercubes the diagnosability is n under this strategy). Under the pessimistic strategy, the diagnosability is shown to be increased to 2n (in regular hypercubes the diagnosability under this strategy is 2n — 2). Since the failure probability of one node is fairly low nowadays so that the increase of diagnosability by one or two will considerably enhance the system’s self-diagnostic capability, and considering the fact that diagnosability does not “easily" increase as the links in networks do, these improvements are noticeable.

KW - Diagnosability

KW - diagnosis

KW - fault tolerance

KW - graph

KW - hypercubes

KW - multicomputer networks

KW - theory

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

U2 - 10.1109/12.312114

DO - 10.1109/12.312114

M3 - Article

AN - SCOPUS:0001135783

VL - 43

SP - 1054

EP - 1061

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

SN - 0018-9340

IS - 9

ER -