Conditional Diagnosability of the Locally Twisted Cubes under the PMC Model

.
DOI: 10.4236/cn.2011.34025   PDF   HTML     3,180 Downloads   5,865 Views   Citations

Abstract

In a multiprocessor systems, it is important to local and to replace the faulty processors to maintain systempsilas high reliability. The fault diagnosis, which is the process of identifying fault processors in a multiprocessor system through testing. The conditional diagnosis requires that for each processor u in a system, all the processors that are directly connected to u do not fail at the same time. In this paper, we study the conditional diagnosability of the n-dimensional locally twisted cubes. After showing some properties of the locally twisted cubes, we prove that it under the PMC model is 4n – 7 for n ≥ 5.

Share and Cite:

R. Feng, G. Bian and X. Wang, "Conditional Diagnosability of the Locally Twisted Cubes under the PMC Model," Communications and Network, Vol. 3 No. 4, 2011, pp. 220-224. doi: 10.4236/cn.2011.34025.

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1] G. M. F. P. Preparata and R. T. Chien, “On the Connection Assignment Problem of Diagnosable Systems,” IEEE Transactions on Electronic Computers, Vol. EC-16, No. 6, December 1967, pp. 848-854. doi:10.1109/PGEC.1967.264748
[2] M. M. J. Maeng, “A Comparison Connection Assignment for Self-Diagnosis of Multiprocessors Systems,” Proceedings of the 11th International Symposium on Fault-Tolerant Computing, Portland, 1981, pp. 173-175.
[3] F. G. F. Barsi and P. Maestrini, “A Theory of Diagnosability of Digital Systems,” IEEE Transactions on Computers, Vol. C-25, No. 6, June 1976, pp. 585-593. doi:10.1109/TC.1976.1674658
[4] R. Ahlswede and H. Aydinian, “On Diagnosability of Large Multiprocessor Networks,” Discrete Applied Mathematics, Vol. 156, No. 18, 2008, pp. 3464-3474. doi:10.1016/j.dam.2008.02.001
[5] D. Wang, “Diagnosability of Enhanced Hypercubes,” IEEE Transactions on Computers, Vol. 43, No. 9, 1994, pp. 1054-1061. doi:10.1109/12.312114
[6] J. Fan, “Diagnosability of the Mobius Cubes,” IEEE Transactions on Parallel and Distributed Systems, Vol. 9, No. 9, 1998, pp. 923-928. doi:10.1109/71.722224
[7] P.-L. Lai, J. Tan, C.-P. Chang and L.-H. Hsu, “Conditional Diagnosability Measures for Large Multiprocessor Systems,” IEEE Transactions on Computers, Vol. 54, No. 2, 2005, pp. 165-175. doi:10.1109/TC.2005.19
[8] S. Hsieh and C. Lee, “Diagnosability of Two-Matching Composition Networks under the MM* Model,” IEEE Transactions on Dependable and Secure Computing, Vol. 8, No. 2, 2009, pp. 246-255.
[9] Q. Zhu, S.-Y. Liu and M. Xu, “On Conditional Diagnosability of the Folded Hypercubes,” Information Sciences, Vol. 178, No. 4, 2008, pp. 1069-1077. doi:10.1016/j.ins.2007.09.005
[10] M. Xu, K. Thulasiraman and X.-D. Hu, “Conditional Diagnosability of Matching Composition Networks under the Pmc Model,” IEEE Transactions on Circuits and Systems II: Express Briefs, Vol. 56, No. 11, 2009, pp. 875-879. doi:10.1109/TCSII.2009.2030361
[11] Q. Zhu, “On Conditional Diagnosability and Reliability of the bc Networks,” The Journal of Supercomputing, Vol. 45, No. 2, 2008, pp. 173-184. doi:10.1007/s11227-007-0167-8
[12] S.-M. Zhou, “The Conditional Diagnosability of Locally Twisted Cubes,” Proceedings of the 4th International Conference on Computer Science and Education, 2009, pp. 221-226.
[13] J. A. Bondy and U. S. R. Murty, “Graph Theory with Applications,” North Holland, New York, 1976.
[14] X.-F. Yang, D. J. Evans and G. M. Megson, “The Locally Twisted Cubes,” International Journal of Computer Mathematics, Vol. 82, No. 4, April 2005, pp. 401-413. doi:10.1080/0020716042000301752
[15] G. M. A. T. Dahbura, “An O(n2.5) Fault Identification Algorithm for Diagnosable Systems,” IEEE Transactions on Computers, Vol. C-33, No. 6, 1984, pp. 486-492. doi:10.1109/TC.1984.1676472
[16] A. T. Dahbura and G. M. Masson, “An O(n2.5) Fault Identification Algorithm for Diagnosable Systems,” IEEE Transactions on Computers, Vol. 33, No. 6, 1984, pp. 486-492. doi:10.1109/TC.1984.1676472
[17] J.-X. Fan, S.-K. Zhang, et al., “The Restricted Connectivity of Locally Twisted Cubes,” 2009 10th International Symposium on Pervasive Systems, Algorithms, and Networks (ISPAN), Kaohsiung, 14-16 December 2009, pp. 574-578. doi:10.1109/I-SPAN.2009.48
[18] J. Fan and X. Lin, “The t/k-Diagnosability of the BC Graphs,” IEEE Transactions on Computers, Vol. 54, No. 2, 2005, pp. 176-184. doi:10.1109/TC.2005.33
[19] X.-F. Yang, J.-Q. Cao, G. M. Megson and J. Luo, “Minimum Neighborhood in a Generalized Cube,” Information Processing Letters, Vol. 97, 2006, pp. 88-93.

  
comments powered by Disqus

Copyright © 2020 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.