Conditional diagnosability of arrangement graphs under the PMC model

Limei Lin, Shuming Zhou, Li Xu, Dajin Wang

Research output: Contribution to journalArticle

23 Citations (Scopus)

Abstract

Processor fault diagnosis has played an important role in measuring the reliability of a multiprocessor system, and the diagnosabilities of many well-known multiprocessor systems have been investigated. The conditional diagnosability has been widely accepted as a measure of diagnosability by assuming an additional condition that any fault-set can't contain all the neighbors of any node in a multiprocessor system. This paper considers the conditional diagnosability of an (n, k)-arrangement graph An,k, a flexible interconnection network model for multiprocessor systems, under the classical PMC diagnostic model, and determines that the conditional diagnosability of An,k (k≥2, n≥k+2) is (4k-4)(n-k)-3, which is about four times its traditional diagnosability.

Original languageEnglish
Pages (from-to)79-97
Number of pages19
JournalTheoretical Computer Science
Volume548
Issue numberC
DOIs
StatePublished - 1 Jan 2014

Fingerprint

Diagnosability
Arrangement
Multiprocessor Systems
Graph in graph theory
Failure analysis
Model
Model Diagnostics
Interconnection Networks
Fault Diagnosis
Network Model
Fault
Vertex of a graph

Keywords

  • Arrangement graphs
  • Conditional diagnosability
  • Fault tolerance
  • PMC model
  • System reliability

Cite this

Lin, Limei ; Zhou, Shuming ; Xu, Li ; Wang, Dajin. / Conditional diagnosability of arrangement graphs under the PMC model. In: Theoretical Computer Science. 2014 ; Vol. 548, No. C. pp. 79-97.
@article{6c56068c0e654cba93358060409f5873,
title = "Conditional diagnosability of arrangement graphs under the PMC model",
abstract = "Processor fault diagnosis has played an important role in measuring the reliability of a multiprocessor system, and the diagnosabilities of many well-known multiprocessor systems have been investigated. The conditional diagnosability has been widely accepted as a measure of diagnosability by assuming an additional condition that any fault-set can't contain all the neighbors of any node in a multiprocessor system. This paper considers the conditional diagnosability of an (n, k)-arrangement graph An,k, a flexible interconnection network model for multiprocessor systems, under the classical PMC diagnostic model, and determines that the conditional diagnosability of An,k (k≥2, n≥k+2) is (4k-4)(n-k)-3, which is about four times its traditional diagnosability.",
keywords = "Arrangement graphs, Conditional diagnosability, Fault tolerance, PMC model, System reliability",
author = "Limei Lin and Shuming Zhou and Li Xu and Dajin Wang",
year = "2014",
month = "1",
day = "1",
doi = "10.1016/j.tcs.2014.06.041",
language = "English",
volume = "548",
pages = "79--97",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",
number = "C",

}

Conditional diagnosability of arrangement graphs under the PMC model. / Lin, Limei; Zhou, Shuming; Xu, Li; Wang, Dajin.

In: Theoretical Computer Science, Vol. 548, No. C, 01.01.2014, p. 79-97.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Conditional diagnosability of arrangement graphs under the PMC model

AU - Lin, Limei

AU - Zhou, Shuming

AU - Xu, Li

AU - Wang, Dajin

PY - 2014/1/1

Y1 - 2014/1/1

N2 - Processor fault diagnosis has played an important role in measuring the reliability of a multiprocessor system, and the diagnosabilities of many well-known multiprocessor systems have been investigated. The conditional diagnosability has been widely accepted as a measure of diagnosability by assuming an additional condition that any fault-set can't contain all the neighbors of any node in a multiprocessor system. This paper considers the conditional diagnosability of an (n, k)-arrangement graph An,k, a flexible interconnection network model for multiprocessor systems, under the classical PMC diagnostic model, and determines that the conditional diagnosability of An,k (k≥2, n≥k+2) is (4k-4)(n-k)-3, which is about four times its traditional diagnosability.

AB - Processor fault diagnosis has played an important role in measuring the reliability of a multiprocessor system, and the diagnosabilities of many well-known multiprocessor systems have been investigated. The conditional diagnosability has been widely accepted as a measure of diagnosability by assuming an additional condition that any fault-set can't contain all the neighbors of any node in a multiprocessor system. This paper considers the conditional diagnosability of an (n, k)-arrangement graph An,k, a flexible interconnection network model for multiprocessor systems, under the classical PMC diagnostic model, and determines that the conditional diagnosability of An,k (k≥2, n≥k+2) is (4k-4)(n-k)-3, which is about four times its traditional diagnosability.

KW - Arrangement graphs

KW - Conditional diagnosability

KW - Fault tolerance

KW - PMC model

KW - System reliability

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

U2 - 10.1016/j.tcs.2014.06.041

DO - 10.1016/j.tcs.2014.06.041

M3 - Article

AN - SCOPUS:84926295668

VL - 548

SP - 79

EP - 97

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - C

ER -