跳到主要內容

臺灣博碩士論文加值系統

(44.221.73.157) 您好!臺灣時間:2024/06/23 00:04
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:魏嘉成
研究生(外文):Wei, Chia-Chen
論文名稱:正規與不正規網路之(t,k)偵錯演算法之研究
論文名稱(外文):A Study of (t,k)-Diagnosis Algorithms for Regular and Irregular Networks
指導教授:謝孫源
指導教授(外文):Hsieh, Sun-Yuan
口試委員:張貿翔李新林吳邦一傅榮勝韓永楷林清池周信宏許慶賢
口試委員(外文):Mao-Hsiang ChangSing-Ling LeeBang-Ye WuJung-Sheng FuWing-Kai HonChing-Chi LinHsin-Hung ChouChing-Hsien Hsu
口試日期:2017-01-19
學位類別:博士
校院名稱:國立成功大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2017
畢業學年度:105
語文別:英文
論文頁數:62
中文關鍵詞:比較診斷模式MM*模型PMC模型條件式故障模型隨機式故障模型條件式(tk)-偵錯(tk)-偵錯多次性偵錯系統偵錯多處理器系統
外文關鍵詞:Comparison diagnosis modelMM* modelPMC modelconditional fault diagnosisrandom fault diagnosisconditional (tk)-diagnosis(tk)-diagnosissequential diagnosissystem-level diagnosismultiprocessor systems
相關次數:
  • 被引用被引用:0
  • 點閱點閱:15
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
系統偵錯是根據系統中處理器彼此之間互相測試的結果所推導出故障處理器的處理程序。偵測模型、偵測策略、偵測演算法及偵錯度是系統偵錯中的四個重要議題。本論文中,我們將重點關注對於多處理器系統上的(t,k)-偵測策略、MM*及PMC模型、(t,k)-偵錯演算法及(t,k)偵錯度。

假設一個系統中存在故障的節點個數最多t個且故障節點的分布沒有受到任何限制的條件下(或是每個節點至少會連接到一個好的節點的條件下),如果每回合至少可偵測出k個故障節點( ),則稱此系統為隨機式條件式(t,k)-可偵測(或是(t,k)-可偵測)。此外,當所有剩餘的故障節點個數少於k時,所有的故障節點都能全部被偵測到。令 為當每個節點都至少會連接到一個好的節點的條件下,圖G的連通度。令 為圖G中最大的度數,當圖G中滿足每一個節點u的鄰居節點v1都存在另一個節點u的鄰居節點v2使得節點v1與v2至少有兩個共同鄰居節點的條件下,我們證明出下列兩個結果: (1)一個正規圖G其度數為r且節點總數為N並滿足 ,則此正規圖形G為條件式 -可偵錯。(2)一個節點總數為N的不正規圖形G為條件式 -可偵錯。將上述的兩個結果應用在多處理器系統上,我們可以分別測量出擴增立方體、折疊式超立方體、平衡超立方體及交換超立方體的條件式(t,k)-偵錯度。

在PMC的模型中,我們分別探討在隨機式及條件式故障模型下超立方體的(t,k)-偵錯度。我們證明由[62]所提出對於超立方體的多次性t-偵測的演算法確實可以擴展成(t,k)-偵測演算法。對於n維的超立方體我們證明出當n為偶數時,其為隨機式 -可偵測,而當n為奇數時,其為隨機式 -可偵測,其中 。此外,利用條件式故障模型的特性,我們提出對於n維的超立方體的(t,k)-偵測演算法,並證明出其為條件式 -可偵測,而當n為奇數時,其為條件式 -可偵測。此外,在PMC的模型、隨機及條件式故障模型下,我們也改善過去的最好的t的下界值。
System-level diagnosis is a process of identifying faulty processors in a system by performing a number of tests among processors and interpreting the test results. Di-
agnosis model, diagnosis strategy, diagnosis algorithm and diagnosability are four important issues in system-level diagnosis. In this dissertation, we focus on the (t,k)-diagnosis strategy, MM* and PMC model, (t,k)-diagnosis algorithm and (t,k)-diagnosability for some multiprocessor systems.

