A Local Diagnosis Algorithm for Hypercube-like Networks under the BGM Diagnosis Model

• Autorzy: Lin Cheng-Kuan , Kung Tzu-Liang , Chun-Nan Hung , Yuan-Hsiang Teng

Identyfikatory

DOI

10.3233/FI-222114

• Języki publikacji: EN

Abstrakty

EN

System diagnosis is process of identifying faulty nodes in a system. An efficient diagnosis is crucial for a multiprocessor system. The BGM diagnosis model is a modification of the PMC diagnosis model, which is a test-based diagnosis. In this paper, we present a specific structure and propose an algorithm for diagnosing a node in a system under the BGM model. We also give a polynomial-time algorithm that a node in a hypercube-like network can be diagnosed correctly in three test rounds under the BGM diagnosis model.

Słowa kluczowe

EN

system diagnosis; diagnosability; local diagnosis; BGM model; hypercube-like network

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2022
• Tom: Vol. 185, nr 4
• Strony: 357--373
• Opis fizyczny: Bibliogr. 44 poz., tab.

Twórcy

autor

Lin Cheng-Kuan

• Department of Computer Science, National Yang Ming Chiao Tung University, Hsinchu City, Taiwan

autor

Kung Tzu-Liang

• Department of Computer Science and Information Engineering, Asia University, Taichung City, Taiwan .

autor

Chun-Nan Hung

• Department of Information Management Da-Yeh University Changhua, Taiwan

autor

Yuan-Hsiang Teng

• Department of Computer Science and Information Engineering, Providence University Taichung City, Taiwan

Bibliografia

