Abstract
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.
Similar content being viewed by others
Data availability
The authors confirm that data sharing is not applicable to this article as no datasets were generated or analyzed during the current study.
References
Armstrong JR, Gray FG (1981) Fault diagnosis in a Boolean \(n\)-cube array of multiprocessors. IEEE Trans Computers 30(8):587–590. https://doi.org/10.1109/TC.1981.1675844
Bondy JA, Murty USR (2008) Graph theory. Springer, New York
Chang G-Y, Chang GJ, Chen G-H (2005) Diagnosabilities of regular networks. IEEE Trans Parallel Distrib Syst 16(4):314–323. https://doi.org/10.1109/TPDS.2005.44
Chen M, Frank Hsu D, Lin C-K (2022) A new structure for a vertex to be locally \(t\)-diagnosabe in large multiprocessor systems. Theor Computer Sci 934:81–90. https://doi.org/10.1016/j.tcs.2022.08.020
Choudum SA, Sunitha V (2002) Augmented cubes. Networks 40(2):71–84
Chwa K-Y, Hakimi SL (1981) Schemes for fault tolerant computing: a comparison of modularly redundant and \(t\)-diagnosable systems. Inf Control 49:212–238. https://doi.org/10.1016/S0019-9958(81)90388-0
Cull P, Larson S (1995) The Möbius cubes. IEEE Trans Computers 44(5):647–659. https://doi.org/10.1109/12.381950
Dahbura AT, Masson GM (1984) An \(O(n^{2.5})\) fault identification algorithm for diagnosable systems. IEEE Trans Computers 33(6):486–492. https://doi.org/10.1109/TC.1984.1676472
Das SK, Banerjee AK (1992) Hyper Petersen network Yet another hypercube-like topology. In Proceedings of the Fourth Symposium on the Frontiers of Massively Parallel Computation 270–277. https://doi.org/10.1109/FMPC.1992.234949
Das SK, Öhring S, Banerjee AK (1995) Embeddings into hyper Petersen networks: Yet another hypercube-like interconnection topology. VLSI Des 2(4):335–351. https://doi.org/10.1155/1995/95759
EI-Awawy A, Latifi S (1991) Properties and performance of folded hypercubes. IEEE Trans Parallel Distrib Syst 2(1):31–42. https://doi.org/10.1109/71.80187
Efe K (1992) The crossed cube architecture for parallel computation. IEEE Trans Parallel Distrib Syst 3(5):513–524. https://doi.org/10.1109/71.159036
Fan J (1998) Diagnosability of crossed cubes under the two strategies. Chinese J Computers 21(5):456–462
Fan J (2002) Diagnosability of crossed cubes under the comparison diagnosis model. IEEE Trans Parallel Distrib Syst 13(7):687–692. https://doi.org/10.1109/TPDS.2002.1019858
Fan J (1998) Diagnosability of the Möbius cubes. IEEE Trans Parallel Distrib Syst 9(9):923–928. https://doi.org/10.1109/71.722224
Fan J, He L (1998) BC Interconnection networks and their properties. Chinese J Computers 126(1):84–90
Fan J, Lin X (2005) The \(t/k\)-diagnosability of the BC graphs. IEEE Trans Computers 54(2):176–184. https://doi.org/10.1109/TC.2005.33
Hilbers PAJ, Koopman MRJ, van de Snepscheut JLA (1987) The twisted cube. In Proceedings of the International PARLE Conference on Parallel Architectures and Languages Europe 258:152–159. https://doi.org/10.1007/3-540-17943-7_126
Hsu L-H, Lin C-K (2009) Graph theory and interconnection networks. CRC Press, USA
Huang Y, Lin L, Hsieh S-Y (2022) A fast \(f(r, k+1)/k\)f(r, k+1)/k-diagnosis for interconnection networks under MM* model. IEEE Trans Parallel Distrib Syst 33(7):1593–1604. https://doi.org/10.1109/TPDS.2021.3122440
Kavianpour A, Kim KH (1991) Diagnosability of hypercube under the pessimistic one-step diagnosis strategy. IEEE Trans Computers 40(2):232–237. https://doi.org/10.1109/12.73595
Larson SM, Cull P (1995) The Möbius cubes. IEEE Trans Computers 44(5):647–659. https://doi.org/10.1109/12.381950
Lee C-W, Hsieh S-Y (2011) Diagnosability of two-matching composition networks under the \(\text{ MM}^*\) model. IEEE Trans Dependable Secure Comput 8(2):246–255. https://doi.org/10.1109/TDSC.2009.52
Lee C-W, Hsieh S-Y (2011) Determining the diagnosability of \((1,2)\)-matching composition networks and its applications. IEEE Trans Dependable Secure Comput 8(3):353–362. https://doi.org/10.1109/TDSC.2010.22
Lai P-L, Tan JJM, Chang C-P, Hsu L-H (2005) Conditional diagnosability measures for large multiprocessor systems. IEEE Trans Computers 54(2):165–175. https://doi.org/10.1109/TC.2005.19
Lai P-L, Tan JJM, Tsai C-H, Hsu L-H (2004) The diagnosability of the matching composition network under the comparison diagnosis model. IEEE Trans Computers 53(8):1064–1069. https://doi.org/10.1109/TC.2004.50
Li X, Teng Y-H, Kung T-L, Chen Q, Lin C-K (2019) The diagnosability and 1-good-neighbor conditional diagnosability of hypercubes with missing links and broken-down nodes. Inf Process Lett 146:20–26. https://doi.org/10.1016/j.ipl.2019.01.007
Lin C-K, Teng Y-H (2014) The diagnosability of triangle-free graphs. Theor Computer Sci 530:58–65. https://doi.org/10.1016/j.tcs.2014.02.024
Lin C-K, Zhang L, Fan J, Wang D (2016) Structure connectivity and substructure connectivity of hypercubes. Theor Computer Sci 634:97–107. https://doi.org/10.1016/j.tcs2016.04.014
Lin L, Zhou S, Xu L, Wang D (2015) The extra connectivity and conditional diagnosability of alternating group networks. IEEE Trans Parallel Distrib Syst 26(8):2352–2362. https://doi.org/10.1109/TPDS.2014.2347961
Lin L, Xu L, Zhou S, Hsieh S-Y (2016) The t/k-diagnosability for regular networks. IEEE Trans Computers 65(10):3157–3170. https://doi.org/10.1109/TC.2015.2512866
Lin L, Hsieh S-Y, Chen R, Xu L, Lee C-W (2018) The relationship between g-restricted connectivity and g-good-neighbor fault diagnosability of general regular networks. IEEE Trans Reliability 67(1):285–296. https://doi.org/10.1109/TC.2015.2512866
Lin L, Huang Y, Xu L, Hsieh S-Y (2021) A complete fault tolerant method for extra fault diagnosability of alternating group graphs. IEEE Trans Reliability 70(3):957–969. https://doi.org/10.1109/TR.2020.3021233
Lin L, Huang Y, Xu L, Hsieh S-Y (2022) A pessimistic fault diagnosability of large-scale connected networks via extra connectivity. IEEE Trans Parallel Distrib Syst 33(2):415–428. https://doi.org/10.1109/TPDS.2021.3093243
Lin L, Huang Y, Lin Y, Hsieh S-Y, Xu L (2022) FFNLFD: Fault diagnosis of multiprocessor systems at local node with fault-free neighbors under PMC model and MM* model. IEEE Trans Parallel Distrib Syst 33(7):1739–1751. https://doi.org/10.1109/TPDS.2021.3126257
Lin L, Xu L, Wang D, Zhou S (2018) The g-good-neighbor conditional diagnosability of arrangement graphs. IEEE Trans Dependable Secure Comput 15(3):542–548. https://doi.org/10.1109/TDSC.2016.2593446
Lin L, Xu L, Chen R, Hsieh S-Y, Wang D (2019) Relating extra connectivity and extra conditional diagnosability in regular networks. IEEE Trans Dependable Secure Comput 16(6):1086–1097. https://doi.org/10.1109/TDSC.2017.2726541
Ma M, Liu G, Xu J-M (2008) The super connectivity of augmented cubes. Inf Process Lett 106(2):59–63
Malek M (1980) A comparison connection assignment for diagnosis of multiprocessor systems, In Proceedings of the 7th Annual Symposium on Computer Architecture 31–35
Maeng J, Malek M (1981) A comparison connection assignment for self-diagnosis of multiprocessor systems, In Proceedings of the 11th International Symposium on Fault-tolerant Computing 173–175
Peng S-L, Lin C-K, Jimmy, Tan JM, Hsu L-H (2012) The \(g\)-good-neighbor conditional diagnosability of hypercube under PMC model. Appl Math Comput 218(21):10406–10412. https://doi.org/10.1016/j.amc.2012.03.092
Preparata FP, Metze G, Chien RT (1967) On the connection assignment problem of diagnosable systems. IEEE Trans Electronic Computers 16(12):848–854. https://doi.org/10.1109/PGEC.1967.264748
Sabir E, Mamut A, Vumar E (2019) The extra connectivity of the enhanced hypercubes. Theor Computer Sci 799:22–31. https://doi.org/10.1016/j.tcs.2019.09.035
Saad Y, Schultz MH (1988) Topological properties of hypercubes. IEEE Trans Computers 37(7):867–872. https://doi.org/10.1109/12.2234
Sengupta A, Dahbura AT (1992) On self-diagnosable multiprocessor systems: diagnosis by the comparison approach. IEEE Trans Computers 41(11):1386–1396. https://doi.org/10.1109/12.177309
Tzeng NF, Wei S (1991) Enhanced hypercubes. IEEE Trans Computers 40:284–294. https://doi.org/10.1109/12.76405
Wang Y, Lin C-K, Li X, Zhou S (2020) Diagnosability for two families of composition networks. Theor Computer Sci 824–825:46–56. https://doi.org/10.1016/j.tcs.2020.04.011
Wang D (1994) Diagnosability of enhanced hypercubes. IEEE Trans Computers 43(9):1054–1061. https://doi.org/10.1109/12.312114
Wang D (1999) Diagnosability of hypercubes and enhanced hypercubes under the comparison diagnosis model. IEEE Trans Computers 48(12):1369–1374. https://doi.org/10.1109/12.817401
Wang G, Lin C-K, Fan J, Cheng B, Jia X (2020) A novel low cost interconnection architecture based on the generalized hypercube. IEEE Trans Parallel Distrib Syst 31(3):647–662. https://doi.org/10.1109/TPDS.2019.2941207
Xu L, Lin L, Zhou S, Hsieh S-Y (2016) The extra connectivity, extra conditional diagnosability, and t/m-diagnosability of arrangement graphs. IEEE Trans Reliability 65(3):1248–1262. https://doi.org/10.1109/TR.2016.2570559
Xu JM, Zhu Q, Hou XM, Zhou T (2005) On restricted connecetivity and extra connectivity of hypercubes and folded hypercubes. J Shanghai Jiaotong Univ (Sci) 10(2):208–212
Zhou S, Lin L, Xu L, Wang D (2015) The t/k-diagnosability of star graph networks. IEEE Trans Computers 64(2):547–555. https://doi.org/10.1109/TC.2013.228
Acknowledgements
This work was supported by the National Natural Science Foundation of China (No. 61872257), by the Fujian Provincial Department of Science and Technology (2020J01268).The authors wish to thank the referees for their helpful comments.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors have no conflict of interest.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Chen, M., Habib, M. & Lin, CK. Diagnosability for a family of matching composition networks. J Supercomput 79, 7584–7608 (2023). https://doi.org/10.1007/s11227-022-04949-8
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11227-022-04949-8