×

On the \(t/k\)-diagnosability of BC networks. (English) Zbl 1334.68031

Summary: To increase the degree of the diagnosability of a system under system-level diagnosis strategies, Somani and Peleg introduced a measure, so called \(t/k\)-diagnosis strategy, in which the identified fault-set is allowed to contain at most \( k\) fault-free processors. Using this diagnosis strategy, the degree of diagnosability of the BC graphs (include hypercubes, crossed cubes, Möbius cubes, and twisted cubes, etc. as the subfamily) increases greatly as the number of the fault-free processors in the fault-set increases for \(1\leqslant k\leqslant n\). In this paper, we extend the result in [X. Lin, “The \(t/k\)-diagnosability of the BC graphs”, IEEE Trans. Comput. 54, No. 2, 176–184 (2005; doi:10.1109/TC.2005.33)] on the \(t/k\)-diagnosability of BC graphs for \(1\leqslant k\leqslant n\) by showing that every \( n\)-dimensional BC graph is \(t(n,k)/k\)-diagnosable when \(n\geqslant 5\) and \(n+1\leqslant k\leqslant 2n-1\), where \(t(n,k)=-\frac{1}{2}(k+1)^2+(2n-\frac{3}{2})(k+1)-(n^2-2)\) for \(n+1\leqslant k\leqslant 2n-1\). The result implies the crossed cube, the Möbius cube, the twisted cube and the hypercube have the same \(t/k\)-diagnosability.

MSC:

68M15 Reliability, testing and fault tolerance of networks and computer systems
Full Text: DOI

References:

[1] Allan, F. J.; Kameda, T.; Toida, S., An approach to the diagnosabilitv analysis of a system, IEEE Trans. Comput., 24, 1040-1042 (1975) · Zbl 0323.94017
[2] Cull, P.; Larson, S., The möbius cubes, IEEE Trans. Comput., 44, 647-659 (1995) · Zbl 1041.68522
[3] Efe, K., A variation on the hypercube with lower diameter, IEEE Trans. Comput., 40, 1312-1316 (1991)
[4] Fan, J.; Jia, X., Edge-pancyclicity and path-embeddability of bijective connection graphs, Inf. Sci., 178, 340-351 (2008) · Zbl 1128.68075
[5] Fan, J.; Jia, X.; Cheng, B.; Yu, J., An efficient fault-tolerant routing algorithm in bijective connection networks with restricted faulty edges, Theor. Comput. Sci., 412, 3440-3450 (2011) · Zbl 1216.68055
[6] Fan, J.; Lin, X., The t/k-diagnosability of the BC graphs, IEEE Trans. Comput., 54, 176-184 (2005)
[7] Fan, J.; Jia, X.; Lin, X., Embedding of cycles in twisted cubes with edge-pancyclic, Algorithmica, 51, 264-282 (2008) · Zbl 1203.68023
[8] Fan, J.; Lin, X.; Jia, X.; Lau, R. W.H., Edge-pancyclicity of twisted cubes, Lect. Notes Comput. Sci., 3827, 1090-1099 (2005) · Zbl 1175.68291
[9] Fan, J.; Jia, X.; Liu, X.; Zhang, S.; Yu, J., Efficient unicast in bijective connection networks with the restricted faulty node set, Inf. Sci., 181, 2303-2315 (2011) · Zbl 1216.68056
[11] Hakimi, S. L.; Amin, A. T., Characterization of connection assignment of diagnosable systems, IEEE Trans. Comput., 23, 86-88 (1974) · Zbl 0278.94018
[12] Hibers, P. A.J.; Koopman, M. R.J.; Snepscheut, J. V.D., The twisted cube, (Proceedings of the Conference on Parallel Architectures and Languages Europe. Proceedings of the Conference on Parallel Architectures and Languages Europe, Lecture Notes in Computer Science (1987), Springer), pp. 152-159
[13] Hung, H.; Fu, J.; Chen, G., Fault-free Hamiltonian cycles in crossed cubes with conditional link faults, Inf. Sci., 177, 5664-5674 (2007) · Zbl 1132.68018
[14] Lai, P.; Tan, J.; Chang, C.; Hsu, L., Conditional diagnosability measures for large multiprocessor systems, IEEE Trans. Comput., 54, 165-175 (2005)
[15] Latifi, S.; Hegde, M.; Naraghi-Pour, M., Conditional connectivity measures for large multiprocessor systems, IEEE Trans. Comput., 43, 218-222 (1994)
[16] Li, T.-K.; Tsai, C.-H.; Hsu, H.-C., A fast fault-identification algorithm for bijective connection graphs using the PMC model, Inf. Sci., 187, 291-297 (2012) · Zbl 1284.68081
[17] Preparata, F. P.; Metze, G.; Chien, R. T., On the connection assignment problem of diagnosable systems, IEEE Trans. Electron. Comput., 16, 848-854 (1967) · Zbl 0189.16904
[18] Somani, A. K.; Peleg, O., On diagnosability of large fault sets in regular topology-based computer systems, IEEE Trans. Comput., 45, 892-903 (1996) · Zbl 1057.68535
[19] Tan, X.; Yu, S.-Z.; Park, J.-H., A note about some properties of BC graphs, Inf. Process. Lett., 108, 398-401 (2008) · Zbl 1191.68474
[20] Yang, M., Conditional diagnosability of balanced hypercubes under the PMC model, Inf. Sci., 222, 754-760 (2013) · Zbl 1293.68037
[21] Yang, X.; Cao, J.; Megson, M.; Luo, J., Minimum neighborhood in a generalized cube, Inf. Process. Lett., 97, 88-93 (2006) · Zbl 1181.68045
[22] Yang, X.; Megson, M.; Cao, J.; Luo, J., A lower bound on the size of k-neighborhood in generalized cubes, Appl. Math. Comput., 179, 47-54 (2006) · Zbl 1110.68115
[23] Yang, X.; Tang, Y., A \((4 n - 9) / 3\)-diagnosis algorithm on n-dimensional cube network, Inf. Sci., 177, 1771-1781 (2007) · Zbl 1116.68018
[25] Zhu, Q.; Wang, X.; Cheng, G., Reliability evaluation of BC networks, IEEE Trans. Comput. (2012)
[26] Zhu, Q., On conditional diagnosability and reliability of the BC networks, J. Supercomputing, 45, 173-184 (2008)
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.