Assume that there are at most t faulty vertices. A system is called random (t,k)-diagnosable (or conditionally (t,k)-diagnosable) if at least k faulty vertices can be
identi¯ed in each iteration under the assumption that there is no any restriction on the fault distribution (or every vertex is adjacent to at least one fault-free vertex) provided there are at most t faulty vertices, where . When the remaining the number of faulty vertices are fewer than k, all of them can also be identifed. Let (G) be the conditional vertex connectivity of G, which measures the vertex connectivity of G
according to the assumption that every vertex is adjacent to at least one fault-free vertex. Let (G) be the maximum degrees of the given graph G. When a graph
G satisfes the condition that for each neighbor v1 of vertex u in G there is another neighbor v2 of u such that v1 and v2 have at least two common neighbors in G, we
show the following two results: 1) An r-regular network G containing N vertices is conditionally -diagnosable. By applying the above results to multiprocessor systems, we can measure conditional (t, k)-diagnosabilities for augmented cubes, folded hypercubes, balanced
hypercubes, and exchanged hypercubes.

Under the PMC model, we consider the (t,k)-diagnosability of a hypercube under
the random fault model and conditional fault model, respectively. We show that the
sequential t-diagnosis algorithm for hypercube proposed by [62] can be extended to the (t,k)-diagnosis algorithm for hypercube and we show that the n-dimensional hyper-cubes are random -diagnosable if n is even, and random -diagnosable if n is odd, where . Moreover, we propose a conditional (t,k)-diagnosis algorithm for hypercubes by using some property of conditional fault model and show that the n-dimensional hypercubes are conditional -diagnosable if n is even, and conditional -diagnosable if n is odd.
Furthermore, under the PMC model, our results improve the previous best low bounds on t under the random and conditional fault models, respectively.
1 Introduction <1>
1.1 Motivation and overview <1>
1.2 Preview of this dissertation <3>
Preliminaries <5>
2.1 Basic De¯nitions and Notation <5>
2.2 Interconnection Networks <7>
2.3 Diagnosis models <8>
2.3.1 MM* model <9>
2.3.2 PMC model <10>
2.4 Diagnosis strategies <10>
2.5 Fault models <12>
3 Conditional (t, k)-Diagnosis in Regular and Irregular Graphs Under the Comparison Diagnosis Model <14>
3.1 Properties for Comparison Diagnosis Model <14>
3.2 (t; k)-Diagnosabilities of Regular and Irregular Graphs <16>
3.3 Applications to Multiprocessor Systems <21>
4 Random and Conditional (t, k)-Diagnosis on Hypercubes Under the PMC Model <31>
4.1 Properties for PMC Model <31>
4.2 Random (t, k)-Diagnosis <35>
4.3 Conditional (t, k)-Diagnosis <40>
5 Concluding Remarks <49>
5.1 Summary <49>
5.2 Further research <50>
Bibliography <51>
[1] S. B. Akers, D. Horel, and B. Krishnamurthy, The star graph: an attractive
alternative to the n-cube," International Conference on Parallel Processing, pp.
1249{1268, 1987.
[2] S. B. Akers and B. Krishnamurthy, A group-theoretic model for symmetric in-
terconnection networks," IEEE Transactions on Computers, vol. 38, no. 4, pp.
555{566, 1989.
[3] F. J. Allan, T. Kameda and S. Toida, Approach to the diagnosability analysis of
a system," IEEE Transaction on Computers, vol. 25, pp. 1040{1042, 1975.
[4] T. Araki and Y. Shibata, Diagnosability of networks by the cartesian product,"
IEICE Transactions on Fundamentals of Electronics Communications and Com-
puter Science, vol. 83, no. 3, pp. 465{470, 2000.
[5] T. Araki and Y. Shibata, Diagnosability of butter°y networks under the com-
parison approach," IEICE Transactions on Fundamentals of Electronics Commu-
nications and Computer Science, vol. E85-A, no. 5, pp. 1152{1160, 2002.
[6] 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.
[7] J. R. Armstrong and F. G. Gray, Fault diagnosis in a boolean n-cube array of
microprocessors," IEEE Transactions on Computers, vol. 30, no. 8, pp. 587{590,
1981.
51
[8] M. Asim, H. Mokhtar, and M. Merabti, A cellular approach to fault detection
and recovery in wireless sensor networks," in Proceedings of the Third International
Conference on Sensor Technologies and Applications (SENSOR-COMM'09), pp.
352{357, 2009.
[9] F. Barsi, F. Grandoni and P. Maestrini, A theory of diagnosability in digital
systems," IEEE Transactions on Computers, vol. 25, pp. 585{593, 1976.
[10] E. R. Berlekamp, Algebraic Coding Theory, (revised), Aegean Park Press, Laguna
Hills, 1984.
[11] P. Berman and A. Pelc, Distributed probabilistic fault diagnosis for multiproces-
sor systems," Proceeding of IEEE Computer Society 20th International Symposium
of Fault-Tolerant Computing, pp. 340{346, 1990.
[12] D. M. Blough, G. F. Sullivan and G. M. Masson, Almost certain diagnosis for in-
termittently faulty systems," Proceeding of IEEE CS 18th International Sympsium
on Fault-Tolerant Computing, pp. 260{265, 1988.
[13] D. M. Blough, G. F. Sullivan, and G. M. Masson, Fault diagnosis for sparsely
interconnected multiprocessor systems," Proceeding of IEEE Computer Society
19th International Sympsium on Fault-Tolerant Computing, pp. 62{69, 1989.
[14] D. M. Blough and A. Pelc, Reliable diagnosis and repair in constant-degree mul-
tiprocessor systems," Proceeding of IEEE Computer Society 20th International
Sympsium on Fault-Tolerant Computing, pp. 316{323, 1990.
[15] D. M. Blough, G. F. Sullivan and G. M. Masson, E±cient diagnosis of multi-
processor systems under probabilistic models," IEEE Transactions on Computers,
vol. 41, pp. 1126{1136, 1992.
[16] D. M. Blough, G. F. Sullivan and G. M. Masson, Intermittent fault diagnosis in
multiprocessor system," IEEE Transactions on Computers, vol. 41, pp. 1430{1441,
52
1992.
[17] 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.
[18] G. Y. Chang, G. H. Chen, and G. J. Chang, (t; k)-Diagnosis for matching com-
position networks," IEEE Transactions on Computers, vol. 55, no. 1, pp. 88{92,
2006.
[19] 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.
[20] G. Y. Chang, G. H. Chen, and G. J. Chang, (t; k)-Diagnosis for matching com-
position networks under the MM* model," IEEE Transactions on Computers, vol.
56, no. 1, pp. 73{79, 2007.
[21] G. Y. Chang, Conditional (t; k)-Diagnosis under the PMC Model," IEEE Trans-
actions on Parallel and Distributed Systems, vol. 22, no. 11, pp. 1797{1803, 2011.
[22] C. A. Chen and S. Y. Hsieh (t; k)-Diagnosis For Component-Composition Graphs
Under the MM* Model," IEEE Transactions on Computers, vol. 60, no. 12, pp.
1704{1717, 2011.
[23] C. A. Chen and S. Y. Hsieh, Component-composition graphs: (t,k)-diagnosability
and its application," IEEE Transactions on Computers, vol. 62, no. 2, pp. 1097{
1110, 2013.
[24] C. A. Chen, G. Y. Chang and S. Y. Hsieh, Conditional (t; k)-diagnosis in graphs
by using the comparison diagnosis model," IEEE Transactions on Computers, vol.
64, no. 6, pp. 1622-1632, June 2015.
53
[25] A. Caruso, S. Chessa, P. Maestrini, and P. Santi, Diagnosability of Regular Sys-
tems," J. Algorithms, vol. 1, no. 1, pp. 1{12, 2002.
[26] S. Chessa and P. Santi, Crash faults identi¯cation in wireless sensor networks,"
Computer Communications, vol. 25, no. 14, pp. 1273-1282, 2002.
[27] S. A. Choudum and V. Sunitha, Augmented cubes," Networks, vol. 40, no. 2, pp.
71{84, 2002.
[28] K. Y. Chwa and S. L. Hakimi, On fault identi¯cation in diagnosable systems,"
IEEE Transactions on Computers, vol. 30, no. 6, pp. 414{422, 1981.
[29] K. Y. Chwa and S. L. Hakimi, Schemes for fault tolerant computing: a compari-
son of modularly redundant and t-diagnosable systems," Information and Control,
vol. 49, pp. 212{238, 1981.
[30] P. Cull and S.M. Larson, The MÄobius cubes," IEEE Transactions on Computers,
vol. 44, no. 5, pp. 647{659, May 1995.
[31] A. T. Dahabura and G. M. Masson, An O(n2:5) fault identi¯cation algorithm
for diagnosable systems," IEEE Transactions on Computers, vol. C-33, no. 6, pp.
486{492, 1984.
[32] A. T. Dahbura, System-level diagnosis: a perspective for the third decade,"
Concurrent Computation: Algorithms, Arhcitectures, Technologies. New York:
Plenum 1988.
[33] A. T. Dahabura and G. M. Masson, Improved diagnosability algorithm," IEEE
Transactions on Computers, vol. 40, no. 2, pp. 143{153, 1991.
[34] A. Das, K. Thulasiraman, V. K. Agarwal and K. B. Lakshmanan, Multiprocessor
fault diagnosis under local constraints," IEEE Transactions on Computers, vol.
42, no. 8, pp. 984{988, 1993.
54
[35] A. El-Amawy, S. Lati¯, Properties and performance of folded hypercubes," IEEE
Transactions on Parallel and Distributed Systems, vol. 2, no. 1, pp. 31{42, 1991.
[36] K. Efe, A variation on the hypercube with lower diameter," IEEE Transactions
on Computers, vol. 40, no. 11, pp. 1312{1316, Nov. 1991.
[37] A. H. Esfahanian, Generalized measures of fault tolerance with application to N-
cube networks, IEEE Transactions on Computers, vol. 38, no. 11, pp. 1586{1591,
1989.
[38] J. Fan, Diagnosability of the mÄobius cubes," IEEE Transactions on Parallel and
Distributed Systems, vol. 9, no. 9, pp. 923{928, 1998.
[39] 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.
[40] 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.
[41] W. Feller, Stirling's formula," in: An Introduction to Probability Theory and Its
Applications, 3rd Edition, vol. 1, Wiley, New York, pp. 50{53, 1968 (chapter 2.9).
[42] A. D. Friedman and L. Simoncini, System-level fault diagnosis," Computer, vol.
13, no. 3, pp. 47{53, 1980.
[43] H. Fujiwara and K. Kinoshita, On the computational complexity of system diag-
nosis," IEEE Transactions on Computers, vol. C-27, no. 10, pp. 881{885, 1978.
[44] A. Ghafoor, A class of fault-tolerant multiprocessor networks," IEEE Transac-
tions on Reliability, vol. 38, no. 1, pp. 5{15, 1989.
[45] A. Ghafoor, Partitioning of even networks for improved diagnosability," IEEE
Transactions on Reliability, vol. 39, no. 3, pp. 281{286, 1990.
55
[46] S. L. Hakimi and A. T. Amin, On the computational complexity of system diag-
nosis," IEEE Transactions on Computers, vol. 23, no. 1, pp. 86{88, 1974.
[47] F. Harary, M. Livingston, Independent domination in hypercubes," Applied
mathematics letters, vol. 6, pp. 27{28, 1993.
[48] P. A. J. Hilbers, M. R. J. Koopman, and J. L. A. va_a de Snepscheut, The twisted
cubes," Proc. Parallel Architecture and Language Europe, pp. 152{159, June 1987.
[49] W. S. Hong and S. Y. Hsieh, Strong diagnosability and conditional diagnosability
of augmented cubes under the comparison diagnosis model," IEEE Transactions
on Reliability, vol. 61, no. 1, pp. 140{148, March 2012.
[50] S. H. Hosseini, J. G. Kuhl and S. M. Reddy, Diagnosis algorithm for distributed
computing systems," IEEE Transactions on Computers, vol. 33, pp. 223-233, 1984.
[51] 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.
[52] J. Hwang, T. He, and Y. Kim, Secure localization with phantom node detection,"
Ad Hoc Networks, vol. 6, no. 7, pp. 1031{1050, 2008.
[53] 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.
[54] A. Kavianpour and K. H. Kim, Diagnosabilities of hypercubes under the pes-
simistic one-step diagnosis strategy," IEEE Transactions on Computers, vol. 40,
no. 2, pp. 232{237, 1991.
[55] 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.
56
[56] 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.
[57] A. Kavianpour, Sequential diagnosability of star graphs," Computers & Electrical
Engineering, vol. 22, no. 1, pp. 37{44, 1996.
[58] 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.
[59] S. Khanna and W. K. Fuchs, A graph partitioning approach to sequential diag-
nosis," IEEE Transactions on Computers, vol. 46, no. 1, pp. 39{47, 1997.
[60] J. G. Kuhl and S. M. Reddy, Fault diagnosis in fully distributed systems,"
Proceedings of IEEE Computer Society 11th International Sympsium on Fault-
Tolerant Computing, pp. 100{105, 1981.
[61] S. P. Kuo, H. J. Kuo, and Y. C. Tseng, The beacon movement detection problem
in wireless sensor networks for localization applications," IEEE Transactions on
Mobile Computing, vol. 8, no. 10, pp. 1326{1338, Oct. 2009.
[62] C. L. Kuo, M. J. Yang, Y. M. Chang, and Y. M. Yeh, High diagnosability of a
sequential diagnosis algorithm in hypercubes under the PMC model," Journal of
Supercomputing, vol. 61, no. 3, pp. 1116{1134, Sep. 2012.
[63] P. L. Lai, 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.
[64] 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, no. 8, pp. 1064{1069, 2004.
57
[65] P. L. Lai, A systematic algorithm for identifying faults on hypercube-like net-
works under the comparison model," IEEE Transactions on Reliability, vol. 61,
no. 2, pp. 452{459, Jun. 2012.
[66] P. L. Lai, M. Y. Chiu, and C. H. Tsai, Three round adaptive diagnosis in hier-
archical multiprocessor systems," IEEE Transactions on Reliability, vol. 62 , no.
3, pp. 608{617, Sep. 2013.
[67] X. J. Li, and J. M. Xu, Generalized measures of fault tolerance in exchanged
hypercubes," Information Processing Letters, vol. 113, no. 14{16, pp. 533{537,
July 2013.
[68] C. K. Lin, J. J. M. Tan, L. H. Hsu, E. Cheng, and L. Lipt¶ak, Conditional diagnos-
ability 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.
[69] C. K. Lin, Y. H. Teng, J. J. M. Tan, and L. H. Hsu, Local diagnosis algorithms
for multiprocessor systems under the comparison diagnosis model," IEEE Trans-
actions on Reliability, vol. 62, no. 4, pp. 800{810, Dec. 2013.
[70] P. K. K. Loh, W. J. Hsu, and Y. Pan, The exchanged hypercube," IEEE Trans-
actions on Parallel and Distributed Systems, vol. 16, no. 9, pp. 866{874, 2005.
[71] M. Ma, G. Liu, and J. M. Xu, The super connectivity of augmented cubes,"
Information Processing Letters vol. 106, pp. 59{63, 2008.
[72] S. Mallela and G. M. Masson, Diagnosable systems for intermittent fault," IEEE
Transactions on Computers, vol. 27, pp. 460{470, 1978.
[73] M. Ma, and L. Zhu, The super connectivity of exchanged hypercubes," Informa-
tion Processing Letters vol. 111, pp. 360{364, 2011.
58
[74] M. Malek, A comparison connection assignment for diagnosable of multiproces-
sor systems," in Proceedings of the 7th International Symposium on Computer
Architecture, pp. 31{36, 1980.
[75] J. Maeng and M. Malek, A comparison connection assignment for self-diagnosis
of multiprocessor systems," in Proceeding 11th International Symposium on Fault
Tolerant Computing, pp. 173{175, 1981.
[76] G. G. L. Meyer, A fault diagnosis algorithm for asymmetric modular architec-
tures," IEEE Transactions on Computers, vol. 30, pp.81{83, 1981.
[77] A. Pelc, Undirected graph models for system-level fault diagnosis," IEEE Trans-
actions on Computers, vol. 40, pp. 1271{1276, 1991.
[78] 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.
[79] Q. Zhu, J.M. Xu, Hou, M. Xu, On reliability of the folded hypercubes," Infor-
mation Sciences: An international Journal, vol. 177, no. 8, pp. 1782{1788, 2007.
[80] H. Robbins, A remark of Stirling's formula," American Mathematical Monthly,
vol. 62, pp. 26{29, 1955.
[81] J. D. Russell and C. R. Kime, System fault diagnosis: masking, exposure, and
diagnosability without repair," IEEE Transactions on Computers, vol. C-24, PP.
1156{1161, 1975.
[82] Y. Saad and M.H. Schultz, Topological properties of hypercubes," IEEE Trans-
actions on Computers, vol. 37, no. 7, pp. 867{872, July 1988.
[83] A. Sengupta and A. T. Danbura, On self-diagnosable multiprocessor systems:
diagnosis by the comparison approach," IEEE Transactions on Computers, vol.
41, no. 11, pp. 1386{1396, 1992.
59
[84] 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.
[85] A. K. Somani and V. K. Agarwal, Distributed syndrome decoding for regular in-
terconnected structure," Proceeding of IEEE Computer Society 19th International
Sympsium on Fault-Tolerant Computing, pp. 70{77, 1989.
[86] A. K. Somani, V. K. Agarwal and D. Avis, On the complexity of single fault set
diagnosability and diagnosis problems," IEEE Transactions on Computers, vol.
38, pp. 195{201, 1989.
[87] 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{902, 1996.
[88] G. Sullivan, A polynomial time algorithm for fault diagnosability," Proceedings
of the 11th Annual Symposium on Computer Architecture, pp. 148{156, 1984.
[89] G. Sullivan, An O(t3+jEj) fault identi¯cation algorithm for diagnosable systems,"
IEEE Transactions on Computers, vol. 37, pp. 388{397, 1988.
[90] T.M. Thompson, From error-correcting codes through sphere packings to simple
groups," Mathematical Association of America, Washington, 1983.
[91] G. J. M. vanWee, Improved sphere bounds on the covering radius of codes," IEEE
Transactions on Information Theory, vol. 34, no. 2, pp. 237{245, Mar. 1988.
[92] D. Wang, Diagnosability of enhanced hypercubes," IEEE Transactions on Com-
puters, vol. 43, no. 9, pp. 1054{1061, 1994.
[93] D. B.West: Introduction to Graph Theory (Second Edition), Prentice Hall, Upper
Saddle River. (2001)
60
[94] D. Wang, Diagnosability of hypercubes and enhanced hypercubes under the com-
parison diagnosis model," IEEE Transactions on Computers, vol. 48, no. 12, pp.
1369{1374, 1999.
[95] J. Wu, K. Huang, The balanced hypercube: a cube-based system for fault-
tolerant applications," IEEE Transactions on Computers, vol. 46, no. 4, pp. 484{
490, 1997.
[96] J. Xu and S. Z. Huang, Sequentially t-diagnosable system: a characterization and
its applications," IEEE Transactions on Computers, vol. 44, no. 2, pp. 340{345,
1995.
[97] J. M. Xu, Q. Zhu, X. M. Hou and T. Zhou, On restricted connectivity and extra
connectivity of hypercubes and folded hypercubes,"J. Shanghai Jiaotong Univ.
(Sci.) E-10, no. 2, pp. 208{212, 2005.
[98] M. C. Yang, Super connectivity of balanced hypercubes," Applied Mathematics
and Computation, vol. 219, no. 3, pp. 970{975, 2012.
[99] X. Yang, A linear time fault diagnosis algorithm for hypercube multiprocessors
under the MM* comparison model," in: Proceedings of the 12th Asian Test Sym-
posium, pp. 50{57, 2003.
[100] T. L. Ye and S. Y. Hsieh, A scalable comparison-based diagnosis algorithm for
hypercube-like networks," IEEE Transactions on Reliability, vol. 62, number 4,
pp. 789{799, Dec. 2013.
[101] 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.
[102] J. Zhao, F. J. Meyer, N. Park, and F. Lombardi, Sequential diagnosis of proces-
sor array systems," IEEE Transactions on Reliability, vol. 53, no. 4, pp. 487{498,
61
2004.
[103] J. Zheng, S. Lati¯, 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.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