(t,k)-偵錯是循序偵錯的概念化，當系統最多t個有毛病的處理機時，每一次進行偵錯至少辨識出k個有毛病的處理機並且以正常的更換取代。在本篇論文中，我們提出一種統一的方法來計算許多多處理機系統的(t,k)-可偵錯度，包括超立方體（hypercubes）、交叉立方體（crossed cubes）、雙扭立方體（twisted cubes）、局部雙扭立方體（locally twisted cubes）、多重雙扭立方體（multiply twisted cubes）、廣義雙扭立方體（generalized twisted cubes）、遞迴環型圖（recursive circulants）、莫氏立方體（Mobius cubes）、M立方體（Mcubes）、星圖（star graphs）、氣泡排序圖（bubble-sort graphs）、煎餅圖（pancake graphs）和燒煎餅圖（burnt pancke graphs）。我們方法的關鍵性概念是概略上面多處理機系統共同的特性，並且證明他們的拓撲結構有共同的超級類別，稱之為合成圖（component-composition graphs）。我們之後證明m（m >= 4）維度合成圖G的(t,k)-可偵錯度下限。根據這個結果，上面提到的多處理機系統可以有效率低計算出其(t,k)-可偵錯度。

(t,k)-Diagnosis, which is a generalization of sequential diagnosis, requires at least k faulty processors identified and replaced in each iteration provided there are at most t faulty processors, where t>=k. In this paper, we propose a unified approach to compute the (t,k)-diagnosability for numerous multiprocessor systems, including hypercubes, crossed cubes, twisted cubes, locally twisted cubes, multiply twisted cubes, generalized twisted cubes, recursive circulants, Mobius cubes, Mcubes, star graphs, bubble-sort graphs, pancake graphs, and burnt pancake graphs. The key concept of our approach is to sketch the common graph properties of the above multiprocessor systems and demonstrate that their underlying topologies have a common super class of graphs, called component-composition graphs. We then show that the m-dimensional component-composition graph G for m>=4 is a lower bound of the (t,k)-diagnosability. Based on this result, the (t,k)-diagnosability of the referred multiprocessor systems can be e±ciently computed.

