Conditional Diagnosability of (n,k)-Star Graphs Under the PMC Model

被引：46
作者：
Chang, Nai-Wen [1 ]
Hsieh, Sun-Yuan [1 ]
机构：
[1] Natl Cheng Kung Univ, Dept Comp Sci & Informat Engn, Tainan 70101, Taiwan
来源：
IEEE TRANSACTIONS ON DEPENDABLE AND SECURE COMPUTING | 2018年 / 15卷 / 02期
关键词：
Interconnection networks; PMC model; conditional diagnosability; (n; k)-star graphs; fault tolerance; multiprocessor systems; COMPOSITION NETWORKS; FAULT-DIAGNOSIS; CONNECTION ASSIGNMENT; TRANSPOSITION TREES; STAR GRAPHS; (N; HYPERCUBES; ARRAY;
D O I：
10.1109/TDSC.2016.2562620
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
Fault diagnosis has played a major role in measuring the reliability of multiprocessor systems. The diagnosability of many well-known multiprocessor systems has been widely investigated. Conditional diagnosability is a novel property of measuring 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 (n,k)-star graphs are exhibited. Based on these properties, we investigate the conditional diagnosability of(n,k)-star graphs under the PMC model, and show that it is 1) [n/2] - 1 for n >= 4 and k = 1, and 2) n + 3k - 6 for 2 <= k <= n - 3.
引用
收藏
页码：207 / 216
页数：10
相关论文
共 62 条
[1]  
Akers S. B., 1987, Proceedings of the 1987 International Conference on Parallel Processing, P393
[2]   A GROUP-THEORETIC MODEL FOR SYMMETRIC INTERCONNECTION NETWORKS [J].
AKERS, SB ;
KRISHNAMURTHY, B .
IEEE TRANSACTIONS ON COMPUTERS, 1989, 38 (04) :555-566
[3]  
ARMSTRONG JR, 1981, IEEE T COMPUT, V30, P587, DOI 10.1109/TC.1981.1675844
[4]  
BARSI F, 1976, IEEE T COMPUT, V25, P585, DOI 10.1109/TC.1976.1674658
[5]   Conditional (t, k)-Diagnosis under the PMC Model [J].
Chang, Guey-Yun .
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2011, 22 (11) :1797-1803
[6]   (t, k)-diagnosis for matching composition networks [J].
Chang, GY ;
Chen, GH ;
Chang, GJ .
IEEE TRANSACTIONS ON COMPUTERS, 2006, 55 (01) :88-92
[7]   Diagnosabilities of regular networks [J].
Chang, GY ;
Chang, GJ ;
Chen, GH .
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2005, 16 (04) :314-323
[8]   Conditional Diagnosability of (n, k)-Star Networks Under the Comparison Diagnosis Model [J].
Chang, Nai-Wen ;
Deng, Wei-Hao ;
Hsieh, Sun-Yuan .
IEEE TRANSACTIONS ON RELIABILITY, 2015, 64 (01) :132-143
[9]   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
[10]   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)
1234567