Skip to main content
Springer Nature Link
Log in

Diagnosability for a family of matching composition networks

  • Published:
The Journal of Supercomputing Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8

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

  1. 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

    Article  MATH  Google Scholar 

  2. Bondy JA, Murty USR (2008) Graph theory. Springer, New York

    Book  MATH  Google Scholar 

  3. 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

    Article  Google Scholar 

  4. 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

    Article  MATH  Google Scholar 

  5. Choudum SA, Sunitha V (2002) Augmented cubes. Networks 40(2):71–84

    Article  MathSciNet  MATH  Google Scholar 

  6. 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

    Article  MathSciNet  MATH  Google Scholar 

  7. Cull P, Larson S (1995) The Möbius cubes. IEEE Trans Computers 44(5):647–659. https://doi.org/10.1109/12.381950

    Article  MathSciNet  MATH  Google Scholar 

  8. 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

    Article  MATH  Google Scholar 

  9. 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

  10. 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

    Article  Google Scholar 

  11. 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

    Article  Google Scholar 

  12. 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

    Article  Google Scholar 

  13. Fan J (1998) Diagnosability of crossed cubes under the two strategies. Chinese J Computers 21(5):456–462

    MathSciNet  Google Scholar 

  14. 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

    Article  Google Scholar 

  15. 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

    Article  Google Scholar 

  16. Fan J, He L (1998) BC Interconnection networks and their properties. Chinese J Computers 126(1):84–90

    MathSciNet  Google Scholar 

  17. 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

    Article  Google Scholar 

  18. 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

  19. Hsu L-H, Lin C-K (2009) Graph theory and interconnection networks. CRC Press, USA

    MATH  Google Scholar 

  20. 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

    Article  Google Scholar 

  21. 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

    Article  Google Scholar 

  22. Larson SM, Cull P (1995) The Möbius cubes. IEEE Trans Computers 44(5):647–659. https://doi.org/10.1109/12.381950

    Article  MathSciNet  MATH  Google Scholar 

  23. 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

    Article  Google Scholar 

  24. 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

    Article  Google Scholar 

  25. 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

    Article  Google Scholar 

  26. 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

    Article  Google Scholar 

  27. 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

    Article  MathSciNet  MATH  Google Scholar 

  28. 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

    Article  MathSciNet  MATH  Google Scholar 

  29. 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

    Article  MathSciNet  MATH  Google Scholar 

  30. 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

    Article  Google Scholar 

  31. 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

    Article  MathSciNet  MATH  Google Scholar 

  32. 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

    Article  Google Scholar 

  33. 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

    Article  Google Scholar 

  34. 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

    Article  Google Scholar 

  35. 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

    Article  Google Scholar 

  36. 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

    Article  Google Scholar 

  37. 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

    Article  Google Scholar 

  38. Ma M, Liu G, Xu J-M (2008) The super connectivity of augmented cubes. Inf Process Lett 106(2):59–63

    Article  MathSciNet  MATH  Google Scholar 

  39. Malek M (1980) A comparison connection assignment for diagnosis of multiprocessor systems, In Proceedings of the 7th Annual Symposium on Computer Architecture 31–35

  40. 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

  41. 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

    Article  MathSciNet  MATH  Google Scholar 

  42. 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

    Article  MATH  Google Scholar 

  43. 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

    Article  MathSciNet  MATH  Google Scholar 

  44. Saad Y, Schultz MH (1988) Topological properties of hypercubes. IEEE Trans Computers 37(7):867–872. https://doi.org/10.1109/12.2234

    Article  Google Scholar 

  45. 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

    Article  MathSciNet  MATH  Google Scholar 

  46. Tzeng NF, Wei S (1991) Enhanced hypercubes. IEEE Trans Computers 40:284–294. https://doi.org/10.1109/12.76405

    Article  Google Scholar 

  47. 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

    Article  MathSciNet  MATH  Google Scholar 

  48. Wang D (1994) Diagnosability of enhanced hypercubes. IEEE Trans Computers 43(9):1054–1061. https://doi.org/10.1109/12.312114

    Article  MathSciNet  MATH  Google Scholar 

  49. 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

    Article  MathSciNet  MATH  Google Scholar 

  50. 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

    Article  Google Scholar 

  51. 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

    Article  Google Scholar 

  52. 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

    MATH  Google Scholar 

  53. 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

    Article  MathSciNet  MATH  Google Scholar 

Download references

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

  1. College of Mathematical Science, Tianjin Normal University, Tianjin, China

    Meirun Chen

  2. IRIF, CNRS & Université Paris Cité, Paris, France

    Michel Habib

  3. Department of Computer Science, National Yang Ming Chiao Tung University, Hsinchu, Taiwan

    Cheng-Kuan Lin

Authors
  1. Meirun Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Michel Habib
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Cheng-Kuan Lin
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Cheng-Kuan Lin.

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.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

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

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11227-022-04949-8

Keywords

Search

Navigation