超立方体在对称PMC模型下的g-好邻条件诊断度和g-额外条件诊断度

doi:10.11896/jsjkx.230700007

计算机科学 ›› 2024, Vol. 51 ›› Issue (9): 103-111.doi: 10.11896/jsjkx.230700007

超立方体在对称PMC模型下的g-好邻条件诊断度和g-额外条件诊断度

涂远杰¹, 程宝雷¹, 王岩¹, 韩月娟², 樊建席¹

1 苏州大学计算机科学与技术学院江苏苏州 215006
2 苏州大学信息化建设与管理中心江苏苏州 215006

收稿日期:2023-07-01 修回日期:2023-11-20 出版日期:2024-09-15 发布日期:2024-09-10
通讯作者: 樊建席(jxfan@suda.edu.cn)
作者简介:(20214227047@stu.suda.edu.cn)
基金资助:
国家自然科学基金(62172291,62272333)

g-Good-Neighbor Conditional Diagnosability and g-Extra Conditional Diagnosability of Hypercubes Under Symmetric PMC Model

TU Yuanjie¹, CHENG Baolei¹, WANG Yan¹, HAN Yuejuan², FAN Jianxi¹

1 School of Computer Science and Technology,Soochow University,Suzhou,Jiangsu 215006,China
2 Center of Information Development and Management,Soochow University,Suzhou,Jiangsu 215006,China

Received:2023-07-01 Revised:2023-11-20 Online:2024-09-15 Published:2024-09-10
About author:TU Yuanjie,born in 1999,postgra-duate,is a member of CCF(No.J1792G).His main research interests include parallel and distributed systems,and graph algorithms.
FAN Jianxi,born in 1965,Ph.D,professor,Ph.D supervisor.His main research interests include parallel and distributed systems,computer networks and graph algorithms.
Supported by:
National Natural Science Foundation of China(62172291,62272333).

摘要/Abstract

摘要： 故障诊断在维持多处理器系统的可靠性中起到了至关重要的作用,而诊断度是系统诊断能力的一个重要度量参数。除经典诊断度外还有条件诊断度,如g-好邻条件诊断度、g-额外条件诊断度等。其中g-好邻条件诊断度是在每个无故障顶点至少有g个无故障邻点的条件下定义的一种条件诊断度,g-额外条件诊断度是在每个无故障分支包含超过g个顶点的条件下定义的一种条件诊断度。故障诊断需要在特定的诊断模型下进行,如PMC模型、对称PMC模型等。对称PMC模型是在PMC模型的基础上通过添加两个假设而提出的一种新的诊断模型。n维超立方体因具有多种优越性质而被研究者们广泛研究。目前有不少在PMC模型下的诊断度研究,但缺乏在对称PMC模型下的诊断度研究。文中首先证明了超立方体在对称PMC模型下的g-好邻条件诊断度的上界和下界,当n≥4且0≤g≤n－4时上界为2^g+1(n－g－1)+2^g－1,当g≥0且n≥max{g+4,2^g+1－2^－g－g－1}时下界为(2n－2^g+1+1)2^g－1+(n－g)2^g－1－1。还证明了超立方体在对称PMC模型下的g-额外条件诊断度的上界和下界,当n≥4且0≤g≤n－4时上界为2n(g+1)－5g－2C²_g－2,当n≥4且$0 \leqslant g \leqslant \min \left\{n-4,\left\lfloor\frac{2}{3} n\right\rfloor\right\}$时下界为$\frac{3}{2} n(g+1)-g-\frac{5}{2} C_{g+1}^{2}-1$。最后通过模拟实验验证了相关理论结果的正确性。

关键词: 互连网络, 超立方体, 系统级诊断, 对称PMC模型, 条件诊断度

