|
|
MM*模型下网络的限制局部可诊断性
|
Abstract:
故障诊断对提升大规模网络可靠性意义重大。实际应用中，往往无需全局诊断，仅需确定信息传输区域内特定顶点(处理器)的工作状态。为此提出局部诊断方法，即设计包含特定顶点v的子网络，通过分析该子网络基于诊断模型得到的症状判断v是否故障。为保障故障网络局部连通性，引入h-限制故障模型，该模型要求移除所有故障顶点后网络的每个连通分量所含顶点数大于h。基于此，进一步提出h-限制局部可诊断性的概念，并给出在MM*模型下估计顶点v的限制局部可诊断性的充分条件，同时设计了包含顶点v的子网络结构
。
Fault diagnosis is crucial for improving the reliability of large-scale networks. In practice, it is often unnecessary to diagnose the entire network. Instead, determining the operational status of speci？c vertices (processors) within a particular information transmission region is more important. To address this, we propose a local diagnosis method that constructs a sub-network containing a speci？c vertex v. By analyzing the symptoms of this sub-network under a given diagnosis model, we can determine whether v is faulty. To ensure local network connectivity in the presence of faults, we introduce the h-extra fault model. This model requires that after removing all faulty vertices, each connected component of the network must have more than h vertices. Based on this, we further introduce the concept of h-extra local diagnosability. We provide sufficient conditions for estimating the extra local diagnosability of a vertex v under the MM* model and design a sub-network structure
that includes vertex v.
| [1] | Dahbura, A.T. and Masson, G.M. (1984) An 0(n2.5) Fault Identification Algorithm for Diagnosable Systems. IEEE Transactions on Computers, 33, 486-492. https://doi.org/10.1109/tc.1984.1676472 |
| [2] | Preparata, F.P., Metze, G. and Chien, R.T. (1967) On the Connection Assignment Problem of Diagnosable Systems. IEEE Transactions on Electronic Computers, 16, 848-854. https://doi.org/10.1109/pgec.1967.264748 |
| [3] | Maeng, J. and Malek, M. (1981) A Comparison Connection Assignment for Self-Diagnosis of Multiprocessor Systems. In: Proceeding of the 11th International Symposium on Fault-Tolerant Computing, ACM Press, 173-175. |
| [4] | Sengupta, A. and Dahbura, A.T. (1992) On Self-Diagnosable Multiprocessor Systems: Diagnosis by the Comparison Approach. IEEE Transactions on Computers, 41, 1386-1396. https://doi.org/10.1109/12.177309 |
| [5] | Hsu, G. and Tan, J.J.M. (2007) A Local Diagnosability Measure for Multiprocessor Systems. IEEE Transactions on Parallel and Distributed Systems, 18, 598-607. https://doi.org/10.1109/tpds.2007.1022 |
| [6] | Chiang, C. 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. https://doi.org/10.1109/tc.2008.158 |
| [7] | Chen, M., Hsu, D.F. and Lin, C. (2022) A New Structure for a Vertex to Be Locally T-Diagnosable in Large Multiprocessor Systems. Theoretical Computer Science, 934, 81-90. https://doi.org/10.1016/j.tcs.2022.08.020 |
| [8] | Chen, M., Lin, C. and Pai, K. (2022) A Tree Structure for Local Diagnosis in Multiprocessor Systems under Comparison Model. In: Hsieh, S.Y., Hung, L.J., Klasing, R., Lee, C.W. and Peng, S.L., Eds., Communications in Computer and Information Science, Springer, 49-60. https://doi.org/10.1007/978-981-19-9582-8_5 |
| [9] | Lv, Y., Lin, C., Hsu, D.F. and Fan, J. (2024) An Algorithm for Conditional-Fault Local Diagnosis of Multiprocessor Systems under the MM⁎ Model. Theoretical Computer Science, 987, Article ID: 114372. https://doi.org/10.1016/j.tcs.2023.114372 |
| [10] | Lin, C., Kung, T. and Tan, J.J.M. (2011) Conditional-Fault Diagnosability of Multiprocessor Systems with an Efficient Local Diagnosis Algorithm under the PMC Model. IEEE Transactions on Parallel and Distributed Systems, 22, 1669-1680. https://doi.org/10.1109/tpds.2011.46 |
| [11] | Lin, C., Kung, T. and Tan, J.J.M. (2013) An Algorithmic Approach to Conditional-Fault Local Diagnosis of Regular Multiprocessor Interconnected Systems under the PMC Model. IEEE Transactions on Computers, 62, 439-451. https://doi.org/10.1109/tc.2011.249 |
| [12] | Lin, C., Teng, Y., Tan, J.J.M. and Hsu, L. (2013) Local Diagnosis Algorithms for Multiprocessor Systems under the Comparison Diagnosis Model. IEEE Transactions on Reliability, 62, 800-810. https://doi.org/10.1109/tr.2013.2285031 |
| [13] | Lin, L., Huang, Y., Lin, Y., Hsieh, S. and Xu, L. (2021) FFNLFD: Fault Diagnosis of Multiprocessor Systems at Local Node with Fault-Free Neighbors under PMC Model and MM* Model. IEEE Transactions on Parallel and Distributed Systems, 33, 1739-1751. https://doi.org/10.1109/tpds.2021.3126257 |
| [14] | Yuan, J., Qiao, H., Liu, A. and Wang, X. (2022) Measurement and Algorithm for Conditional Local Diagnosis of Regular Networks under the MM* Model. Discrete Applied Mathematics, 309, 46-67. https://doi.org/10.1016/j.dam.2021.11.006 |
| [15] | Lai, P., Tan, J.J.M., Chang, C. and Hsu, L. (2005) Conditional Diagnosability Measures for Large Multiprocessor Systems. IEEE Transactions on Computers, 54, 165-175. https://doi.org/10.1109/tc.2005.19 |
| [16] | Fàbrega, J. and Fiol, M.A. (1996) On the Extraconnectivity of Graphs. Discrete Mathematics, 155, 49-57. https://doi.org/10.1016/0012-365x(94)00369-t |
| [17] | Zhang, S. and Yang, W. (2016) The g-Extra Conditional Diagnosability and Sequential t/k-Diagnosability of Hypercubes. International Journal of Computer Mathematics, 93, 482-497. https://doi.org/10.1080/00207160.2015.1020796 |
| [18] | Lin, L., Hsieh, S., Xu, L., Zhou, S. and Chen, R. (2018) The Relationship between Extra Connectivity and Conditional Diagnosability of Regular Graphs under the PMC Model. Journal of Computer and System Sciences, 95, 1-18. https://doi.org/10.1016/j.jcss.2017.11.004 |
| [19] | Lin, L., Xu, L., Chen, R., Hsieh, S. and Wang, D. (2019) Relating Extra Connectivity and Extra Conditional Diagnosability in Regular Networks. IEEE Transactions on Dependable and Secure Computing, 16, 1086-1097. https://doi.org/10.1109/tdsc.2017.2726541 |
