在對於估算多處理器系統的可靠度上及在許多著名的連結網路上的偵錯，處理器故障的診斷扮演著重要的角色。條件偵錯度(Conditional Diagnosability)是一個測量偵錯度的新方式，它藉由增加一個限制條件︰在一個系統中，任一個處理器其與之相鄰的處理器不會同時全都故障的條件下求其偵錯度。在論文中，我們所探討的連結網路架構為k元n立方體（k-ary n-cubes），根據其屬性，證明出在比較偵錯模式下，當k>=4且n>=4時，k元n立方體的條件偵錯度為6n-5。

Processor fault diagnosis plays an important role in measuring the reliability of multi-processor systems and the diagnosis of many well-known interconnected networks. Conditional diagnosability is a novel measure of diagnosability, which was introduced by Lai et al., who added the additional condition that any faulty set cannot contain all of the neighbors of any vertex in a system. In this thesis we study some topological properties of k-ary n-cubes, where k>=4 and n>=4, from which we can show that the conditional diagnosability of k-ary n-cubes under the comparison diagnosis model is 6n-5.

[1] J. R. Armstrong and F. G. Gray, "Fault diagnosis in a boolean n cube array of multiprocessors," IEEE Transactions on Computers, vol. 30, no. 8, pp. 587-590, 1981.
[2] T. Araki and Y. Shibata, "Diagnosability of networks represented by the Cartesian product," IEICE Transactions on Fundamentals, vol. E83-A, no. 3, pp. 465-470, 2000.
[3] B. Bose, B. Broeg, Y. Kwon, and Y. Ashir, "Lee distance and topological properties of k-ary n-cubes," IEEE Transactions on Computers, vol. 44, no. 8, pp. 1021-1030,
1995.
[4] G. Y. Chang, G. J. Chang, and G. H. Chen, "Diagnosabilities of regular networks," IEEE Transactions on Parallel and Distributed Systems, vol. 16, no. 4, pp. 314-323, 2005.
[5] A. T. Dahbura and G. M. Masson, "An O(n^{2.5}) fault identication algorithm for diagnosable systems," IEEE Transactions on Computers, vol. 33, no. 6, pp. 486-492,
1984.
[6] K. Day and A. E. Ai-Ayyoub, "Fault diameter of k-ary n-cube networks," IEEE Transactions on Parallel and Distributed Systems, vol. 8, pp. 903-907, 1997.
[7] K. Day, "The conditional node connectivity of the k-ary n-cube," Journal of Interconnection Networks, vol. 5, no.1, pp. 13-26, 2004.
[8] A. D. Friedman and L. Simoncini, "System-level fault diagnosis," The Computer Journal, vol. 13, no. 3, pp. 47-53, 1980.
[9] H. Fujiwara and K. Kinoshita, "On the computational complexity of system diagnosis," IEEE Transactions on Computers, vol. 27, no. 10, pp. 881-885, 1978.
[10] J. Fan, "Diagnosability of crossed cubes under the two strategies," Chinese Journal of Computers, vol. 21, no. 5, pp. 456-462, 1998.
[11] J. Fan, "Diagnosability of the MÄobius cubes," IEEE Transactions on Parallel and Distributed Systems, vol. 9, no. 9, pp. 923-928, 1998.
[12] A. Gonzalez, M. ValeroGarcia and L. Diaz de Cerio, "Executing algorithms with hypercube topology on torus multicomputers," IEEE Transactions on Parallel and
Distributed Systems, vol. 6, no. 8, pp. 803-814, 1995.
[13] G. H. Hsu and J. J. M. Tan, "Conditional diagnosability of the BC Networks under the comparison diagnosis model," International Computer Symposium, vol. 1, pp. 269-274, 2008.
[14] S. L. Hakimi and A. T. Amin, "Characterization of connection assignment of diagnosable systems," IEEE Transactions on Computers, vol. 23, pp. 86-88, 1974.
[15] S. Y. Hsieh and T. J. Lin, "Embedding cycles and paths in a k-ary n-cube," in Proceedings of International Conference on Parallel and Distributed Systems, vol. 2, pp. 1-7, 2007.
[16] S. Y. Hsieh and Y. S. Chen, "Strongly diagnosable product networks under the comparison diagnosis model," IEEE Transactions on Computers, vol. 57, no. 6, pp. 721-732, 2008.
[17] S. Y. Hsieh and Y. S. Chen, "Strongly diagnosable systems under the comparison diagnosis model," IEEE Transactions on Computers, vol. 57, no. 12, pp. 1720-1725,
2008.
[18] S. Y. Hsieh and T. J. Lin, "Panconnectivity and edge-pancyclicity of k-ary n-cubes," Networks, vol. 54, issue 1, pp. 1-11, 2009.
[19] S. Y. Hsieh and C. W. Lee, "Diagnosability of two-matching composition networks under the MM* model," IEEE Transactions on Dependable and Secure Computing, vol. 8, no. 2, pp. 246-255, 2011.
[20] Y. Ishida, N. Adachi, and H. Tokumaru, "Diagnosability and distinguishability analysis and its applications," IEEE Transactions on Reliability, vol. 36, no. 5, pp. 531-538,
1987.
[21] A. Kavianpour, "Sequential diagnosability of star graphs," Computers and Electrical Engineering, vol. 22, no. 1, pp. 37-44, 1996.
[22] A. Kavianpour and K. H. Kim, "Diagnosability of hypercubes under the pessimistic one-step diagnosis strategy," IEEE Transactions on Computers, vol. 40, no. 2, pp. 232-237, 1991.
[23] A. Kavianpour and K. H. Kim, "A comparative evaluation of four basic system-level diagnosis strategies for hypercubes," IEEE Transactions on Reliability, vol. 41, no. 1, pp. 26-37, 1992.
[24] R. E. Kessler and J. L. Schwarzmeier, "Cray T3D: a new dimension for Cray research," in Proceedings of the 38th IEEE Computer Society International Conference, pp. 176-
182, 1993.
[25] C. K. Lin, J. J. M. Tan, L. H. Hsu, E. Cheng, and L. Liptak, "Conditional diagnosability of Cayley Graphs generated by transposition trees under the comparison diagnosis model," Journal of Interconnection Networks, vol. 9, nos. 1-2, pp. 83-97, 2008.
[26] P. L. Lai, J. J.M. Tan, C. P. Chang, and L. H. Hsu, "Conditional diagnosability measures for large multiprocessor systems," IEEE Transactions on Computers, vol. 54, no. 2, pp. 165-175, 2005.
[27] J. Maeng and M. Malek, "A comparison connection assignment for self-diagnosis of multiprocessors systems," in Proceedings of the 11th International Symposium on
Fault-Tolerant Computing, pp. 173-175, 1981.
[28] M. Malek, "A comparison connection assignment for diagnosis of multiprocessor systems," in Proceedings of the 7th International Symposium on Computer Architecture, pp. 31-36, 1980.
[29] W. Mao, and D. M. Nicol, "On k-ary n-cubes: theory and applications," Discrete Applied Mathematics, vol. 129, pp. 171-193, 2003.
[30] W. Najjar and J. L. Gaudiot, "Network resilience: a measure of network fault tolerance," IEEE Transactions on Computers, vol. 39, pp. 174-181, 1990.
[31] F. P. Preparata, G. Metze, and R.T. Chien, "On the connection assignment problem of diagnosable systems," IEEE Transactions on Electronic Computers, vol. 16, no. 6, pp. 848-854, 1967.
[32] Y. Pan, "Fault tolerance in the block-shift network," IEEE Transactions on Reliability, vol. 50, no. 1, pp. 85-91, 2001.
[33] A. Sengupta and A. T. Dahbura, "On self-diagnosable multiprocessor systems: diagnosis by the comparison approach," IEEE Transactions on Computers, vol. 41, no. 11, pp. 1386-1396, 1992.
[34] A. K. Somani, V. K. Agarwal, and D. Avis, "A generalized theory for system level diagnosis," IEEE Transactions on Computers, vol. 36, no. 5, pp. 538-546, 1987.
[35] H. Sarbazi-Azad, M. Ould-Khaoua, L. M. Mackenzie, and S. G. Akl, "On some properties of k-ary n-cubes," Proceedings of the Eighth International Conference on Parallel and Distributed Systems (ICPADS), IEEE Computer Society, pp. 517-524, 2001.
[36] D. Wang, "Diagnosability of enhanced hypercubes," IEEE Transactions on Computers, vol. 43, no. 9, pp. 1054-1061, 1994.
[37] D. Wang, "Diagnosability of hypercubes and enhanced hypercubes under the comparison diagnosis model," IEEE Transactions on Computers, vol. 48, no. 12, pp. 1369-1374, 1999.
[38] M. Xu, K. Thulasiraman, and X. D. Hu, "Conditional diagnosability of matching composition networks under the PMC model," IEEE Transactions on Circuits and Systems, vol. 56, no. 11, pp. 875-879, 2009.
[39] X. Yang, Y.Y. Tang and J. Cao, "Embedding torus in hexagonal honeycomb torus," IET Computers and Digital Techniques, vol. 2. no. 2, pp. 86-93, 2008.
[40] J. Zhao, F. J. Meyer, N. Park, and F. Lombardi, "Sequential diagnosis of processor array systems," IEEE Transactions on Reliability, vol. 53, no. 4, pp. 487-498, 2004.
[41] S. Zhou, "The conditional diagnosability of hypercubes under the comparison model," Proceedings of the 2009 WASE International Conference on Information Engineering,
pp. 459-462, 2009.
[42] S. Zhou, "The conditional diagnosability of MÄobius cubes under the Comparison Model," Proceedings of the 2009 IEEE International Conference on Information and
Automation, pp. 96-100, 2009.
[43] S. Zhou, "The conditional diagnosability of locally twisted cubes," Proceedings of 2009 4th International Conference on Computer Science and Education, pp. 221-226,
2009.
[44] S. Zhou, "The conditional diagnosability of twisted cubes under the comparison model," 2009 IEEE International Symposium on Parallel and Distributed Processing with Applications, pp. 696-701, 2009.
[45] S. Zhou, "The conditional diagnosability of crossed cubes under the comparison model ," International Journal of Computer Mathematics, vol. 87, no. 15, pp. 3387-3396,
2010.