偵錯性(diagnosability)，這概念長久以來一直是去估量多處理器系統可靠性的一個重要指標。如一個系統具有t診斷能力(t-diagnosable)，即表示當系統發生錯誤的節點數不超過t時，則該系統保證可以將所有的錯誤節點標示出來。更進一步地，當一個系統具有強t診斷能力(strongly t-diagnosable)時，則當錯誤節點數不超過t+1時，系統保證可將所有的錯誤節點標示出來，只有一個情況會例外，就是該系統中存在一個節點，而與其相鄰的節點皆同時發生錯誤的情況。在論文中，我們去研究一種互連網路架構，稱為配對構成網路(Matching Composition Network，簡稱MCN)，在比較診斷模式(Comparison diagnosis model)下的強診斷能力，進而發現滿足一些條件的配對構成網路，其所具備的強診斷能力；同時，我們也提出一個充分且必要的條件可用來驗證一個系統是否具有強t診斷能力。以我們的結果為基礎，我們證明了下面幾個為人所熟知的互連網路架構，超立方體(hypercube)、交錯立方體(crossed cube)、莫氏立方體(Mobius cube)、雙扭超立方體(twisted cube)和局部雙扭超立方體(locally twisted cube)，當它們的維度是n時，皆具有強n診斷能力。

The notion of diagnosability has long played an important role in measuring the reliability of multiprocessor systems. Such a system is t-diagnosable if all faulty nodes can be identified without replacement when the number of faults does not exceed t, where t is some positive integer. Furthermore, a system is strongly t-diagnosable if it is almost (t+1)-diagnosable, except for the case where a node's neighbors are all faulty. In this thesis, we investigate a class of interconnection networks, called Matching Composition Networks (MCNs), and show that they are strongly diagnosable system under the comparison diagnosis model. We also propose some conditions for verifying whether MCNs are strongly diagnosable. Based on our results, we show that, subject to certain conditions, n-diagnosable and n-connected, several well-known interconnection networks are strongly n-diagnosable, including the n-dimensional hypercube, the n-dimensional crossed cube, the n-dimensional Mobius cube, the n-dimensional twisted cube, and the n-dimensional locally twisted cube.

[1] 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.
[2] 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.
[3] 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, Aug. 1981.
[4] C. P. Chang, P. L. Lai, J. J. M. Tan, and L. H. Hsu, "Diagnosability of t-connected networks and product networks under the comparison diagnosis model," IEEE Transactions on Computers, vol. 53, no. 12, pp. 1582-1590, Dec. 2004.
[5] 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.
[6] 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.
[7] G. Y. Chang, G. H. Chen, and G. J. Chang, "(t; k)-Diagnosis for matching composition networks under the MM* model," accepted and to appear in IEEE Transactions on Computers.
[8] P. Cull and S. M. Larson, "The mobius cubes," IEEE Transactions on Computers, vol. 44, no. 5, pp. 647-659, May 1995.
[9] K. Y. Chwa and L. Hakimi, "On fault identification in diagnosable systems," IEEE Transactions on Computers, vol. 30, no. 6, pp. 414-422, June 1981.
[10] A. Das, K. Thulasiraman, and V. K. Agarwal, "Diagnosis of t/(t + 1)-diagnosable systems," SIAM Journal on Computing, vol. 23, no. 5, pp. 895-905, May 1994.
[11] K. Efe, "A variation on the hypercube with lower diameter," IEEE Transactions on Computers, vol. 40, no. 11, pp. 1312-1316, Nov. 1991.
[12] J. Fan, "Diagnosability of the mobius cubes," IEEE Transactions on Parallel and Distributed Systems, vol. 9, no. 9, pp. 923-928, Sep. 1998.
[13] 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, July 2002.
[14] 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.
[15] 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.
[16] 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.
[17] 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.
[18] P. Kulasinghe, "Connectivity of the crossed cube," Information Proceeding Letters, vol. 61, no. 4, pp. 221-226, Feb. 1997.
[19] P. L. Lai, J. J. M. Tan, C. H. Tsai, and L. H. Hsu, "Diagnosability of the matching composition network under the comparison diagnosis model," IEEE Transactions on Computers, vol. 53, no. 8, pp. 1064-1069, Aug. 2004.
[20] 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.
[21] 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.
[22] 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.
[23] 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.
[24] W. Najjar and J. L. Gaudiot, "Network Resilience: A measure of Network Fault Tolerance," IEEE Transactions on Computers, vol. 39, no. 2, pp. 174-181, Feb. 1990.
[25] 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.
[26] A. K. Somani, "Sequential fault occurrence and reconfiguration in system level diagnosis," IEEE Transactions on Computers, vol. 39, no. 12, pp. 1472-1475, Dec. 1990.
[27] 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.
[28] 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-903, Aug. 1996.
[29] D.Wang, "Diagnosability of hypercubes and enhanced hypercubes under the comparison diagnosis model," IEEE Transactions on Computers, vol. 48, no. 12, pp. 1369-1374, Dec. 1999.
[30] C. L. Yang, G. M. Masson, and R. A. Leonetti, "On fault isolation and identification in t1/t1-diagnosable Systems," IEEE Transactions on Computers, vol. 35, no. 7, pp. 639-643, July 1986.
[31] 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.