有遗失边的n维超立方体和折叠超立方体在MM*模型下的诊断度
Diagnosability of n-Dimensional Hypercubes and Folded Hypercubes with Missing Edges under the MM* Model
DOI: 10.12677/AAM.2021.101018, PDF,  被引量    国家自然科学基金支持
作者: 樊畅畅, 王世英*, 马晓蕾：河南师范大学，数学与信息科学学院，河南 新乡
关键词: 互连网络；局部诊断度；n维超立方体；n维折叠超立方体；MM*模型；Interconnection Networks； Local Diagnosability； n-Dimensional Hypercubes； n-Dimensional Folded Hypercubes； MM* Model
摘要: 一个多重处理器系统的诊断度是测量互连网络错误容忍度的一个重要研究参数。n维折叠超立方体FQn是由n维超立方体Qn添加2n-1条边得到。在这篇文章中，我们首先研究了Qn在MM*模型下的诊断度，证明了Qn即使存在n-2条遗失边仍具有强局部诊断性，并且证明了n-2是最优值。然后，我们研究了FQn在MM*模型下的诊断度，证明了FQn即使存在n-1条遗失边仍具有强局部诊断性，并且证明了n-1是最优值。
Abstract: Diagnosability of a multiprocessor system is an important research parameter to measure the fault tolerance of interconnection networks. The n-dimensional folded hypercube FQn is obtained by adding 2n-1 edges to the n-dimensional hypercube Qn. In this paper, we firstly study the diagnosability of Qn and prove that Qn has the strong local diagnosability property even if there exist n-2 missing edges in it under the MM* model and the result is optimal with respect to the number of missing edges. Then we study the diagnosability of FQn and prove that FQn has the strong local diagnosability property even if there exist n-1 missing edges in it under the MM* model and the result is optimal with respect to the number of missing edges.
文章引用：樊畅畅, 王世英, 马晓蕾. 有遗失边的n维超立方体和折叠超立方体在MM*模型下的诊断度[J]. 应用数学进展, 2021, 10(1): 150-159. https://doi.org/10.12677/AAM.2021.101018

参考文献

[1] Maeng, J. and Malek, M. (1981) A Comparison Connection Assignment for Self-Diagnosis of Multiprocessors Systems. Proceeding of the 11th International Symposium on Fault-Tolerant Computing, Vol. 11, 173-175.
[2] Sengupta, A. and Dahbura, A. (1992) On Self-Diagnosable Multiprocessor Systems: Diagnosis by the Comparison Approach. IEEE Transactions on Computers, 41, 1386-1396. [Google Scholar] [CrossRef] 
[3] Fan, J.X. (2002) Diagnosability of Crossed Cubes under the Comparison Diagnosis Model. IEEE Transactions on Parallel and Distributed Systems, 13, 1099-1104. [Google Scholar] [CrossRef] 
[4] Gu, M.-M., Hao, R.-X., Feng, Y.-Q. and Yu, A.-M. (2018) The 3-Extra Connectivity and Faulty Diagnosability. The Computer Journal, 61, 672-686. [Google Scholar] [CrossRef] 
[5] Gu, M.-M., Hao, R.-X. and Zhou, S.M. (2019) Fault Diagnosability of Data Center Networks. Theoretical Computer Science, 776, 138-147. [Google Scholar] [CrossRef] 
[6] Lai, P.-L., Tan, J.J.M., Chang, C.-P. and Hsu, L.-H. (2005) Conditional Diagnosability Measures for Large Multiprocessor Systems. IEEE Transactions on Computers, 54, 165-175. [Google Scholar] [CrossRef] 
[7] Hsu, G.-H. and Tan, J.J.M. (2007) A Local Diagnosability Measure for Multiprocessor Systems. IEEE Transactions on Parallel and Distributed Systems, 18, 598-607. [Google Scholar] [CrossRef] 
[8] Chiang, C.-F. and Tan, J.J.M. (2009) Using Node Diagnosability to Determine t-Diagnosability under the Comparison Diagnosis Model. IEEE Transactions on Computers, 58, 251-259. [Google Scholar] [CrossRef] 
[9] Chiang, C.-F., Hsu, G.-H., Shih, L.-M. and Tan, J.J.M. (2012) Diagnosability of Star Graphs with Missing Edges. Information Sciences, 188, 253-259. [Google Scholar] [CrossRef] 
[10] Cheng, E. and Liptak, L. (2013) Diagnosability of Cayley Graphs Generated by Transposition Trees with Missing Edges. Information Sciences, 238, 250-252. [Google Scholar] [CrossRef] 
[11] Cheng, E., Liptak, L. and Steffy, D.E. (2013) Strong Local Diagnosability of (n,k)-Star Graphs and Cayley Graphs Generated by 2-Trees with Missing Edges. Information Processing Letters, 113, 452-456. [Google Scholar] [CrossRef] 
[12] Wang, S.Y. and Ma, X.L. (2018) Diagnosability of Alternating Group Graphs with Missing Edges. Recent Advances Electrical and Electronic Engineering, 11, 51-57. [Google Scholar] [CrossRef] 
[13] Ren, Y.X. and Wang, S.Y. (2020) Diagnosability of the Cayley Graph Generated by Complete Graph with Missing Edges under the MM* Model. The Computer Journal, 63, 1438-1447. [Google Scholar] [CrossRef] 
[14] Wang, S.Y. and Ma, X.L. (2020) Diagnosability of Arrangement Graphs with Missing Edges under the MM* Model. International Journal of Parallel, Emergent and Distributed Systems, 35, 69-80. [Google Scholar] [CrossRef] 
[15] Zhou, Z.P., Wang, S.Y., Ma, X.L. and Ren, Y.X. (2020) Diagnosability of Expanded k-Ary n-Cubes with Missing Edges under the Comparison Model. International Journal of Parallel, Emergent and Distributed Systems, 35, 16-28. [Google Scholar] [CrossRef] 
[16] El-Amawy, A. and Latifi, S. (1991) Properties and Performance of Folded Hypercubes. IEEE Transactions on Parallel and Distributed Systems, 2, 31-42. [Google Scholar] [CrossRef] 
[17] Bondy, J.A. and Murty, U.S.R. (2007) Graph Theory. Springer, New York. [Google Scholar] [CrossRef] 
[18] Dahbura, A.T. and Masson, G.M. (1984) An Fault Identification Algorithm for Diagnosable Systems. IEEE Transactions on Computers, 33, 486-492. [Google Scholar] [CrossRef] 
[19] Saad, Y. and Schultz, M.H. (1988) Topological Properties of Hypercubes. IEEE Transactions on Computers, 37, 867-872. [Google Scholar] [CrossRef] 

为你推荐