Adaptive Diagnosis of Hamiltonian Networks under the Comparison Model
Abstract
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. , A group theoretic model for symmetric interconnection networks, IEEE Transactions on Computers 38(4) (1989) 555–566. Crossref, ISI, Google Scholar
- 2. , Lee distance and topological properties of k-ary n-cubes, IEEE Transactions on Computers 44(8) (1995) 1021–1030. Crossref, ISI, Google Scholar
- 3. , Embedding of cycles in arrangement graphs, IEEE Transactions on Computers 42(8) (1993) 1002–1006. Crossref, ISI, Google Scholar
- 4. , BC interconnection networks and their properties, Chinese Journal of Computers 26(1) (2003) 84–90. Google Scholar
- 5. , Edge-pancyclicity and path-embeddability of bijective connection graphs, Information Sciences 178(2) (2008) 340–351. Crossref, ISI, Google Scholar
- 6. , The t/k-diagnosability of the BC graphs, IEEE Transactions on Computers 54(2) (2005) 176–184. Crossref, ISI, Google Scholar
- 7. , Adaptive system-level diagnosis for hypercube multiprocessors, IEEE Transactions on Computers 45(10) (1996) 1157–1170. Crossref, ISI, Google Scholar
- 8. , Better adaptive diagnosis of hypercubes, IEEE Transactions on Computers 49(10) (2000) 1013–1020. Crossref, ISI, Google Scholar
- 9. , Optimal adaptive diagnosis for simple multiprocessor systems, Networks 34 (1999) 206–214. Crossref, ISI, Google Scholar
- 10. , Adaptive system-level diagnosis for hypercube multiprocessors using a comparison model, Information Sciences 252 (2013) 118–131. Crossref, ISI, Google Scholar
- 11. , Adaptive diagnosis for torus systems under the comparison model, International Journal of Computer Mathematics 89(2) (2012) 146–159. Crossref, ISI, Google Scholar
- 12. , Three round adaptive diagnosis in hierarchical multiprocessor systems, IEEE Transactions on Reliability 62(3) (2013) 608–617. Crossref, ISI, Google Scholar
- 13. , The extra connectivity, extra conditional diagnosability and t/k-diagnosability of the data center network DCell, Theoretical Computer Science 766 (2019) 16–29. Crossref, ISI, Google Scholar
- 14. , Structure connectivity and substructure connectivity of k-ary n-cube networks, Information Sciences 433–434 (2018) 115–124. Crossref, ISI, Google Scholar
- 15. , Edge-fault-tolerant hamiltonicity of folded hypercube, Journal of University of Science and Technology of China 36(3) (2006) 244–248. Google Scholar
- 16. , A comparison connection assignment for diagnosis of multiprocessor systems, Proceedings of the 11th International Fault-Tolerant Computing,
1981 , pp. 173–175. Google Scholar - 17. , A new approach to system diagnosis, in Proceedings of the 19th Allerton Conference Communication, Control and Computing,
1981 , pp. 697–706. Google Scholar - 18. , On adaptive fault diagnosis for multiprocessor systems, in Proceedings of the ISAAC 2001,
LNCS 2223 (2001), pp. 86–98. Google Scholar - 19. , 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. , Adaptive diagnosis of variants of the hypercube, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E88-A(3) (2005) 728–735. Crossref, ISI, Google Scholar
- 21. , On the connection assignment problem of diagnosable systems, IEEE Transactions on Electronic Computers EC-16 (1967) 848–854. Crossref, Google Scholar
- 22. , On self-diagnosable multiprocessor systems: Diagnosis by the comparison approach, IEEE Transactions on Computers 41(11) (1992) 1386–1396. Crossref, ISI, Google Scholar
- 23. , A note about some properties of BC graphs, Information Processing Letters 108 (2008) 398–401. Crossref, ISI, Google Scholar
- 24. , Hamiltonian properties of DCell networks, The Computer Journal 58(11) (2015) 2944–2955. Crossref, ISI, Google Scholar
- 25. , Reliability evaluation of BC networks in terms of the extra vertex- and edge-connectivity, IEEE Transactions on Computers 63(10) (2014) 2540-2548. Crossref, ISI, Google Scholar
- 26. , Five-round adaptive diagnosis in hamiltonian networks, IEEE Transactions on Parallel and Distributed Systems 26(9) (2015) 2459–2464. Crossref, ISI, Google Scholar
- 27. , The t/k-diagnosability of star graph networks, IEEE Transactions Computers 64(2) (2015) 547–555. Crossref, ISI, Google Scholar
- 28. , Reliability evaluation of BC networks, IEEE Transactions on Computers 62(11) (2003) 2337–2340. Crossref, ISI, Google Scholar


