處理器錯誤診斷在多處理器系統之可靠度當中扮演著相當重要的角色，並且多數知名的多處理器系統之偵錯度也已經被廣泛的研究出。在2005年，賴教授等人[23] 當時提出一個新的偵錯度測量方法–即條件偵錯度，並且條件偵錯度的大小比傳統的偵錯度還要來的大。條件偵錯度所發展的基礎是限制在假設系統中每一個處理器的鄰居不會在同一時間發生錯誤。這個限制發展的原因是系統中每一個處理器的鄰居在同一時間發生錯誤發生之機率是相當小的。在本篇論文當中，我們計算了在PMC模式之下k元n立方體的條件偵錯度。k元n立方體是有名的互連網路拓墣圖形之一，它具有許多良好的特性。在我們的結果當中，在k,n≧4的條件之下，k元n立方體的條件偵錯度大小為8n-7。

Processor fault diagnosis has been an important part in the reliability of a multiprocessor system, and the diagnosability of many well-known multiprocessor systems have been widely investigated. In 2005, Lai et al. [23] proposed a new measure of diagnosability namely conditional diagnosability, which is larger than the classical diagnosability. The conditional diagnosability based on restricting that for each processor in the system, all the neighbors do not fail at the same time. Because the probability of above situation is quite small. In this thesis, we evaluate the conditional diagnosability for the k-ary n-cubes under the PMC model. The k-ary n-cube is one of the well-known topologies for interconnection networks. And it has some favorable properties. From our result, the conditional diagnosability of the k-ary n-cubes is 8n-7 for k ≥ 4, n ≥ 4.

[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] Y. A. Ashir and I.A. Stewart, “Fault-tolerant embeddings of Hamiltonian circuits in k-ary n-cubes,” SIAM Journal on Discrete Mathematics, vol. 15, no. 3, pp. 317–328, 2002.
[3] M. M. Bae and B. Bose, “Edge disjoint Hamiltonian cycles in k-ary n-cubes and hypercube,” IEEE Transactions on Computers, vol. 52, no. 10, pp. 1271–1284, 2003.
[4] 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, Aug. 1995.
[5] M. Y. Chan and S. J. Lee, “On the existence of Hamiltonian circuits in faulty hypercubes,” SIAM Journal on Discrete Mathematics, vol. 4, no. 4, pp. 511–527, 1991.
[6] 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.
[7] N. W. Chang and S. Y. Hsieh, “Conditional diagnosability of augmented cubes under the PMC model,” IEEE Transactions on Dependable and Secure 45 Computing IEEE computer Society Digital Library. IEEE Computer Society, http://dx.doi.org/10.1109/TDSC.2010.59.
[8] 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, pp. 486–492, 1984.
[9] K. Day and A. E. Ai-Ayyoub, “Fault diameter of k-ary n-cube networks,” IEEE Transactions Parallel Distribution Systems, vol. 8, no. 9, pp. 903–907, 1997.
[10] J. Fan, “Diagnosability of the M¨obius cubes,” IEEE Transactions on Parallel and Distributed Systems, vol. 9, no. 9, pp. 923–928, 1998.
[11] H. Fujiwara and K. Kinoshita, “On the computational complexity of system diagnosis,” IEEE Transactions on Computers, vol. 100, no. 10, pp. 881–885, 1978.
[12] A. Ghafoor, “A class of fault-tolerant multiprocessor networks,” IEEE Transactions on Reliability, vol. 38, no. 1, pp. 5–15, 1989.
[13] A. Ghafoor, “Partitioning of even networks for improved diagnosability,” IEEE Transactions on Reliability, vol. 39, no. 3, pp. 281–286, 1990.
[14] S. A. Ghozati and H. C. Wasserman, “The k-ary n-cube network: modeling, topological properties and routing strategies,” Computers and Electrical Engineering, vol. 25, no. 3, pp. 155–168, 1999.
[15] S. L. Hakimi and A. T. Amin, “Characterization of the connection assignment of diagnosable systems,” IEEE Transactions on Computers, vol. C-23, pp. 86–88, Jan. 1974.
[16] W. S. Hong and S. Y. Hsieh, “Strong diagnosability and conditional diagnosability of augmented cubes under the comparison diagnosis model,” IEEE Transactions on Reliability, accepted.
[17] 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.
[18] 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.
[19] 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. 1, pp. 1–7, 2007.
[20] G. H. Hsu, C. F. Chiang, L. M. Shih, L. H. Hsu, and J. J. M. Tan, “Conditional diagnosability of hypercubes under the comparison diagnosis model,” Journal of SystemsArchitecture, vol. 55, no. 2, pp. 140–146, 2009.
[21] G. H. Hsu and J. J. M. Tan, “Conditional diagnosabilit y of the BC networks under the comparison diagnosis model,” International Computer Symposium, vol. 1, pp. 269–274, 2008.
[22] P. L. Lai, J. J. M. Tan, C. H. Tsai, and L. H. Hsu, “The diagnosability of the matching composition network under the comparison diagnosis model,” IEEE Transactions on Computers, vol. 53, pp. 1064–1069, 2004.
[23] 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.
[24] C. W. Lee and S. Y. Hsieh, “Determining the Diagnosability of (1,2)-matching composition networks and its applications,” IEEE Transactions on Dependable and Secure Computing, vol. 8, no. 3, pp. 353–362, 2011.
[25] C. W. Lee and S. Y. Hsieh, “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.
[26] C. K. Lin, J. J. M. Tan, L. H. Hsu, E. Cheng, and L. Lipt´ak, “Conditional diagnosability of Cayley graphs generated by transposition trees,” Journal of Interconnection Networks, vol. 9, nos. 1-2, pp. 83–97, 2008.
[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 multiprocessors systems,” in Proceedings of the 7th International Symposium on Computer Architecture, pp. 31–36, 1980.
[29] F. P. Preparata, G. Metze, and R.T. Chien, “On the connection assignment problem of diagnosis systems,” IEEE Transactions on Electronic Computers, vol. 16, no. 12, pp. 848–854, 1967.
[30] A. Sengupta and A. Dahbura, “On self-diagnosable multiprocessor system: diagnosis by the comparison approach,” IEEE Transactions on Computers, vol. 41, no. 11, pp. 1386–1396, 1992.
[31] 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.
[32] D. Wang, T. An, M. Pan, K. Wang, and S. Qu, “Hamiltonian-like properies of k-Ary n-Cubes,” in Proceedings of Sixth International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT05), pp. 1002–1007, 2005.
[33] 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, vol. 56, no. 11, pp. 875–879, 2009.
[34] 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.
[35] S. Zhou, “The conditional diagnosability of locally twisted cubes,” Proceedings of 2009 4th International Conference on Computer Science and Education, pp. 221-226, 2009.
[36] 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.
[37] S. Zhou, “The conditional diagnosability of crossed cubes under the comparison model,” 2009 International Journal of Computer Mathematics, vol. 87, no. 15, pp. 3387–3396, 2010.
[38] Q. Zhu, “On conditional diagnosability and reliability of the BC networks,” The Journal of Supercomputing, vol. 45, no. 2, pp. 173–184,2008.
[39] Q. Zhu, S. Y. Liu, and M. Xu, “On conditional diagnosability of folded hypercubes,” Information Science, vol. 178, no.4, pp.1069-1077, 2008.