| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Reducing the Number of Sequential Diagnosis Iterations in Hypercubes
January 2004 (vol. 53 no. 1)
pp. 89-92
Abstract—In this note, we use a vertex-isoperimetric inequality to show that the number of test and repair iterations needed to perform sequential diagnosis of d-dimensional hypercubes is upper bounded by d-r, where r\in\Theta(d). This result improves the best bound of d test and repair iterations previously known. Numerical evaluation has shown that the actual value of r ranges from 0.16d to 0.31d.
[1] 89 A. Bjorklund, Optimal Adaptive Fault Diagnosis of Hypercubes Proc. Scandinavian Workshop Algorithm Theory (SWAT 2000), pp. 527-534, 2000.[2] A. Caruso, S. Chessa, P. Santi, and P. Maestrini, Diagnosability of Regular Systems J. Algorithms, vol. 45, no. 2, pp.126-143, Nov. 2002.[3] T.H. Cormen, C.E. Leiserson, and R.L. Rivest, Introduction to Algorithms. MIT Press, 1990.[4] C. Feng, L.N. Bhuyan, and F. Lombardi, Adaptive System-Level Diagnosis for Hypercube Multiprocessors IEEE Trans. Computers, vol. 45, no. 10, pp. 1157-1170, Oct. 1996.[5] S.L. Hakimi and A.T. Amin, Characterization of Connection Assignment of Diagnosable Systems IEEE Trans. Computers, vol. 23, no.1, pp. 86-88, Jan. 1974.[6] S. Huang, J. Xu, and T. Chen, "Characterization and Design of Sequentially t-Diagnosable Systems," Proc. IEEE CS 19th Int'l Symp. Fault-Tolerant Computing, pp. 554-559, 1989.[7] G.O.H. Katona, The Hamming-Sphere Has Minimum Boundary Studia Scientarum Mathematicarum Hungarica, vol. 10, pp. 131-140, 1975.[8] A. Kavianpour and K.H. Kim, "A Comparative Evaluation of Four Basic System-Level Diagnosis Strategies for Hypercubes," IEEE Trans. Reliability, vol. 41, pp. 26-37, Mar. 1992.[9] S. Khanna and W.K. Fuchs, A Graph Partitioning Approach to Sequential Diagnosis IEEE Trans. Computers, vol. 46, no. 1, pp. 39-47, Jan. 1997.[10] S. Khanna and W.K. Fuchs, A Linear Time Algorithm for Sequential Diagnosis in Hypercubes J. Parallel and Distributed Computing, vol. 26, pp. 48-53, Apr. 1995.[11] E. Kranakis and A. Pelc, Better Adaptive Diagnosis of Hypercubes IEEE Trans. Computers, vol. 49, no. 10, pp. 1013-1020, Oct. 2000.[12] I. Leader, Discrete Isoperimetric Inequalities AMS Proc. Symposia Applied Math., vol. 44, pp. 57-80, 1991.[13] P. Maestrini and C.L. Liu, On the Sequential Diagnosability of a Class of Digital Systems IEEE Proc. 11th Int'l Symp. Fault-Tolerant Computing, pp. 112-115, 1981.[14] F.P. Preparata, G. Metze, and R.T. Chien, On the Connection Assignment Problem of Diagnosable Systems IEEE Trans. Computers, vol. 16, pp. 848-854, Dec. 1967.
Index Terms:
Massively parallel systems, system-level diagnosis, sequential diagnosis, hypercubes.
Citation:
Paolo Santi, Stefano Chessa, "Reducing the Number of Sequential Diagnosis Iterations in Hypercubes," IEEE Transactions on Computers, vol. 53, no. 1, pp. 89-92, Jan. 2004, doi:10.1109/TC.2004.1255796
