The \(g\)-good-neighbor conditional diagnosabilities of hypermesh optical interconnection networks under the PMC and comparison models. (English) Zbl 07837625
Summary: Processor fault diagnosis is intended to identify faulty processors of a multicomputer system, guaranteeing its high reliability and availability. The \(g\)-good-neighbor conditional diagnosability is a novel fault diagnosis method for various networks. Under the PMC model and comparison model, the \(g\)-good-neighbor conditional diagnosabilities of hypermesh optical interconnection networks are determined, respectively. Directly applying the results, the \(g\)-good-neighbor conditional diagnosabilities of hypercubes are derived under the PMC and comparison models.
MSC:
| 68Mxx | Computer system organization |
| 68Rxx | Discrete mathematics in relation to computer science |
| 05Cxx | Graph theory |
Keywords:
\(g\)-good-neighbor conditional diagnosability; hypermesh optical interconnection networks; PMC model; comparison model; conditional diagnosabilityReferences:
| [1] | Bondy, J. A. and Murty, U. S. R., Graph Theory, Springer, New York, 2008. · Zbl 1134.05001 |
| [2] | Chang, N. W., Lin, T. Y. and Hsieh, S. Y., Conditional diagnosability of \(k\)-ary \(n\)-cubes under the PMC Model, ACM Trans. Design Automation of Electronic Systems17 (2012), Article 46. |
| [3] | Cheng, E., Qiu, K. and Shen, Z., On the conditional diagnosability of matching composition networks, Theoret. Comput. Sci.557 (6)(2014) 101-114. · Zbl 1338.68028 |
| [4] | Cheng, E., Qiu, K. and Shen, Z., A general approach to deriving the \(g\)-good-neighbor conditional diagnosability of interconnection networks, Theoret. Comput. Sci.757(24) (2019) 56-67. · Zbl 1410.68060 |
| [5] | Fan, J., Diagnosability of crossed cubes under the comparison diagnosis model, IEEE Trans. Parallel Distrib. Syst.13(7) (2002) 687-692. |
| [6] | Guo, J., Li, D. and Lu, M., The \(g\)-good-neighbor conditional diagnosability of the crossed cubes under the PMC and MM* model, Theoret. Comput. Sci.75510 (2019) 81-88. · Zbl 1411.68023 |
| [7] | Hsieh, S. Y., Tsai, C. Y. and Chen, C. A., Strong diagnosability and conditional diagnosability of multiprocessor systems and folded hypercubes, IEEE Trans. Comput.62 (2013) 1472-1477. · Zbl 1365.94699 |
| [8] | Lai, P. L., Tan, J. J. M., Chang, C. P. and Hsu, L. H., Conditional diagnosability measures for large multiprocessor systems, IEEE Trans. Comput.54 (2005) 165-175. |
| [9] | Li, X., Yang, X. and He, L., Diagnosability of optical multi-mesh hypercube networks under the comparison diagnosis model, Int. J. Comput. Math.90(9) (2013) 1774-1781. · Zbl 1312.68027 |
| [10] | Li, X., Strong diagnosability and conditional diagnosability of optical multi-mesh hypercube networks under the PMC model, Int. J. Comput. Math.93(12) (2016) 2054-2063. · Zbl 1404.68026 |
| [11] | Li, X., Yang, X., He, L., Yu, C. and Zhang, J., Conditional fault tolerance of hypermesh optical interconnection networks, Int. J. Found. Comput. S.26(1) (2015) 159-168. · Zbl 1312.68028 |
| [12] | Li, X., Yang, X., He, L., Zhang, J. and Yu, C., Conditional diagnosability of optical multi-mesh hypercube networks under the comparison diagnosis model, Theoret. Comput. Sci.531 (2014) 47-53. · Zbl 1359.68029 |
| [13] | Li, D. and Lu, M., The \(g\)-good-neighbor conditional diagnosability of star graphs under the PMC and MM* model, Theoret. Comput. Sci.674 (2017) 53-59. · Zbl 1370.68034 |
| [14] | Li, X. Y., Fan, J. X., Lin, C.-K and Jia, X. H., Diagnosability evaluation of the data center network DCell, Comput. J.61(1) (2018) 129-143. |
| [15] | Liu, H., Hu, X. and Gao, S., The \(g\)-good-neighbor conditional diagnosability of twisted hypercubes under the PMC and MM* model, Appl. Math. Comput.3321 (2018) 484-492. · Zbl 1427.05185 |
| [16] | Liu, X., Yang, X. and Xiang, M., One-step \(t\)-fault diagnosis for hypermesh optical interconnection multiprocessor systems, J. Syst. Softw.82 (2009) 1491-1496. |
| [17] | Loucif, S., Ould-Khaoua, M. and Al-Ayyoub, A., Hypermeshes: Implementation and performance, J. Syst. Architect.48 (2002) 37-47. |
| [18] | Maeng, J. and Malek, M., A comparison connection assignment for self-diagnosis of multiprocessors systems, Proc. \(11\) th Int. Symp. Fault-Tolerant Comput. Los Alamitos, CA, USA, , 1981, 173-175. |
| [19] | Malek, M., A comparison connection assignment for diagnosis of multiprocessor systems, Proc. Seventh Int. Symp. Computer Architecture, La Baule, France, , 1980, 31-36. |
| [20] | Moraveji, R., Sarbazi-Azad, H., Nayebi, A. and Navi, K., Modeling the effects of hot-spot traffic load on the performance of wormhole-switched hypermeshes, Comput. Electr. Engin.37 (2011) 1-23. · Zbl 1214.68103 |
| [21] | Peng, S. L., Lin, C. K., Tan, J. J. M. and Hsu, L. H., The \(g\)-good-neighbor conditional diagnosability of hypercube under PMC model, Appl. Math. Comput.218 (2012) 10406-10412. · Zbl 1247.68032 |
| [22] | Preparata, F. P., Metze, G. and Chien, R. T., On the connection assignment problem of diagnosable systems, IEEE Trans. Electron. Comput.16 (1967) 848-854. · Zbl 0189.16904 |
| [23] | Ren, Y. X. and Wang, S. Y., The \(g\)-good-neighbor diagnosability of locally twisted cube, Theoret. Comput. Sci.697 (2017) 91-97. · Zbl 1379.68024 |
| [24] | Sengupta, A. and Dahbura, A. T., On self-diagnosable multiprocessor systems: Diagnosis by the comparison approach, IEEE Trans. Comput.41 (1992) 1386-1396. · Zbl 1395.68062 |
| [25] | Tsai, C. H. and Chen, J. C., Fault isolation and identification in general biswapped networks under the PMC diagnostic model, Theoret. Comput. Sci.501 (2013) 62-71. · Zbl 1296.68020 |
| [26] | Wang, S. and Han, W., The \(g\)-good-neighbor conditional diagnosability of \(n\)-dimensional hypercubes under the MM* model, Inf. Process. Lett.116 (2016) 574-577. · Zbl 1357.68016 |
| [27] | Wang, M., Lin, Y. and Wang, S., The 2-good-neighbor diagnosability of Cayley graphs generated by transposition trees under the PMC model and MM* model, Theoret. Comput. Sci.628 (2016) 92-100. · Zbl 1338.68036 |
| [28] | Wang, S. Y. and Wang, Z. H., \(g\)-good-neighbor conditional diagnosability of star graph networks under PMC model and MM* model, Front. Math. China12(5) (2017) 1221-1234. · Zbl 1378.05194 |
| [29] | Wang, S. and Wang, M., The \(g\)-good neighbor and \(g\)-extra diagnosability of networks, Theoret. Comput. Sci.773 (2019) 107-114. · Zbl 1422.68013 |
| [30] | Wei, Y. L. and Xu, M., On \(g\)-good-neighbor conditional diagnosability of \((n,k)\)-star networks, Theoret. Comput. Sci.697 (2017) 79-90. · Zbl 1379.68025 |
| [31] | Wu, J. and Guo, G., Fault tolerance measures for \(m\)-ary \(n\)-dimensional hypercubes based in forbidden faulty sets, IEEE Trans. Comput.47 (1998) 888-893. · Zbl 0894.68001 |
| [32] | Xu, X., Li, X. W., Zhou, S. M., Hao, R. X. and Gu, M. M., The \(g\)-good-neighbor diagnosability of \((n,k)\)-star graphs, Theoret. Comput. Sci.659 (2017) 53-63. · Zbl 1355.68027 |
| [33] | Yang, E., Yang, X., Dong, Q. and Li, J., Conditional diagnosability of hypermesh optical multiprocessor systems under the PMC model, Int. J. Comput. Math.88 (2011) 2275-2284. · Zbl 1230.68047 |
| [34] | Yang, E., Yang, X., Dong, Q. and Li, J., Conditional diagnosability of hypermeshes under the comparison model, Inf. Process. Lett.111 (2011) 188-193. · Zbl 1260.68026 |
| [35] | Yuan, J., Liu, A., Qin, X., Zhang, J. and Li, J., \(g\)-Good-neighbor conditional diagnosability measures for 3-ary \(n\)-cube networks, Theoret. Comput. Sci.626 (2016) 144-162. · Zbl 1336.68018 |
| [36] | Yuan, J., Liu, A., Ma, X., Liu, X., Qin, X. and 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 (2015) 1165-1177. |
| [37] | Zhou, M., Li, Y., Tahir, M. J., Gong, X., Wang, Y. and He, W., Integrated statistical test of signal distributions and access point contributions for Wi-Fi indoor localization, IEEE Trans. on Veh. Technol.70(5) (2021) 5057-5070. |
| [38] | Zhou, S., Song, S., Yang, X. and Chen, L., On conditional fault tolerance and diagnosability of hierarchical cubic networks, Theoret. Comput. Sci.609 (2016) 421-433. · Zbl 1331.68035 |
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.
