The Extra Connectivity and Conditional Diagnosability of Alternating Group Networks

Limei Lin, Shuming Zhou, Li Xu, Dajin Wang

Research output: Contribution to journalArticle

38 Citations (Scopus)

Abstract

Extra connectivity, diagnosability, and conditional diagnosability are all important measures for a multiprocessor system's ability to diagnose and tolerate faults. In this paper, we analyze the fault tolerance ability for the alternating group graph, a well-known interconnection network proposed for multiprocessor systems, establish the h-extra connectivity, where 1 ≤ h ≤ 3 , and prove that the conditional diagnosability of an n-dimensional alternating group graph, denoted by AGn, is 8n - 27 (n ≥ 4) under the PMC model. This is about four times of the AGn's traditional diagnosability. As a byproduct, the strong diagnosability of AGn is also obtained.

Original languageEnglish
Article number6879268
Pages (from-to)2352-2362
Number of pages11
JournalIEEE Transactions on Parallel and Distributed Systems
Volume26
Issue number8
DOIs
StatePublished - 1 Aug 2015

Fingerprint

Fault tolerance
Byproducts

Keywords

  • Alternating group graphs
  • PMC model
  • conditional diagnosability
  • extra connectivity
  • fault tolerance
  • strong diagnosability
  • system-level diagnosis

Cite this

@article{4469d413c2a240ec9d2e11548a4a24c9,
title = "The Extra Connectivity and Conditional Diagnosability of Alternating Group Networks",
abstract = "Extra connectivity, diagnosability, and conditional diagnosability are all important measures for a multiprocessor system's ability to diagnose and tolerate faults. In this paper, we analyze the fault tolerance ability for the alternating group graph, a well-known interconnection network proposed for multiprocessor systems, establish the h-extra connectivity, where 1 ≤ h ≤ 3 , and prove that the conditional diagnosability of an n-dimensional alternating group graph, denoted by AGn, is 8n - 27 (n ≥ 4) under the PMC model. This is about four times of the AGn's traditional diagnosability. As a byproduct, the strong diagnosability of AGn is also obtained.",
keywords = "Alternating group graphs, PMC model, conditional diagnosability, extra connectivity, fault tolerance, strong diagnosability, system-level diagnosis",
author = "Limei Lin and Shuming Zhou and Li Xu and Dajin Wang",
year = "2015",
month = "8",
day = "1",
doi = "10.1109/TPDS.2014.2347961",
language = "English",
volume = "26",
pages = "2352--2362",
journal = "IEEE Transactions on Parallel and Distributed Systems",
issn = "1045-9219",
publisher = "IEEE Computer Society",
number = "8",

}

The Extra Connectivity and Conditional Diagnosability of Alternating Group Networks. / Lin, Limei; Zhou, Shuming; Xu, Li; Wang, Dajin.

In: IEEE Transactions on Parallel and Distributed Systems, Vol. 26, No. 8, 6879268, 01.08.2015, p. 2352-2362.

Research output: Contribution to journalArticle

TY - JOUR

T1 - The Extra Connectivity and Conditional Diagnosability of Alternating Group Networks

AU - Lin, Limei

AU - Zhou, Shuming

AU - Xu, Li

AU - Wang, Dajin

PY - 2015/8/1

Y1 - 2015/8/1

N2 - Extra connectivity, diagnosability, and conditional diagnosability are all important measures for a multiprocessor system's ability to diagnose and tolerate faults. In this paper, we analyze the fault tolerance ability for the alternating group graph, a well-known interconnection network proposed for multiprocessor systems, establish the h-extra connectivity, where 1 ≤ h ≤ 3 , and prove that the conditional diagnosability of an n-dimensional alternating group graph, denoted by AGn, is 8n - 27 (n ≥ 4) under the PMC model. This is about four times of the AGn's traditional diagnosability. As a byproduct, the strong diagnosability of AGn is also obtained.

AB - Extra connectivity, diagnosability, and conditional diagnosability are all important measures for a multiprocessor system's ability to diagnose and tolerate faults. In this paper, we analyze the fault tolerance ability for the alternating group graph, a well-known interconnection network proposed for multiprocessor systems, establish the h-extra connectivity, where 1 ≤ h ≤ 3 , and prove that the conditional diagnosability of an n-dimensional alternating group graph, denoted by AGn, is 8n - 27 (n ≥ 4) under the PMC model. This is about four times of the AGn's traditional diagnosability. As a byproduct, the strong diagnosability of AGn is also obtained.

KW - Alternating group graphs

KW - PMC model

KW - conditional diagnosability

KW - extra connectivity

KW - fault tolerance

KW - strong diagnosability

KW - system-level diagnosis

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

U2 - 10.1109/TPDS.2014.2347961

DO - 10.1109/TPDS.2014.2347961

M3 - Article

AN - SCOPUS:84937404142

VL - 26

SP - 2352

EP - 2362

JO - IEEE Transactions on Parallel and Distributed Systems

JF - IEEE Transactions on Parallel and Distributed Systems

SN - 1045-9219

IS - 8

M1 - 6879268

ER -