Conditional Diagnosability of Cayley Graphs Generated by Transposition Trees under the PMC Model

被引：18

作者：

Chang, Naiwen ^{[1
]}

Cheng, Eddie ^{[2
]}

Hsieh, Sunyuan ^{[1
]}

机构：

[1] Natl Cheng Kung Univ, Dept Comp Sci & Informat Engn, Tainan 70101, Taiwan

[2] Oakland Univ, Dept Math & Stat, Rochester, MI 48309 USA

来源：

ACM TRANSACTIONS ON DESIGN AUTOMATION OF ELECTRONIC SYSTEMS | 2015年 / 20卷 / 02期

关键词：

Interconnection networks; PMCmodel; conditional diagnosability; Cayley graphs; fault tolerance; multiprocessor systems; Design; Algorithms; Performance; COMPOSITION NETWORKS; INTERCONNECTION NETWORKS; CONNECTION ASSIGNMENT; FAULT IDENTIFICATION; STAR GRAPHS; DIAGNOSIS;

D O I：

10.1145/2699854

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

Processor fault diagnosis has played an essential role in measuring the reliability of a multiprocessor system. The diagnosability of many well-known multiprocessor systems has been widely investigated. Conditional diagnosability is a novel measure of diagnosability by adding a further condition that any fault set cannot contain all the neighbors of every node in the system. Several known structural properties of Cayley graphs are exhibited. Based on these properties, we investigate the conditional diagnosability of Cayley graphs generated by transposition trees under the PMC model and show that it is 4n -11 for n >= 4 except for the n-dimensional star graph for which it has been shown to be 8n-21 for n >= 5 (refer to Chang andHsieh [2014]).

引用

页数：16

共 76 条

[11] Diagnosabilities of regular networks [J].

Chang, GY ;

Chang, GJ ;

Chen, GH .

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2005, 16 (04) :314-323

[12] Structural Properties and Conditional Diagnosability of Star Graphs by Using the PMC Model [J].

Chang, Nai-Wen ;

Hsieh, Sun-Yuan .

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2014, 25 (11) :3002-3011

[13] Conditional Diagnosability of k-Ary n-Cubes under the PMC Model [J].

Chang, Nai-Wen ;

Lin, Tzu-Yin ;

Hsieh, Sun-Yuan .

ACM TRANSACTIONS ON DESIGN AUTOMATION OF ELECTRONIC SYSTEMS, 2012, 17 (04)

[14] Conditional Diagnosability of Augmented Cubes under the PMC Model [J].

Chang, Nai-Wen ;

Hsieh, Sun-Yuan .

IEEE TRANSACTIONS ON DEPENDABLE AND SECURE COMPUTING, 2012, 9 (01) :46-60

[15] On deriving conditional diagnosability of interconnection networks [J].

Cheng, E. ;

Liptak, L. ;

Qiu, K. ;

Shen, Z. .

INFORMATION PROCESSING LETTERS, 2012, 112 (17-18) :674-677

[16]

Cheng E., 2006, CONGR NUMER CONF J N, V180, P81

[17] Linearly many faults in Cayley graphs generated by transposition trees [J].

Cheng, Eddie ;

Liptak, Laszlo .

INFORMATION SCIENCES, 2007, 177 (22) :4877-4882

[18]

Cheng Eddie, 2007, 20076 OAKL U

[19]

Chiang W.-K., 1998, INT J FOUND COMPUT S, V9, P235

[20] ON FAULT IDENTIFICATION IN DIAGNOSABLE SYSTEMS [J].

CHWA, KY ;

HAKIMI, SL .

IEEE TRANSACTIONS ON COMPUTERS, 1981, 30 (06) :414-422

← 1 2 3 4 5 6 7 8 →