強偵錯性(strong diagnosability)提出了一個新的概念在於估量多處理器系統的可靠性，它比傳統的估量指標－偵錯性(diagnosability)更為精確。在論文中，我們研究在PMC模式下多處理器系統的強偵錯性，我們的主要結果是證明於PMC模式下正則網路與卡氏積網路的強偵錯性。以我們的結果為基礎，我們證明了以下幾個為人所熟知的互聯網路架構的強偵錯性：超立方體(hypercube)、加強型超立方體(enhanced hypercube)、雙扭超立方體(twisted cube)、局部雙扭超立方體(locally twisted cube)、交錯立方體(crossed cube)、莫氏立方體(Möbius cube)、星狀圖(star graph)、網狀連結超立方體(mesh-connected hypercube)、圓環面連結超立方體(torus-connected hypercube)以及超彼得森圖形(hyper Petersen graph)。

Strong diagnosability provides a new concept in measuring the reliability of multiprocessor systems, which is more precise than the traditional global measurement. In this thesis, we study strong diagnosabilities of multiprocessor systems under the PMC model. Our main results are to determinate strong diagnosabilities of two wide classes of networks, called regular networks and product networks, subject to certain conditions. Based on our results, we determine the strong diagnosabilities of several well-known networks, including variants of hypercubes and many others.

[1] S. B. Akers and D. Horel and B. Krishnamurthy, "The star graph: an attractive alterna- tive to the n-cube," Proceedings of the
International Conference on Parallel Processing, pp.393V400, 1987.
[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, Mar. 2000.
[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, July 2003.
[4] J. R. Armstrong and F. G. Gray, "Fault diagnosis in a boolean n cube array of multi- processors," IEEE Transactions on Computers, vol. 30, no. 8, pp. 587{590, Aug. 1981.
[5] S. Bettayeb, "On the k-ary hypercube," Theoretical Computer Science, vol. 140, no. 2, pp. 333-339, 1995.
[6] L. Bhuyan and D. P. Agrawal, "Generalized hypercube and hyperbus structures for a computer network," IEEE Transactions on Computers, vol. 33, no. 4, pp. 323-333, 1984.
[7] 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.
[8] C. P. Chang, P. L. Lai, J. J. M. Tan, and L. H. Hsu, "Diagnosability of t-connected net- works and product networks under the
comparison diagnosis model," IEEE Transactions on Computers, vol. 53, no. 12, pp. 1582{1590, Dec. 2004.
[9] 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, Apr. 2005.
[10] 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, Jan. 2006.
[11] K. Y. Chwa and L. Hakimi, "On fault identi¯cation in diagnosable systems," IEEE Transactions on Computers, vol. 30, no. 6, pp. 414{422, June 1981.
[12] W. S. Chiue and B. S. Shieh, "On connectivity of the Cartesian product of two graphs," Applied Mathematics and Computation, vol. 102, no. 2-3, pp. 129{137, July 1999.
[13] P. Cull and S. M. Larson, "The mAobius cubes," IEEE Transactions on Computers, vol. 44, no. 5, pp. 647{659, May 1995.
[14] A. T. Dahbura and G. M. Masson, "An O(n2:5) fault identi¯cation algorithm for di- anosable systems, IEEE Transactions on Computers, vol. 33, no. 6 pp. 486-492, June 1984.
[15] A. Das, K. Thulasiraman, and V. K. Agarwal, "Diagnosis of t=(t + 1)-diagnosable sys- tems, SIAM Journal on Computing, vol. 23, no. 5, pp. 895{905, May 1994.
[16] S.K. Das, S.R. A Ohring, and A.K. Banerjee, "Embeddings into hyper Petersen network: yet another hypercube-Like interconnection topology," VLSI Design, vol. 2, no. 4, pp. 335-351, 1995.
[17] K. Day and A. E. Al-Ayyoub, "The cross product of interconnection networks," IEEE Transactions on Parallel and Distributed Systems, vol. 2, no. 2, pp.109{118, Feb. 1997.
[18] K. Efe, "A variation on the hypercube with lower diameter," IEEE Transactions on Computers, vol. 40, no. 11, pp. 1312{1316, Nov. 1991.
[19] J. Fan, "Diagnosability of the mAobius cubes," IEEE Transactions on Parallel and Dis- tributed Systems, vol. 9, no. 9, pp. 923{928, 1998.
[20] H. Fugiwara and K. Kinoshita, "On the computational complexity of system diagnosis," IEEE Transactions on Computers, vol. 27, no. 10, pp. 881{885, 1978.
[21] S. L. Hakimi and A. T. Amin, "Characterization of connection assignment," IEEE Transactions on Computers, vol. 23, pp. 86{88, 1974.
[22] P. A. J. Hilbers, M. R. J. Koopman, and J. L. A. van de Snepscheut, "The twisted cube," Proceeding Parallel Architectures and Languages Europe, pp. 152{159, June 1987.
[23] 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, Feb. 1991.
[24] A. Kavianpour, "Sequential diagnosability of star graphs," Computers and Electrical Engineering, vol. 22, no. 1, pp. 37-44, 1996.
[25] S. Khanna and W. K. Fuchs, "A linear time algorithm for sequential diagnosis in hy- percubes," Journal of Parallel and Distributed Computing, vol. 26, pp. 48{53, 1995.
[26] S. Khanna and W. K. Fuchs, "A graph partitioning approach to sequential diagnosis," IEEE Transactions on Computers, vol. 46, no. 1, pp. 39{47, Jan. 1997.
[27] 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, Feb. 2005.
[28] J. K. Lee and J. T. Butler, "A characterization of t=s-diagnosability and sequential t- diagnosability in designs," IEEE Transactions on Computers, vol. 39, no. 10, pp. 1298{ 1304, Oct. 1990.
[29] J. Maeng and M. Malek, "A comparison connection assignment for self-diagnosis of multiprocessor systems," Proceeding 11th International Symposium on Fault-Tolerant Computing, pp. 173{175, 1981.
[30] F. P. Preparata, G. Metze, and R. T. Chien, "On the connection assignment problem of diagnosable systems," IEEE Transactions on Computers, vol. EC-16, pp. 448{454, Dec. 1967.
[31] F.P. Preparata and J. Vuillemin, "The Cube-connected cycles: A versatile network for parallel computation," Communications of the ACM Archive, vol. 24, pp. 300-309, 1981.
[32] 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, Nov. 1992.
[33] A. K. Somani, "Sequential fault occurrence and recon¯guration in system level diagno- sis," IEEE Transactions on Computers, vol. 39, no. 12, pp. 1472{1475, Dec. 1990.
[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, May 1987.
[35] A. K. Somani and O. Peleg, "On diagnosability of large fault sets in regular topology- based computer systems," IEEE Transactions on Computers, vol. 45, no. 8, pp. 892{903, Aug. 1996.
[36] Y. Saad and M .H . Schultz, "Topological properties of hypercubes," IEEE Transactions on Computers, vol. 37, no 7, pp. 867-872, 1988.
[37] N . E. Tzeng and S. Wei, "Enhanced hypercubes," IEEE Transactions on Computers, vol. 41, no. 11, pp. 1386-1396, 1992.
[38] D. Wang, "Diagnosability of enhanced hypercubes," IEEE Transactions on Computers, vol. 43, no. 9, pp. 1054-1061, 1994.
[39] C. L. Yang, G. M. Masson, and R. A. Leonetti, "On fault isolation and identi¯cation in t1=t1-diagnosable Systems, IEEE Transactions on Computers, vol. 35, no. 7, pp. 639-643, July 1986.
[40] 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, Apr. 2005.