×

Hybrid fault diagnosis capability analysis of hypercubes under the PMC model and \(\mathrm{MM}^\ast\) model. (English) Zbl 1410.68063

Summary: System level diagnosis is an important approach for the fault diagnosis of multiprocessor systems. In system level diagnosis, diagnosability is an important measure of the diagnosis capability of interconnection networks. But as a measure, diagnosability can not reflect the diagnosis capability of multiprocessor systems to link faults which may occur in real circumstances. In this paper, we propose the definition of \(h\)-edge tolerable diagnosability to better measure the diagnosis capability of interconnection networks under hybrid fault circumstances. The \(h\)-edge tolerable diagnosability of a multiprocessor system \(G\) is the maximum number of faulty nodes that the system can guarantee to locate when the number of faulty edges does not exceed \(h\), denoted by \(t_h^e(G)\). The PMC model and MM model are the two most widely studied diagnosis models for the system level diagnosis of multiprocessor systems. The hypercubes are the most well-known interconnection networks. In this paper, the \(h\)-edge tolerable diagnosability of \(n\)-dimensional hypercube under the PMC and \(\mathrm{MM}^\ast\) model is determined as follows: \(t_h^e(Q_n) = n - h\), where \(1 \leq h < n\), \(n \geq 4\).

MSC:

