A tree structure for local diagnosis in multiprocessor systems under the comparison model. (English) Zbl 07813019
Summary: Diagnosability is an important indicator to measure the reliability of multiprocessor systems. If we focus on the status of a particular node, instead of doing global diagnosis, Hsu and Tan introduced the concept of local diagnosis and proposed an extended star structure to diagnose a node under the comparison model. Usually, there is a gap between the local diagnosability and the lower bound guaranteed by the extended star structure mentioned above. In this paper, we propose a new testing structure and a corresponding diagnosis algorithm to diagnose a node under the comparison model and better evaluate the local diagnosability. The local diagnosability of a node is upper bounded by its degree in the system. If the local diagnosability of each node equals to its degree in the system, then we say this system has the strong local diagnosability property. Based on the new structure, we provide two sufficient conditions for a multiprocessor system to have the strong local diagnosability property. As applications, we show that the \(n\)-dimensional star graph \(S_n\) and pancake graph \(P_n\) with faulty links have the strong local diagnosability property no matter how many edges are faulty, provided that each node connects to at least three fault-free links. Moreover, we show that \(S_n\) and \(P_n\) keep the strong local diagnosability property even if they have up to \(3n - 12\) faulty links, assuming that each node connects to at least two fault-free links. Simulations are presented to show the performance of our tree structure.
MSC:
| 68Qxx | Theory of computing |
References:
| [1] | Akers, S. B.; Krishnameurthy, B., Group-theoretic model for symmetric interconnection networks, IEEE Trans. Comput., 38, 4, 555-566, 1989 · Zbl 0678.94026 |
| [2] | Bondy, J. A.; Murty, U. S.R., Graph Theory, 2008, Springer: Springer New York · Zbl 1134.05001 |
| [3] | Chang, N.-W.; Wu, H.-J.; Hsieh, S.-Y., Pancake graphs: structural properties and conditional diagnosability, J. Comb. Optim., 44, 5, 3263-3293, 2022 · Zbl 07610128 |
| [4] | Chang, N.-W.; Hsieh, S.-Y., Conditional diagnosability of alternating group networks under the PMC model, IEEE/ACM Trans. Netw., 28, 5, 1968-1980, 2020 |
| [5] | Chang, N.-W.; Hsieh, S.-Y., Conditional diagnosability of \((n, k)\)-star graphs under the PMC model, IEEE Trans. Dependable Secure Comput., 15, 2, 207-216, 2018 |
| [6] | Chang, N.-W.; Deng, W.-H.; Hsieh, S.-Y., Conditional diagnosability of \((n, k)\)-star networks under the comparison diagnosis model, IEEE Trans. Reliab., 64, 1, 132-143, 2015 |
| [7] | Chen, M.; Frank Hsu, D.; Lin, C.-K., A new structure for a vertex to be locally t-diagnosable in large multiprocessor systems, Theor. Comput. Sci., 934, 81-90, 2022 · Zbl 1537.68018 |
| [8] | Chen, M.; Habib, M.; Lin, C.-K., Diagnosability for a family of matching composition networks, J. Supercomput., 79, 7, 7584-7608, 2023 |
| [9] | Chiang, C.-F.; Hsu, G.-H.; Shih, L.-M.; Tan, J. J.M., Diagnosability of star graphs with missing edges, Inf. Sci., 188, 253-259, 2012 · Zbl 1257.68042 |
| [10] | Chiang, C.-F.; Tan, J. J.M., Using node diagnosability to determine t-diagnosability under the comparison diagnosis model, IEEE Trans. Comput., 58, 1, 251-259, 2009 · Zbl 1368.68071 |
| [11] | Gates, W. H.; Papadimitriou, C. H., Bounds for sorting by prefix reversal, Discrete Math., 27, 47-49, 1979 |
| [12] | Hsieh, S.-Y.; Lee, C.-W., Diagnosability of two-matching composition networks under the MM^⁎ model, IEEE Trans. Dependable Secure Comput., 8, 2, 246-255, 2011 |
| [13] | Hsieh, S.-Y.; Tsai, C.-Y.; Chen, C.-A., Strong diagnosability and conditional diagnosability of multiprocessor systems and folded hypercubes, IEEE Trans. Comput., 62, 7, 1472-1477, 2013 · Zbl 1365.94699 |
| [14] | Hsu, G.-H.; Tan, J. J.M., A local diagnosability measure for multiprocessor systems, IEEE Trans. Parallel Distrib. Syst., 18, 598-607, 2007 |
| [15] | Hsu, L.-H.; Lin, C.-K., Graph Theory and Interconnection Networks, 2009, CRC Press · Zbl 1168.05002 |
| [16] | Lin, C.-K.; Teng, Y.-H.; Tan, J. J.M.; Hsu, L.-H., Local diagnosis algorithms for multiprocessor systems under the comparison diagnosis model, IEEE Trans. Reliab., 62, 4, 800-810, 2013 |
| [17] | Konstantinova, E. V.; Medvedev, A. N., Cycles for length seven in the Pancake graphs, Diskretn. Anal. Issled. Oper., 17, 46-55, 2010, (in Russian) · Zbl 1249.05207 |
| [18] | Konstantinova, E. V.; Medvedev, A. N., Small cycles in the star graph, Sib. Electron. Math. Rep., 11, 906-914, 2014 · Zbl 1326.05062 |
| [19] | Lai, P.-L.; Tan, J. J.M.; Chang, C.-P.; Hsu, L.-H., Conditional diagnosability measures for large multiprocessor systems, IEEE Trans. Comput., 54, 2, 165-175, 2005 |
| [20] | Lee, C.-W.; Hsieh, S.-Y., Determining the diagnosability of \((1, 2)\)-matching composition networks and its applications, IEEE Trans. Dependable Secure Comput., 8, 3, 353-362, 2011 |
| [21] | Li, P.; Xu, M., The \(t / k\)-diagnosability and strong Menger connectivity on star graphs with conditional faults, Theor. Comput. Sci., 793, 181-192, 2019 · Zbl 1434.68051 |
| [22] | Lin, C.-K.; Teng, Y.-H., The diagnosability of triangle-free graphs, Theor. Comput. Sci., 530, 58-65, 2014 · Zbl 1359.68030 |
| [23] | Liu, W.; Lin, C.-K., Diagnosability and diagnostic algorithm for Pancake graph under the Comparison model, J. Interconnect. Netw., 15, Article 1550005 pp., 2015 |
| [24] | Maeng, J.; Malek, M., A comparison connection assignment for diagnosis of multiprocessor systems, (Proceedings of the 11th International Symposium on Fault-Tolerant Computing, 1981), 173-175 |
| [25] | Malek, M., A comparison connection assignment for diagnosis of multiprocessor systems, (Proceedings of the 7th Annual Symposium on Computer Architecture, 1980), 31-35 |
| [26] | Peng, S.-L.; Lin, C.-K.; Tan, J. J.M.; Hsu, L.-H., The g-good-neighbor conditional diagnosability of hypercube under PMC model, Appl. Math. Comput., 218, 21, 10406-10412, 2012 · Zbl 1247.68032 |
| [27] | Preparata, F. P.; Metze, G.; Chien, R. T., On the connection assignment problem of diagnosable systems, IEEE Trans. Electron. Comput., 16, 12, 848-854, 1967 · Zbl 0189.16904 |
| [28] | Ren, Y.; Wang, S., Local diagnosability of bipartite graphs with conditional faulty edges under Preparata, Metze and Chien’s model, Discrete Appl. Math., 322, 286-294, 2022 · Zbl 07600642 |
| [29] | Sengupta, A.; Dahbura, A. T., On self-diagnosable multiprocessor systems: diagnosis by the comparison approach, IEEE Trans. Comput., 41, 11, 1386-1396, 1992 · Zbl 1395.68062 |
| [30] | Wei, Y.; Xu, M., On g-good-neighbor conditional diagnosability of \((n, k)\)-star networks, Theor. Comput. Sci., 697, 79-90, 2017 · Zbl 1379.68025 |
| [31] | Xu, M.; Thulasiraman, K.; Hu, X. D., Conditional diagnosability of matching composition networks under the PMC model, IEEE Trans. Circuits Syst. II, Express Briefs, 56, 11, 875-879, 2009 |
| [32] | Xu, M.; Thulasiraman, K.; Zhu, Q., Conditional diagnosability of a class of matching composition networks under the comparison model, Theor. Comput. Sci., 674, 43-52, 2017 · Zbl 1369.68063 |
| [33] | Yuan, J.; Liu, A. X.; Ma, X.; Qin, X.; Zhang, J., The g-good-neighbor conditional diagnosability of k-ary n-cubes under the PMC model and MM^⁎ model, IEEE Trans. Parallel Distrib. Syst., 26, 4, 1165-1177, 2015 |
| [34] | Zhou, S., The conditional fault diagnosability of \((n, k)\)-star graphs, Appl. Math. Comput., 218, 19, 9742-9749, 2012 · Zbl 1245.05122 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