[1] S. B. Akers, D. Horel, and B. Krishnamurthy, "The star graph: an attractive alternative to the n-cube," in Proceedings of the International Conference on Parallel
Processing, pp. 393-400, 1987.
[2] S. B. Akers and B. krishnamurthy, "A group-theoretic model for symmetric interconnection networks," IEEE Transactions on Computers, vol. 38, no. 4, pp. 555-566, 1989.
[3] T. Araki and Y. Shibata, "(t,k)-diagnosable system: A generalization of the PMC
models," IEEE Transactions on Computers, vol. 52, no. 7, pp. 971-975, 2003.
[4] L. Bhuyan and D. P. Agrawal, "Generalized hypercubes and hyperbus structure for
a computer network," IEEE Transactions on Computers, vol. 33, pp. 323-333, 1984.
[5] J. R. Armstrong and F. G. Gray, "Fault diagnosis in a boolean n-cube array of
microprocessors," IEEE Transactions on Computers, vol. C-30, no. 8, pp. 587-590, 1981.
[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-322, 2005.
[7] G. Y. Chang and G. H. Chen, "(t,k)-diagnosability of multiprocessor systems with
applications to grids and tori," SIAM Journal on Computing, vol. 37, no. 4, pp. 1280-1298, 2007.
[8] G. Y. Chang, G. H. Chen, and G. J. Chang, "(t,k)-diagnosis for matching composition
networks," IEEE Transactions on Computers, vol. 55, no. 1, pp. 88-92, 2006.
[9] G. Y. Chang, G. H. Chen, and G. J. Chang, "(t,k)-diagnosis for matching composition
networks under the MM* model," IEEE Transactions on Computers, vol. 56, no. 1, pp. 73-79, 2007.
[10] F. B. Chedid, "On the generalized twisted cube," Information Processing Letters, vol.
55, no. 1, pp. 49-52, 1995.
[11] P. Cull and S. M. Larson, "The MAobius cubes," IEEE Transactions on Computers,
vol. 44, no. 5, pp.647-659, 1995.
[12] A. T. Dahabura and G. M. Masson, "An o(n^2.5) fault identification algorithm for
diagnosable systems," IEEE Transactions on Computers, vol. C-33, no. 6, pp. 486-492, 1984.
[13] A. H. Esfahanian, L. M. Ni, and B. E. Sagan, "The twisted n-cube with application to
multiprocessing," IEEE Transactions on Computers, vol. 40, no. 1, pp. 88-93, 1991.
[14] K. Efe, "A variation on the hypercube with lower diameter," IEEE Transactions on
Computers, vol. 40, no. 11, pp. 1312-1316, 1991.
[15] K. Efe, "The crossed cube architecture for parallel computation," IEEE Transactions
on Parallel and Distributed Systems, vol. 3, no. 5, pp. 513-524, 1992.
[16] J. Fan, "Diagnosability of the mAobius cubes," IEEE Transactions on Parallel and
Distributed Systems, vol. 9, no. 9, pp. 923-928, 1998.
[17] J. Fan, "Diagnosability of crossed cubes under the comparison diagnosis model,"
IEEE Transactions on Parallel and Distributed Systems, vol. 13, no. 7, pp. 687-692, 2002.
[18] J. Fan and X. Lin, "The t/k-diagnosability of the BC graphs," IEEE Transactions
on Computers, vol. 54, no. 2, pp. 176-184, 2005.
[19] A. D. Friedman and L. Simoncini, "System-level fault diagnosis," Computer, vol. 13,
no. 3, pp. 47-53, 1980.
[20] H. Fujiwara and K. Kinoshita, "On the computational complexity of system diagnosis," IEEE Transactions on Computers, vol. C-27, no. 10, pp. 881-885, 1978.
[21] S. L. Hakimi and A. T. Amin, "On the computational complexity of system diagnosis," IEEE Transactions on Computers, vol. 23, no. 1, pp. 86-88, 1974.
[22] P. A. J. Hilbers, M. R. J. Koopman, and J. L. A. van de Snepscheut, "The twisted
cube," in Proceedings of the Conference on Parallel Architectures and Languages Europe, Volume I: Parallel Architectures, pp. 152-159, 1987.
[23] 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-731, 2008.
[24] J. S. Jwo, S. Lakshmivarahan, and S. K. Dhall, "A new class of interconnection
networks based on the alternating group," Networks, vol. 23, pp. 315-326, 1993.
[25] K. Kaneko and N. Sawada, "An algorithm for node-to-set disjoint paths problem
in burnt pancake graphs," IEICE Transactions on Information and Systems, vol.
E86VD, no. 12, pp. 2588-2594, 2003.
[26] K. Kaneko and N. Sawada, "An algorithm for node-to-node disjoint paths problem
in burnt pancake graphs," IEICE Transactions on Information and Systems, vol.
E90VD, no. 1, pp. 306-313, 2007.
[27] A. Kavianpour, "Sequential diagnosability of star graphs," Computers & Electrical
Engineering, vol. 22, no. 1, pp. 37-44, 1996.
[28] A. Kavianpour and K. H. Kim, "Diagnosabilities of hypercubes under the pessimistic
one-step diagnosis strategy," IEEE Transactions on Computers, vol. 40, no. 2, pp. 232-237, 1991.
[29] A. Kavianpour and K. H. Kim, "A comparative evaluation of four basic system-level
diagnosis strategies for hypercubes," IEEE Transactions on Computers, vol. 41, no. 1, pp. 26-37, 1992.
[30] S. Khanna and W. K. Fuchs, "A linear time algorithm for sequential diagnosis in
hypercubes," Journal of Parallel and Distributed Computing, vol. 26, pp. 48-53, 1995.
[31] S. Khanna and W. K. Fuchs, "A graph partitioning approach to sequential diagnosis,"
IEEE Transactions on Computers, vol. 46, no. 1, pp. 39-47, 1997.
[32] S. Lakshmivarahan, J. S. Jwo, and S. K. Dhall, "Symmetry in interconnection networks based on cayley graphs of permutation groups: a survey," Parallel Computing, vol. 19, no. 4, pp. 361-407, 1993.
[33] F. T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees,
Hypercubes, Morgan Kaufmann, San Mateo, CA, 1992.
[34] 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, no. 1 & 2, pp. 83-97, 2008.
[35] J. H. Park and K. Y. Chwa, "Recursive circulants and their embeddings among
hypercubes," Theoretical Computer Science, vol. 244, pp. 35-62, 2000.
[36] J. H. Park, H. C. Kim, and H. S. Lim, "Many-to-many disjoint path covers in
hypercube-like interconnection networks with faulty elements," IEEE Transactions
on Parallel and Distributed Systems, vol. 17, no. 3, pp. 227-240, 2006.
[37] J. H. Park, H. S. Lim, and H. C. Kim, "Panconnectivity and pancyclicity of
hypercube-like interconnection networks with faulty elements," Theortical Computer
Science, vol. 377, pp. 170-180, 2007.
[38] F. P. Preparata, G. Metze, and R. T. Chien, "On the connection assignment problem
of diagnosable systems," IEEE Transactions on Electronic Computers, vol. EC-16, no. 6, pp. 848-854, 1967.
[39] N. K. Singhvi and K. Ghose, "The Mcube: a symmetrical cube based network with
twisted links," in: Proceedings of the 9th IEEE International Parallel Processing
Symposium IPPS 1995, pp. 11-16, 1995.
[40] A. K. Somani, V. K. Agarwal, and D. Avis, "A generalized theory for system level
diagnosis," IEEE Transactions on Computers, vol. C-36, no. 5, pp. 538-546, 1987.
[41] A. K. Somani and O. Peleg, "On diagnosability of large fault sets in regular topologybased computer systems," IEEE Transactions on Computers, vol. 45, no. 8, pp. 892-902, 1996.
[42] Y. Suzuki and K. Kaneko, "An algorithm for node-disjoint paths in pancake graphs,"
IEICE Transactions on Information and Systems, vol. E86-D, no. 3, pp. 610-615, 2003.
[43] A. S. Vaidya, P. S. N. Rao, and S. R. Shankar, "A class of hypercube-like networks,"
in: Proc. 5th Symp. on Parallel and Distributed Processing, pp. 800-803, 1993.
[44] D.Wang, "Diagnosability of enhanced hypercubes," IEEE Transactions on Computers, vol. 43, no. 9, pp. 1054-1061, 1994.
[45] 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.
[46] J. Xu and S. ze Huang, "Sequentially t-diagnosable system: A characterization and
its applications," IEEE Transactions on Computers, vol. 44, no. 2, pp. 340-345, 1995.
[47] T. Yamada, T. Ohtsukab, A. Watanabe, and S. Ueno, "On sequential diagnosis of
multiprocessor systems," Discrete Applied Mathematics, vol. 146, no. 3, pp. 311-342,
2005.
[48] X. Yang, D. J. Evans, and G. M. Megson, "The locally twisted cubes," International
Journal of Computer Mathematics, vol. 82, no. 4, pp. 401-413, 2005.
[49] J. Zheng, S. Latifi, E. Regentova, K. Luo, and X. Wu, "Diagnosability of star graphs
under the comparison diagnosis model," Information Processing Letters, vol. 93, no.
1, pp. 29-36, 2005.