World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

Adaptive Diagnosis of Hamiltonian Networks under the Comparison Model

    Adaptive diagnosis is an approach in which tests can be scheduled dynamically during the diagnosis process based on the previous test outcomes. Naturally, reducing the number of test rounds as well as the total number of tests is a major goal of an efficient adaptive diagnosis algorithm. The adaptive diagnosis of multiprocessor systems under the PMC model has been widely investigated, while adaptive diagnosis using comparison model has been independently discussed only for three networks, including hypercube, torus, and completely connected networks. In addition, adaptive diagnosis of general Hamiltonian networks is more meaningful than that of special graph. In this paper, the problem of adaptive fault diagnosis in Hamiltonian networks under the comparison model is explored. First, we propose an adaptive diagnostic scheme which takes five to six test rounds. Second, we derive a dynamic upper bound of the number of fault nodes instead of setting a value like normal. Finally, we present an algorithm such that at least one sequence obtained from cycle partition can be picked out and all nodes in this sequence can be identified based on the previous upper bound.

    Communicated by Ke Qiu

    References

    • 1. S. B. Akers and B. Krishnamurthy, A group theoretic model for symmetric interconnection networks, IEEE Transactions on Computers 38(4) (1989) 555–566. Crossref, ISIGoogle Scholar
    • 2. B. Bose, B. Broeg, Y. Kwon, Y. Ashir, Lee distance and topological properties of k-ary n-cubes, IEEE Transactions on Computers 44(8) (1995) 1021–1030. Crossref, ISIGoogle Scholar
    • 3. K. Day, A. Tripathi, Embedding of cycles in arrangement graphs, IEEE Transactions on Computers 42(8) (1993) 1002–1006. Crossref, ISIGoogle Scholar
    • 4. J. Fan, L. He, BC interconnection networks and their properties, Chinese Journal of Computers 26(1) (2003) 84–90. Google Scholar
    • 5. J. Fan, X. Jia, Edge-pancyclicity and path-embeddability of bijective connection graphs, Information Sciences 178(2) (2008) 340–351. Crossref, ISIGoogle Scholar
    • 6. J. Fan, X. Lin, The t/k-diagnosability of the BC graphs, IEEE Transactions on Computers 54(2) (2005) 176–184. Crossref, ISIGoogle Scholar
    • 7. C. Feng, L. N. Bhuyan, F. Lombardi, Adaptive system-level diagnosis for hypercube multiprocessors, IEEE Transactions on Computers 45(10) (1996) 1157–1170. Crossref, ISIGoogle Scholar
    • 8. E. Kranakis, A. Pelc, Better adaptive diagnosis of hypercubes, IEEE Transactions on Computers 49(10) (2000) 1013–1020. Crossref, ISIGoogle Scholar
    • 9. E. Kranakis, A. Pelc, A. Spatharis, Optimal adaptive diagnosis for simple multiprocessor systems, Networks 34 (1999) 206–214. Crossref, ISIGoogle Scholar
    • 10. P.-L. Lai, Adaptive system-level diagnosis for hypercube multiprocessors using a comparison model, Information Sciences 252 (2013) 118–131. Crossref, ISIGoogle Scholar
    • 11. P.-L. Lai, Adaptive diagnosis for torus systems under the comparison model, International Journal of Computer Mathematics 89(2) (2012) 146–159. Crossref, ISIGoogle Scholar
    • 12. P.-L. Lai, M.-Y. Chiu, C.-H. Tsai, Three round adaptive diagnosis in hierarchical multiprocessor systems, IEEE Transactions on Reliability 62(3) (2013) 608–617. Crossref, ISIGoogle Scholar
    • 13. X. Li, J. Fan, C.-K. Lin, B. Cheng, X. Jia, The extra connectivity, extra conditional diagnosability and t/k-diagnosability of the data center network DCell, Theoretical Computer Science 766 (2019) 16–29. Crossref, ISIGoogle Scholar
    • 14. Y. Lv, J. Fan, D. F. Hsu, C.-K. Lin, Structure connectivity and substructure connectivity of k-ary n-cube networks, Information Sciences 433–434 (2018) 115–124. Crossref, ISIGoogle Scholar
    • 15. M. Ma, J.-M. Xu, Z. Du, Edge-fault-tolerant hamiltonicity of folded hypercube, Journal of University of Science and Technology of China 36(3) (2006) 244–248. Google Scholar
    • 16. M. Maeng, M. Malek, A comparison connection assignment for diagnosis of multiprocessor systems, Proceedings of the 11th International Fault-Tolerant Computing, 1981, pp. 173–175. Google Scholar
    • 17. K. Nakajima, A new approach to system diagnosis, in Proceedings of the 19th Allerton Conference Communication, Control and Computing, 1981, pp. 697–706. Google Scholar
    • 18. K. Nakajima, T. Yoshida, S. Ueno, On adaptive fault diagnosis for multiprocessor systems, in Proceedings of the ISAAC 2001, LNCS 2223 (2001), pp. 86–98. Google Scholar
    • 19. A. Okashita, T. Araki, Y. Shibata, An optimal adaptive diagnosis of butterfly networks, Transactions on Fundamentals of Electronics, Communications and Computer Sciences E86-A(5) (2003) 1008–1018. Google Scholar
    • 20. A. Okashita, T. Araki, Y. Shibata, Adaptive diagnosis of variants of the hypercube, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E88-A(3) (2005) 728–735. Crossref, ISIGoogle Scholar
    • 21. F. P. Preparata, G. Metze, R. T. Chien, On the connection assignment problem of diagnosable systems, IEEE Transactions on Electronic Computers EC-16 (1967) 848–854. CrossrefGoogle Scholar
    • 22. A. Sengupta, A. T. Dahbura, On self-diagnosable multiprocessor systems: Diagnosis by the comparison approach, IEEE Transactions on Computers 41(11) (1992) 1386–1396. Crossref, ISIGoogle Scholar
    • 23. X. Tan, S.-Z. Yu, J. H. Park, A note about some properties of BC graphs, Information Processing Letters 108 (2008) 398–401. Crossref, ISIGoogle Scholar
    • 24. X. Wang, A. Erickson, J. Fan, X. Jia, Hamiltonian properties of DCell networks, The Computer Journal 58(11) (2015) 2944–2955. Crossref, ISIGoogle Scholar
    • 25. W. Yang, H. Lin, Reliability evaluation of BC networks in terms of the extra vertex- and edge-connectivity, IEEE Transactions on Computers 63(10) (2014) 2540-2548. Crossref, ISIGoogle Scholar
    • 26. L.-C. Ye, J.-R. Liang, Five-round adaptive diagnosis in hamiltonian networks, IEEE Transactions on Parallel and Distributed Systems 26(9) (2015) 2459–2464. Crossref, ISIGoogle Scholar
    • 27. S. Zhou, L. Lin, L. Xu, D. Wang, The t/k-diagnosability of star graph networks, IEEE Transactions Computers 64(2) (2015) 547–555. Crossref, ISIGoogle Scholar
    • 28. Q. Zhu, X.-K. Wang, G. Cheng, Reliability evaluation of BC networks, IEEE Transactions on Computers 62(11) (2003) 2337–2340. Crossref, ISIGoogle Scholar