The Extra Connectivity and Conditional Diagnosability of Alternating Group Networks

Limei Lin; Shuming Zhou; Li Xu; Dajin Wang

doi:10.1109/TPDS.2014.2347961

The Extra Connectivity and Conditional Diagnosability of Alternating Group Networks

Limei Lin, Shuming Zhou, Li Xu, Dajin Wang

Computer Science

Research output: Contribution to journal › Article › peer-review

87 Scopus citations

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 AG_n, is 8n - 27 (n ≥ 4) under the PMC model. This is about four times of the AG_n's traditional diagnosability. As a byproduct, the strong diagnosability of AG_n is also obtained.

Original language	English
Article number	6879268
Pages (from-to)	2352-2362
Number of pages	11
Journal	IEEE Transactions on Parallel and Distributed Systems
Volume	26
Issue number	8
DOIs	https://doi.org/10.1109/TPDS.2014.2347961
State	Published - 1 Aug 2015

Keywords

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

Access to Document

10.1109/TPDS.2014.2347961

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",

note = "Publisher Copyright: {\textcopyright} 2014 IEEE.",

year = "2015",

month = aug,

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",

}

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

SN - 1045-9219

VL - 26

SP - 2352

EP - 2362

JO - IEEE Transactions on Parallel and Distributed Systems

JF - IEEE Transactions on Parallel and Distributed Systems

IS - 8

M1 - 6879268

ER -

The Extra Connectivity and Conditional Diagnosability of Alternating Group Networks

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this