The diagnosability of interconnection networks. (English) Zbl 07919044
Summary: Diagnosability is a fundamental consideration when designing an interconnected network. The PMC and MM\(^\ast\) fault diagnosis models are the two most commonly used models. Both the \(g\)-good-neighbour diagnosability and \(g\)-extra diagnosability of an interconnection network have been two of the hot topics in the intersectional research areas of Graph theory and Computer Science, which become increasingly attractive for new solutions to real-world problems. However, there are still some problems in the transformation from the concepts of Computer Science to that of mathematics. In this paper, we systematically study such problems and give a strict proof from concepts to mathematical conclusions. In the terms of results, we not only give the relationship between \(g\)-good-neighbour diagnosabilities of the network under PMC model and MM\(^\ast\) model, but also between \(g\)-extra diagnosabilities of the network under PMC and MM\(^\ast\) models. To apply our results, we give an application on the enhanced hypercube in the end and derive a lemma explaining whether these are 3-cycles in enhanced hypercubes and how many common neighbours for two vertices of enhanced hypercubes under different values of \(k\) in the meantime.
MSC:
| 68Mxx | Computer system organization |
| 68Rxx | Discrete mathematics in relation to computer science |
| 05Cxx | Graph theory |
Keywords:
interconnection networks; graph; connectivity; diagnosability; \(g\)-good-neighbour; enhanced hypercubeReferences:
| [1] | Barsi, F.; Grandoni, F.; Maestrini, P., A theory of diagnosability of digital systems, IEEE Trans. Comput., 25, 6, 585-593, 1976 · Zbl 0331.94008 |
| [2] | Bondy, J. A.; Murty, U. S.R., Graph Theory, 2007, Springer: Springer New York · Zbl 1134.05001 |
| [3] | 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 |
| [4] | Chiang, C.-F.; Tan, J. J.M., Using node diagnosability to determine \(t\)-diagnosability under the comparison diagnosis model, IEEE Trans. Comput., 58, 2, 251-259, 2009 · Zbl 1368.68071 |
| [5] | Chwa, K. Y.; Hakimi, S. L., Schemes for fault-tolerant computing: A comparison of modularly redundant and \(t\)-diagnosable systems, Inf. Control, 49, 212-238, 1981 · Zbl 0486.94022 |
| [6] | Dahbura, A. T.; Masson, G. M., An \(O ( n^{2 . 5} )\) fault identification algorithm for diagnosable systems, IEEE Trans. Comput., 33, 6, 486-492, 1984 · Zbl 0537.68043 |
| [7] | Fan, J., Diagnosability of crossed cubes under the comparison diagnosis model, IEEE Trans. Parallel Distrib. Syst., 13, 10, 1099-1104, 2002 |
| [8] | Fan, J.; Lin, X., The t/k-diagnosability of the BC graphs, IEEE Trans. Comput., 54, 2, 176-184, 2005 |
| [9] | Fan, W., An efficient algorithm for embedding exchanged hypercubes into grids, J. Supercomput., 75, 2, 783-807, 2019 |
| [10] | A.D. Friedman, A new measure of digital system diagnosis, in: Digest of the International Sympsium on Fault Tolerant Computing, 1975, pp. 167-170. |
| [11] | Hsieh, S.-Y.; Kao, C.-Y., The conditional diagnosability of \(k\)-ary \(n\)-ubes under the comparison diagnosis model, IEEE Trans. Comput., 62, 839-843, 2013 · Zbl 1365.68085 |
| [12] | Hu, X.; Yang, W.; Tian, Y.; Meng, J., Equal relation between g-good-neighbor diagnosability under the PMC model and g-good-neighbor diagnosability under the MM \({}^\ast\) model of a graph, Discrete Appl. Math., 262, 96-103, 2019 · Zbl 1411.05242 |
| [13] | Jirimutu, J.; Wang, S., The 1-good-neighbor diagnosability of alternating group graph networks under the PMC model and MM* model, Recent Patents Comput. Sci., 10, 2, 108-115, 2017 |
| [14] | Lai, P. L.; Tan, J. J.; Chang, C. P., Conditional diagnosability measures for large multiprocessor systems, IEEE Trans. Comput., 54, 2, 165-175, 2005 |
| [15] | 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 |
| [16] | Latifi, S.; Hegde, M.; Naraghi-pour, M., Conditional connectivity measures for large multiprocessor systems, IEEE Trans. Comput., 43, 218-222, 1994 |
| [17] | Maeng, J.; Malek, M., A comparison connection assignment for self-diagnosis of multiprocessor systems, (Proceeding of 11th International Symposium on Fault-Tolerant Computing, 1981, ACM Press: ACM Press New York), 173-175 |
| [18] | Malek, Miroslaw, A comparison connection assignment for diagnosis of multiprocessor systems, (Proceedings of the 7th Annual Symposium on Computer Architecture, 1982, ACM Press: ACM Press New York), 31-36 |
| [19] | Peng, S. L.; Lin, C. K.; Tan, J. J., The \(g\)-good-neighbour conditional diagnosability of hypercube under PMC model, Appl. Math. Comput., 218, 21, 10406-10412, 2012 · Zbl 1247.68032 |
| [20] | Preparata, F. P.; Metze, G.; Chien, R. T., On the connection assignment problem of diagnosable systems, IEEE Trans. Electron. Comput., 16, 6, 848-854, 1967 · Zbl 0189.16904 |
| [21] | Ren, Y.; Wang, S., Some properties of the g-good-neighbor (g-extra) diagnosability of a multiprocessor system, Am. J. Comput. Math., 6, 3, 259-266, 2016 |
| [22] | Ren, Y.; Wang, S., The g-good-neighbor diagnosability of locally twisted cubes, Theoret. Comput. Sci., 697, 91-97, 2017 · Zbl 1379.68024 |
| [23] | Saad, Y.; Schultz, M. H., Topological properties of hypercubes, IEEE Trans. Comput., 37, 867-872, 1988 |
| [24] | Somani, A. K.; Peleg, O., On diagnosability of large fault sets in regular topology-based computer systems, IEEE Trans. Comput., 45, 8, 892-903, 1996 · Zbl 1057.68535 |
| [25] | Tzeng, N. F.; Wei, S., Enhanced hypercubes, IEEE Trans. Comput., 40, 03, 284-294, 1991 |
| [26] | Wang, M.; Guo, Y.; Wang, S., The 1-good-neighbour diagnosability of Cayley graphs generated by transposition trees under the PMC model and MM \({}^\ast\) model, Int. J. Comput. Math., 94, 1-4, 620-631, 2017 · Zbl 1362.05062 |
| [27] | Wang, S.; Han, W., The \(g\)-good-neighbour conditional diagnosability of n-dimensional hypercubes under the MM \({}^\ast\) model, Inform. Process. Lett., 116, 9, 574-577, 2016 · Zbl 1357.68016 |
| [28] | Wang, S.; Ma, X., The g-extra connectivity and diagnosability of crossed cubes, Appl. Math. Comput., 336, 60-66, 2018 · Zbl 1427.68028 |
| [29] | Wang, S.; Ren, Y., The \(h\)-extra connectivity and diagnosability of locally twisted cubes, IEEE Access, 7, Article 102113-102118, 2019 |
| [30] | Wang, S.; Wang, M., The \(g\)-good-neighbour and \(g\)-extra diagnosability of networks, Theoret. Comput. Sci., 773, 107-114, 2019 · Zbl 1422.68013 |
| [31] | Wang, S.; Wang, Z.; Wang, M., The 2-extra connectivity and 2-extra diagnosability of bubble-sort star graph networks, Comput. J., 59, 12, 1839-1856, 2016 |
| [32] | Wei, Y.; Xu, M., The 1 2-good-neighbor conditional diagnosabilities of regular graphs, Appl. Math. Comput., 334, 295-310, 2018 · Zbl 1427.68029 |
| [33] | Yu, H.; Yang, J.; Lin, L.; Huang, Y.; Li, J.; Chen, R., {1, 2 3}-Restricted connectivity of-enhanced hypercubes, Comput. J., 63, 9, 1355-1371, 2020 |
| [34] | Zhang, S.; Yang, W., The \(g\)-extra conditional diagnosability and sequential \(t / k\)-diagnosability of hypercubes, Int. J. Comput. Math., 93, 3, 482-497, 2016 · Zbl 1358.68047 |
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.