Abstract: Fault diagnosis plays a very important role in maintaining the reliability of multiprocessor systems,and the diagno-sability is an important measure of the diagnosis capability of the system.Except for the traditional diagnosability,there are also conditional diagnosability,such as g-good-neighbor conditional diagnosability,g-extra conditional diagnosability,etc.Where g-good-neighbor conditional diagnosability is defined under the condition that every fault-free vertex has at least g fault-free neighbors,and g-extra conditional diagnosability is defined under the condition that every fault-free component contains more than g vertices.Fault diagnosis needs to be performed under a specific diagnosis model,such as PMC model,symmetric PMC model,in which the symmetric PMC model is a new diagnosis model proposed by adding two assumptions to the PMC model.The n-dimensional hypercube has many excellent properties,so it has been widely studied by researchers.At present,there are a number of diagnosability studies under the PMC models,but there is a lack of diagnosability studies under the symmetric PMC models.This paper first investigates the upper and lower bounds for the g-good-neighbor conditional diagnosability of hypercubes under the symmetric PMC model,with an upper bound of 2^g+1(n－g－1)+2^g－1 when n≥4 and 0≤g≤n－4 and a lower bound of (2n－2^g+1+1)2^g－1+(n－g)2^g－1－1 when g≥0 and n≥max{g+4,2^g+1－2^－g－g－1}.Also study the upper and lower bounds for the g-extra conditional diagnosability of hypercubes under the symmetric PMC model,the upper bound is 2n(g+1)－5g－2C²_g－2 when n≥4 and 0≤g≤n－4,and the lower bound is$\frac{3}{2} n(g+1)-g-\frac{5}{2} C_{g+1}^{2}-1$ when n≥4 and $0 \leqslant g \leqslant \min \left\{n-4,\left\lfloor\frac{2}{3} n\right\rfloor\right\}$.Finally,the correctness of the relevant theoretical conclusions is verified by simulation experiments.

Key words: Interconnection network, Hypercube, System level diagnosis, Symmetric PMC model, Conditional diagnosability

中图分类号:

TP393

涂远杰, 程宝雷, 王岩, 韩月娟, 樊建席. 超立方体在对称PMC模型下的g-好邻条件诊断度和g-额外条件诊断度[J]. 计算机科学, 2024, 51(9): 103-111. https://doi.org/10.11896/jsjkx.230700007

TU Yuanjie, CHENG Baolei, WANG Yan, HAN Yuejuan, FAN Jianxi. g-Good-Neighbor Conditional Diagnosability and g-Extra Conditional Diagnosability of Hypercubes Under Symmetric PMC Model[J]. Computer Science, 2024, 51(9): 103-111. https://doi.org/10.11896/jsjkx.230700007

参考文献

