Share This Article:

Conditional Diagnosability of the Locally Twisted Cubes under the PMC Model

Full-Text HTML Download Download as PDF (Size:189KB) PP. 220-224
DOI: 10.4236/cn.2011.34025    3,019 Downloads   5,539 Views   Citations


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.

Conflicts of Interest

The authors declare no conflicts of interest.

Cite this paper

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.


[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 © 2018 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.