• [1] Intanagonwiwat C, Govindan R, Estrin D. Directed diffusion: A scalable and robust communication paradigm for sensor networks, Proceedings of the 6th Annual ACM/IEEE International Conference on Mobile Computing and Networking (MOBICOM), 2000, p. 56-67. doi:10.1145/345910.345920.
• [2] Kung TL, Hung CN, Teng YH, Hung JY, Hsu LH. On the robust approach to data inconsistency detection of sensor networks, 10th International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing (IMIS), 2016. doi:10.1109/IMIS.2016.71.
• [3] Hsieh SY, Chuang TY. The strong diagnosability of regular networks and product networks under the PMC model, IEEE Transactions on Parallel and Distributed Systems, 2009. 20:367-378. doi:10.1109/TPDS.2008.99.
• [4] Hsu LH, Lin CK. Graph Theory and Interconnection Networks, CRC Press, 2008. ISBN-13: 9781420044812.
• [5] Lin CK, Teng YH. The diagnosability of triangle-free graphs, Theoretical Computer Science, 2014. 530:58-65. doi:10.1016/j.tcs.2014.02.024.
• [6] Chang NW, Hsieh SY. Structural properties and conditional diagnosability of star graphs by using the PMC model, IEEE Transactions on Parallel and Distributed Systems, 2014. 25(11):3002-3011. doi:10.1109/TPDS.2013.290.
• [7] Lin L, Zhou S, Xu L, Wang D. The extra connectivity and conditional diagnosability of alternating group networks, IEEE Transactions on Parallel and Distributed Systems, 2015. 26(8):2352-2362. doi:10.1109/TPDS.2014.2347961.
• [8] Teng YH, Lin CK. A test round controllable local diagnosis algorithm under the PMC diagnosis model, Applied Mathematics and Computation, 2014. 244:613-623. doi:10.1016/j.amc.2014.07.036.
• [9] Li D, Lu M. The g-good-neighbor conditional diagnosability of star graphs under the PMC and MM∗ model, Theoretical Computer Science, 2017. 674(C):53-59. doi:10.1016/j.tcs.2017.02.011.
• [10] Zhu Q, Li L, Liu S, Zhang X. Hybrid fault diagnosis capability analysis of hypercubes under the PMC model and MM∗ model, Theoretical Computer Science, 2019. 758:1-8. doi:10.1016/j.tcs.2018.07.019.
• [11] Lin CK, Kung TL, Wang D, Teng YH. The diagnosability of (K4 − {e})-free graphs under the PMC diagnosis model, Fundamenta Informaticae, 2020. 177(2):181-188. doi:10.3233/FI-2020-1985.
• [12] Barsi F, Grandoni F, Maestrini P. A theory of diagnosability of digital systems, IEEE Transactions on Computers, 1976. C-25(6):585-593. doi:10.1109/TC.1976.1674658.
• [13] Preparata FP, Metze G, Chien RT. On the connection assignment problem of diagnosis systems, IEEE Transactions on Electronic Computers, 1976. EC-16(6):848-854. doi:10.1109/PGEC.1967.264748.
• [14] Albini LCP, Chessa S, Maestrini P. Diagnosis of symmetric graphs under the BGM model, The Computer Journal, 2004. 47(1):85-92. doi:10.1093/comjnl/47.1.85.
• [15] Blough DM, Brown HW. The broadcast comparison model for on-line fault diagnosis in multicomputer systems: theory and implementation, IEEE Transactions on Computers, 1999. 48(5):470-493. doi:10.1109/12.769431.
• [16] Vedeshenkov VA. On the BGM model-based diagnosis of failed modules and communication lines in digital systems, Automation and Remote Control, 2002. 63(2):316-327. doi:10.1023/A:1014259927555.
• [17] Leighton FT. Introduction to parallel algorithms and architectures: arrays, trees, hypercubes, Morgan Kaufmann, San Mateo, CA, 1992.
• [18] Abraham S, Padmanabhan K. The twisted cube topology for multiprocessors: a study in network asymmetry, Journal of Parallel and Distributed Computing, 1991. 13(1):104-110. doi:10.1016/0743-7315(91)90113-N.
• [19] Cull P, Larson SM. The Möbius cubes, IEEE Transactions on Computers, 1995. 44(5):647-659. doi:10.1109/12.381950.
• [20] Efe K. A variation on the hypercube with lower diameter, IEEE Transactions on Computers, 1991. 40(11):1312-1316. doi:10.1109/12.102840.
• [21] Efe K. The crossed cube architecture for parallel computing, IEEE Transactions on Parallel and Distributed Systems, 1992. 3(5):513-524. doi:10.1109/71.159036.
• [22] Vaidya AS, Rao PSN, Shankar SR. A class of hypercube-like networks, in: Proceedings of the Fifth IEEE Symposium on Parallel and Distributed Processing, IEEE Computer Society Press, Los Alamitos, CA, 1993, pp. 800-803. doi:10.1109/SPDP.1993.395450.
• [23] Hsu JH and Lin CK. Graph Theory and Interconnection Networks, CRC Press, 2008. ISBN-9780367386771.
• [24] Hsu GH, Tan JJM. A local diagnosability measure for multiprocessor systems, IEEE Transactions on Parallel Distributed System, 2007. 18(5):598-607. doi:10.1109/TPDS.2007.1022.
• [25] Chiang CF, Hsu GH, Shih LM, Tan JJM. Diagnosability of star graphs with missing edges, Information Sciences, 2012. 188:253-259. doi:10.1016/j.ins.2011.11.012.
• [26] Cheng E, Lipták L, Steffy DE. Strong local diagnosability of (n, k)-star graphs and Cayley graphs generated by 2-trees with missing edges, Information Processing Letters, 2013. 113(12):452-456. doi: 10.1016/j.ipl.2013.03.002.
• [27] Lin CK, Teng YH, Tan JJM, Hsu LH. Local diagnosis algorithms for multiprocessor systems under the comparison diagnosis model, IEEE Transactions on Reliability, 2013. 62(4):800-810. doi:10.1109/TR.2013.2285031.
• [28] Wang S, Ma X. Diagnosability of alternating group graphs with missing edges, Recent Advances in Electrical and Electronic Engineering, 2018. 11(1):51-57. doi:10.2174/2352096510666171107155511.
• [29] Fan J and Lin X. The t/k–diagnosability of the BC graphs, IEEE Transactions on Computers, 2005. 54(2):176-184. doi:10.1109/TC.2005.33.
• [30] Lai PL, Tan JJM, Chang CP, Hsu LH. Conditional diagnosability measures for large multiprocessor systems, IEEE Transactions on Computers, 2005. 54(2):165-175. doi:10.1109/TC.2005.19.
• [31] Edmonds J. Paths, trees and flowers, Canadian Journal of Mathematics, 1965. 17:449-467. doi:10.4153/CJM-1965-045-4.
• [32] Chang GY, Chang GJ, Chen GH. Diagnosabilities of regular networks, IEEE Transactions on Parallel and Distributed Systems, 2005. 16:314-323. doi:10.1109/TPDS.2005.44.
• [33] Chang NW, Hsieh SY. Conditional diagnosability of augmented cubes under the PMC model, IEEE Transactions on Dependable and Secure Computing, 2010. 9:46-60. doi:10.1109/TDSC.2010.59.
• 34] Chang NW, Hsieh SY. Structural properties and conditional diagnosability of star graphs by using the PMC model, IEEE Transactions on Parallel and Distributed Systems, 2014. 25:3002-3011. doi:10.1109/TPDS.2013.290.
• [35] Dahbura AT, Masson GM. An O(n2.5) fault identification algorithm for diagnosable systems, IEEE Transactions on Computers, 1984. 33:486-492. doi:10.1109/TC.1984.1676472.
• [36] Hakimi SL, Amin AT. Characterization of connection assignment of diagnosable systems, IEEE Transactions on Computers, 1974. 23:86-88. doi:10.1109/T-C.1974.223782.
• [37] Hsieh SY, Chuang TY. The strong diagnosability of regular networks and product networks under the PMC model, IEEE Transactions on Parallel and Distributed Systems, 2009. 20:367-378. doi:10.1109/TPDS.2008.99.
• [38] Hsu LH, Lin CK. Graph Theory and Interconnection Networks, CRC Press, 2008. ISBN-13: 9781420044812.
• [39] Lin CK, Teng YH. The diagnosability of triangle-free graphs, Theoretical Computer Science, 2014. 530:58-65. doi:10.1016/j.tcs.2014.02.024.
• [40] Lin L, Zhou S, Xu L, Wang D. The extra connectivity and conditional diagnosability of alternating group networks, IEEE Transactions on Parallel and Distributed Systems, 2015. 26:2352-2362. doi:10.1109/TPDS.2014.2347961.
• [41] Preparata FP, Metze G, Chien RT. On the connection assignment problem of diagnosis systems, IEEE Transactions on Electronic Computers, 1967. 16:848-854. doi:10.1109/PGEC.1967.264748.
• [42] Teng YH, Lin CK. A test round controllable local diagnosis algorithm under the PMC diagnosis model, Applied Mathematics and Computation, 2014. 244:613-623. doi:10.1016/j.amc.2014.07.036.
• [43] Yuan J, Liu A, Ma X, Liu X. The g-good-neighbor conditional diagnosability of k-ary n-cubes under the PMC model and MM model, IEEE Transactions on Parallel and Distributed Systems, 2015. 26:1165-1177. doi:10.1109/TPDS.2014.2318305.
• [44] Zhou S, Lin L, Xu L, Wang D. The t/k-diagnosability of star graph networks, IEEE Transactions on Computers, 2015. 64:547—-555. doi:10.1109/TC.2013.228.

Uwagi

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023). (PL)