[1]SAAD Y,SCHULTZ M H.Topological properties of hyper-cubes[J].IEEE Transactions on Computers,1988,37(7):867-872.
[2]CONDON P,DIAZ A E,GIRAO A,et al.Hamiltonicity of random subgraphs of the hypercube[C]//Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms(SODA).Society for Industrial and Applied Mathematics,2021:889-898.
[3]ZHANG S,LIANG D,CHEN L,et al.The component diagno-sability of hypercubes with large-scale faulty nodes[J].The Computer Journal,2022,65(5):1129-1143.
[4]WEI C C,HSIEH S Y.Random and conditional (t,k)-diagnosis of hypercubes[J].Algorithmica,2017,79(3):625-644.
[5]YANG W,MENG J.Extraconnectivity of hypercubes[J].Applied Mathematics Letters,2009,22(6):887-891.
[6]PREPARATA F P,METZE G,CHIEN R T.On the connection assignment problem of diagnosable systems[J].IEEE Transactions on Electronic Computers,1967,EC-16(6):848-854.
[7]MAENG J,MALEK M.A comparison connection assignmentfor self-diagnosis of multiprocessor systems[C]//Proceedings-11th Annual International Symposium on Fault-Tolerant Computing.IEEE Computer Society,1981:173-175.
[8]BARSI F,GRANDONI F,MAESTRINI P.A theory of diagno-sability of digital systems[J].IEEE Transactions on Compu-ters,1976,25(6):585-593.
[9]PENG S L,LIN C K,TAN J J M,et al.The g-good-neighbor conditional diagnosability of hypercube under PMC model[J].Applied Mathematics and Computation,2012,218(21):10406-10412.
[10]DING T,XU M.Relationship between diagnosability and non-inclusive diagnosability of triangle-free connected graphs under the PMC model[J].Theoretical Computer Science,2023,944:113676.
[11]YUAN J,QIAO H,LIU A.The upper and lower bounds of Rg-conditional diagnosability of networks[J].Information Proces-sing Letters,2022,176:106248.
[12]WEI Y,XU M.Conditional diagnosability of Cayley graphs ge-nerated by wheel graphs under the PMC model[J].Theoretical Computer Science,2021,849:163-172.
[13]MA M J,XU M,DING T T,et al.The non-inclusion diagno-sability of hypercubes under the PMC model[J].Journal of the Operations Research Society of China,2022,6:1-7.
[14]ZHU Q,THULASIRAMAN K,NAIK K,et al.Symmetric PMC model of diagnosis,b-matchings in graphs and fault identification in t-diagnosable systems[J].Theoretical Computer Science,2021,891:35-49.
[15]HAKIMI S L,AMIN A T.Characterization of connection as-signment of diagnosable systems[J].IEEE Transactions on Computers,1974,23(1):86-88.
[16]SULLIVAN G.A polynomial time algorithm for fault diagno-sability[C]//IEEE 25th Annual Symposium on Foundations of Computer Science.IEEE Computer Society Press,1984:148-156.
[17]LAI P L,TAN J J M,CHANG C P,et al.Conditional diagnosability measures for large multiprocessor systems[J].IEEE Transactions on Computers,2005,54(2):165-175.
[18]LIU H,HU X,GAO S.The g-good neighbor conditional diagnosability of twisted hypercubes under the PMC and MM* model[J].Applied Mathematics and Computation,2018,332:484-492.
[19]WEI Y L,XU M.The g-good-neighbor conditional diagnosability of locally twisted cubes[J].Journal of the Operations Research Society of China,2018,6(2):333-347.
[20]GUO J,LI D,LU M.The g-good-neighbor conditional diagno-sability of the crossed cubes under the PMC and MM^* model[J].Theoretical Computer Science,2019,755:81-88.
[21]JUN Y,AIXIA L,XUE M,et al.The g-good-neighbor conditional diagnosability of k-ary n-cubes under the PMC model and MM^* model[J].IEEE Transactions on Parallel and Distributed Systems,2014,26(4):1165-1177.
[22]ZHANG S,YANG W.The g-extra conditional diagnosabilityand sequential t/k-diagnosability of hypercubes[J].InternationalJournal of Computer Mathematics,2016,93(3):482-497.
[23]WANG X,HUANG L,SUN Q,et al.The g-extra diagnosability of the balanced hypercube under the PMC and MM^* model[J].The Journal of Supercomputing,2022,78(5):6995-7015.
[24]CHENG E,QIU K,SHEN Z.On the g-extra diagnosability of enhanced hypercubes[J].Theoretical Computer Science,2022,921:6-19.
[25]WANG S,MA X.The g-extra connectivity and diagnosability of crossed cubes[J].Applied Mathematics and Computation,2018,336:60-66.
[26]BONDY J A,MURTY U S R.Graph theory with applications[M].London:Macmillan,1976.
[27]LI X,LIN C K,FAN J,et al.Relationship between extra connectivity and component connectivity in networks[J].The Computer Journal,2021,64(1):38-53.
[28]DAHBURA A T,MASSON G M.An O(n^2.5) fault identification algorithm for diagnosable systems[J].IEEE Transactions on Computers,1984,33(6):486-492.
[29]LEIGHTON F T.Introduction to parallel algorithms and ar-chitectures:arrays. trees. hypercubes[M].San Mateo:Else-vier,1992.
[30]LATIFI S,HEGDE M,NARAGHI-POUR M.Conditional connectivity measures for large multiprocessor systems[J].IEEE Transactions on Computers,1994,43(2):218-222.
[31]OH A D,CHOI H A.Generalized measures of fault tolerance in n-cube networks[J].IEEE Transactions on Parallel and Distri-buted Systems,1993,4(6):702-703.
[32]ZHU Q,XU J M.On restricted edge connectivity and extra edge connectivity of hypercubes and folded hypercubes[J].Journal of University of Science and Technology of China,2006,36(3):249-253.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

超立方体在对称PMC模型下的g-好邻条件诊断度和g-额外条件诊断度

g-Good-Neighbor Conditional Diagnosability and g-Extra Conditional Diagnosability of Hypercubes Under Symmetric PMC Model

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

Metrics

本文评价

推荐阅读 0