68M15 Reliability, testing and fault tolerance of networks and computer systems
68M10 Network design and communication in computer systems
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] 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
[2] Maeng, J.; Malek, M., A comparison connection assignment for self-diagnosis of multiprocessor systems, (Symposium on Fault-tolerant Computing, (1981))
[3] 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
[4] Chang, G. Y.; Chang, G. J.; Chen, G. H., Diagnosabilities of regular networks, IEEE Trans. Parallel Distrib. Syst., 16, 4, 314-323, (2005)
[5] Chang, G. Y.; Chen, G. H.; Chang, G. J., \((t, k)\)-diagnosis for matching composition networks under the \(\text{MM}^\ast\) model, IEEE Trans. Comput., 56, 1, 73-79, (2007) · Zbl 1388.68017
[6] Hsieh, S. Y.; Lee, C. W., Diagnosability of two-matching composition networks, (International Conference on Computing and Combinatorics, (2008)), 478-486 · Zbl 1148.68317
[7] Lee, C. W.; Hsieh, S. Y., Diagnosability of component-composition graphs in the \(\text{MM}^\ast\) model, ACM Transact. Des. Automat. Electron. Syst., 19, 3, 3902-3912, (2014)
[8] Hsieh, S. Y.; Lee, C. W., Diagnosability of two-matching composition networks under the \(\text{MM}^\ast\) model, IEEE Transact. Dependable Secure Comput., 8, 2, 246-255, (2011)
[9] Yang, M. C., Conditional diagnosability of balanced hypercubes under the \(\text{MM}^\ast\) model, J. Supercomput., 65, 3, 1264-1278, (2013)
[10] Chiang, C. F.; Hsu, G. H.; Shih, L. M.; Tan, J. J.M., Diagnosability of star graphs with missing edges, Inform. Sci., 188, 253-259, (2012) · Zbl 1257.68042
[11] Yang, M. C., Conditional diagnosability of matching composition networks under the \(\text{MM}^\ast\) model, Inform. Sci., 233, 233, 230-243, (2013) · Zbl 1284.68083
[12] Zhang, S.; Yang, W., The g-extra conditional diagnosability and sequential \(t / k\)-diagnosability of hypercubes, Int. J. Comput. Math., 93, 3, 1-20, (2015)
[13] Han, W.; Wang, S., The g-extra conditional diagnosability of folded hypercubes, Appl. Math. Sci., 9, 146, 7247-7254, (2015)
[14] Wang, S.; Wang, Z.; Wang, M., The 2-extra connectivity and 2-extra diagnosability of bubble-sort star graph networks, Comput. J., (2016)
[15] Wei, C. C.; Chen, C. A.; Hsieh, S. Y., Conditional \((t, k)\)-diagnosis in regular and irregular graphs under the comparison diagnosis model, IEEE Transact. Dependable Secure Comput., 15, 2, 351-356, (2018)
[16] Wang, D., Diagnosability of enhanced hypercubes, IEEE Trans. Comput., 43, 9, 1054-1061, (1994) · Zbl 1061.68507
[17] Fan, J., Diagnosability of the Mobius cubes, IEEE Trans. Parallel Distrib. Syst., 9, 9, 923-928, (1998)
[18] Wang, D., Diagnosability of hypercubes and enhanced hypercubes under the comparison diagnosis model, IEEE Trans. Comput., 48, 12, 1369-1374, (1999) · Zbl 1392.68061
[19] Fan, J., Diagnosability of crossed cubes under the comparison diagnosis model, IEEE Trans. Parallel Distrib. Syst., 13, 10, 1099-1104, (2002)
[20] Lai, P. L.; Tan, J. J.M.; Tsai, C. H.; Hsu, L. H., The diagnosability of the matching composition network under the comparison diagnosis model, IEEE Trans. Comput., 53, 8, 1064-1069, (2004)
[21] Zheng, J.; Latifi, S.; Regentova, E.; Luo, K.; Wu, X., Diagnosability of star graphs under the comparison diagnosis model, Inform. Process. Lett., 93, 1, 29-36, (2005) · Zbl 1173.68615
[22] Zhou, S.; Xu, J. M., Fault diagnosability of arrangement graphs, Inform. Sci., 246, 177-190, (2013) · Zbl 1337.68215
[23] 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
[24] 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)
[25] Hsu, G. H.; Chiang, C. F.; Shih, L. M.; Hsu, L. H.; Tan, J. J.M., Conditional diagnosability of hypercubes under the comparison diagnosis model, J. Syst. Archit., 55, 2, 140-146, (2009)
[26] Hong, W. S.; Hsieh, S. Y., Strong diagnosability and conditional diagnosability of augmented cubes under the comparison diagnosis model, IEEE Trans. Reliab., 61, 1, 140-148, (2012)
[27] Hsieh, S. Y.; Kao, C. Y., The conditional diagnosability of k-ary n-cubes under the comparison diagnosis model, IEEE Trans. Comput., 62, 4, 839-843, (2013) · Zbl 1365.68085
[28] 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
[29] Li, X.; Yang, X.; He, L.; Zhang, J.; Yu, C., Conditional diagnosability of optical multi-mesh hypercube networks under the comparison diagnosis model, Theoret. Comput. Sci., 531, 47-53, (2014) · Zbl 1359.68029
[30] Lin, L.; Zhou, S.; Xu, L.; Wang, D., The extra connectivity and conditional diagnosability of alternating group networks, IEEE Trans. Parallel Distrib. Syst., 26, 8, 2352-2362, (2015)
[31] Zhu, Q.; Liu, S. Y.; Xu, M., On conditional diagnosability of the folded hypercubes, Inform. Sci., 178, 4, 1069-1077, (2008) · Zbl 1134.68014
[32] Zhu, Q., On conditional diagnosability and reliability of the BC networks, J. Supercomput., 45, 2, 173-184, (2008)
[33] Chang, N. W.; Hsieh, S. Y., Conditional diagnosability of augmented cubes under the PMC model, IEEE Transact. Dependable Secure Comput., 9, 1, 46-60, (2012)
[34] Chang, N.; Cheng, E.; Hsieh, S., Conditional diagnosability of Cayley graphs generated by transposition trees under the PMC model, ACM Transact. Des. Automat. Electron. Syst., 20, 2, 1-16, (2015)
[35] Chang, N. W.; Hsieh, S. Y., Conditional diagnosability of \((n, k)\)-star graphs under the PMC model, IEEE Transact. Dependable Secure Comput., 15, 2, 207-216, (2018)
[36] Lin, L.; Hsieh, S. Y.; Xu, L.; Zhou, S.; Chen, R., The relationship between extra connectivity and conditional diagnosability of regular graphs under the PMC model, J. Comput. System Sci., 95, 1-18, (2018) · Zbl 1390.68506
[37] 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
[38] Xu, L.; Lin, L.; Zhou, S.; Hsieh, S. Y., The extra connectivity, extra conditional diagnosability, and \(t / m\)-diagnosability of arrangement graphs, IEEE Trans. Reliab., 65, 3, 1248-1262, (2016)
[39] Yang, C.; Masson, G., Hybrid fault diagnosability with unreliable communication links, IEEE Trans. Comput., 37, 2, 175-181, (1988)
[40] Wang, D., The diagnosability of hypercubes with arbitrarily missing links, J. Syst. Archit., 46, 6, 519-527, (2000)
[41] Zheng, S.; Zhou, S., Diagnosability of the incomplete star graphs, Tsinghua Sci. Technol., 12, 105-109, (2007) · Zbl 1174.68472
[42] Xu, J., Theory and Application of Graphs, (2013), Springer Publishing Company, Incorporated
[43] Dahbura, A. T.; Masson, G. M., An \(0(n^{2.5})\) fault identification algorithm for diagnosable systems, IEEE Trans. Comput., C-33, 6, 486-492, (1984) · Zbl 0537.68043
[44] Zhu, Q.; Xu, J. M., On restricted edge connectivity and extra edge connectivity of hypercubes and folded hypercubes, J. Univ. Sci. Technol. China, 36, 3, 249-253, (2006) · Zbl 1259.05106
[45] Yang, X.; Cao, J.; Megson, G.; Luo, J., Minimum neighborhood in a generalized cube, Inform. Process. Lett., 97, 3, 88-93, (2006) · Zbl 1181.68045
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.