Diagnosability for a family of matching composition networks

被引：8
作者：
Chen, Meirun [1 ]
Habib, Michel [2 ,3 ]
Lin, Cheng-Kuan [4 ]
机构：
[1] Tianjin Normal Univ, Coll Math Sci, Tianjin, Peoples R China
[2] CNRS, IRIF, Paris, France
[3] Univ Paris Cite, Paris, France
[4] Natl Yang Ming Chiao Tung Univ, Dept Comp Sci, Hsinchu, Taiwan
来源：
JOURNAL OF SUPERCOMPUTING | 2023年 / 79卷 / 07期
基金：
中国国家自然科学基金;
关键词：
Diagnosability; Matching composition networks; PMC model; MM* model; T/K-DIAGNOSABILITY; CONDITIONAL DIAGNOSABILITY; FAULT DIAGNOSABILITY; DIAGNOSIS; CONNECTIVITY; HYPERCUBES;
D O I：
10.1007/s11227-022-04949-8
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
We study here the diagnosability of networks under two models of self-diagnosis: PMC model introduced by Preparata, Metze and Chien (IEEE Trans Electronic Computers 16(12):848-854 (1967)) and MM* model introduced by Sengupta and Dahbura (IEEE Trans Computers 41(11):1386-1396 (1992)) which is the variant of the comparison model (1980). The diagnosability of a network of processors is the maximum number of faulty processors that can be identified by the network itself. Lee and Hsieh (IEEE Trans Dependable Secure Comput 8(2):246-255 (2011)) considered the diagnosability of networks obtained by connecting two networks of the same order by two perfect matchings and got the lower bounds. Usually, there is a gap between the lower bound and the exact value of the diagnosability. In this paper, we completely determine the diagnosability of this family of matching composition networks.
引用
收藏
页码：7584 / 7608
页数：25
相关论文
共 52 条
[1]  
ARMSTRONG JR, 1981, IEEE T COMPUT, V30, P587, DOI 10.1109/TC.1981.1675844
[2]  
Bondy J.A., 2008, Graph Theory, DOI DOI 10.1007/978-1-84628-970-5
[3]   Diagnosabilities of regular networks [J].
Chang, GY ;
Chang, GJ ;
Chen, GH .
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2005, 16 (04) :314-323
[4]   A new structure for a vertex to be locally t-diagnosable in large multiprocessor systems [J].
Chen, Meirun ;
Hsu, D. Frank ;
Lin, Cheng-Kuan .
THEORETICAL COMPUTER SCIENCE, 2022, 934 :81-90
[5]   Augmented cubes [J].
Choudum, SA ;
Sunitha, V .
NETWORKS, 2002, 40 (02) :71-84
[6]   SCHEMES FOR FAULT-TOLERANT COMPUTING - A COMPARISON OF MODULARLY REDUNDANT AND T-DIAGNOSABLE SYSTEMS [J].
CHWA, KY ;
HAKIMI, SL .
INFORMATION AND CONTROL, 1981, 49 (03) :212-238
[7]   THE MOBIUS CUBES [J].
CULL, P ;
LARSON, SM .
IEEE TRANSACTIONS ON COMPUTERS, 1995, 44 (05) :647-659
[8]  
DAHBURA AT, 1984, IEEE T COMPUT, V33, P486, DOI 10.1109/TC.1984.1676472
[9]   EMBEDDINGS INTO HYPER PETERSEN NETWORKS - YET ANOTHER HYPERCUBE-LIKE INTERCONNECTION TOPOLOGY [J].
DAS, SK ;
OHRING, S ;
BANERJEE, AK .
VLSI DESIGN, 1995, 2 (04) :335-351
[10]  
DAS SK, 1992, FRONTIERS 92 : THE FOURTH SYMPOSIUM ON THE FRONTIERS OF MASSIVELY PARALLEL COMPUTATION, P270, DOI 10.1109/FMPC.1992.234949
123456