|
Published Articles >> Table of Contents >> Abstract
January 2004 - (Vol. 53, No. 1)
pp. 89-92
Reducing the Number of Sequential Diagnosis Iterations in Hypercubes
Paolo Santi
Stefano Chessa
Full Article Text:
   
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/TC.2004.1255796
Send link to a friend
| 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.
|
 References
|
[1] 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.
|
 Additional Information
|
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
|
|
RSS Feed