No Access

STRONG FAULT-TOLERANCE: PARALLEL ROUTING IN STAR NETWORKS WITH FAULTS

EUNSEUK OH

Department of Computer Science, Texas A&M University, College Station, TX 77843-3112, USA

Search for more papers by this author

and

JIANER CHEN

Department of Computer Science, Texas A&M University, College Station, TX 77843-3112, USA

Corresponding author.

Search for more papers by this author

https://doi.org/10.1142/S0219265903000763Cited by:17 (Source: Crossref)

Abstract

We study the strong fault-tolerance for the star networks. Let G be a network in which all nodes have degree d. We say that G is strongly fault-tolerant if it has the following property: let G_f be a copy of G with at most d - 2 faulty nodes removed, then for any pair of non-faulty nodes u and v in G_f, there is a container of width t between u and v, where t is the minimum of degree of u and degree of v in G_f. We show that the star networks are strongly fault-tolerant and develop an algorithm that constructs a maximum width container of nearly optimal length in a star network with faults. Our algorithm requires no prior knowledge for the faulty nodes and runs in optimal time.

This work is supported in part by NSF under Grant CCR-0000206.

References

S. B. AKERS, D. HAREL and B. KRISHNAMURTHY, The star graph: an attractive alternative to the n-cube, Proc. Intl. Conf. of Parallel Processing pp. 393–400. Google Scholar
S. B. AKERS and B. KRISHNAMURTHY, IEEE Trans. on Computers 38, 555 (1989). Crossref, Web of Science, Google Scholar
S. B. AKERS and B. KRISHNAMURTHY, The fault tolerance of star graphs, Proc. 2nd International Conference on Supercomputing pp. 270–276. Google Scholar
N. BAGHERZADEH, N. NASSIF and S. LATIFI, IEEE Trans. on Computers 42, 1398 (1993). Crossref, Web of Science, Google Scholar
G. BlRKHOFF and S. MACLANE , A Survey of Modern Algebra ( The Macmillan Company , New York , 1965 ) . Google Scholar
C. C. CHEN and J. CHEN, IEEE Trans. on Computers 46, 1293 (1997). Crossref, Web of Science, Google Scholar
C. C. CHEN and J. CHEN, IEEE Trans. Parallel, Distrib. Syst. 8, 1196 (1997). Crossref, Web of Science, Google Scholar
K. DAY and A. TRIPATHI, IEEE Trans. Parallel, Distrib. Syst. 5, 31 (1994). Crossref, Web of Science, Google Scholar
M. DIETZFELBINGER, S. MADHAVAPEDDY and I. H. SUDBOROUGH, Three disjoint path paradigms in star networks, Proc. 3rd IEEE Symposium on Parallel and Distributed Processing pp. 400–406. Google Scholar
S. FUJITA, IEEE Trans. on Computers 48, 1123 (1999). Crossref, Web of Science, Google Scholar
L. GARGANO, A. RESCIGNO and U. VACCARO, Discrete Applied Mathematics 83, 97 (1998). Crossref, Web of Science, Google Scholar
Q.-P. Gu and S. PENG, Parallel Processing Letters 6, 127 (1996). Link, Google Scholar
Q.-P. Gu and S. PENG, Information Processing Letters 67, 283 (1998). Crossref, Web of Science, Google Scholar
D. F. Hsu, IEICE Trans. Fundamentals E77-A, 668 (1994). Google Scholar
J. Jwo, S. LAKSHMIVARAHAN and S. K. DHALL, Characterization of node disjoint (parallel) path in star graphs, Proc. 5th Intl. Parallel Processing Symp. pp. 404–409. Google Scholar
S. LATIFI, Information Processing Letters 46, 143 (1993). Crossref, Web of Science, Google Scholar
N. W. Lo, B. S. CARLSON and D. L. TAO, IEEE Trans. on Computers 46, 1357 (1997). Crossref, Web of Science, Google Scholar
G. D. MARCO and U. VACCARO, Information Processing Letters 66, 321 (1998). Crossref, Web of Science, Google Scholar
E. OH and J. CHEN, Parallel routing in hypercube networks with faulty nodes, Proc. 8th International Conference on Parallel and Distributed Systems pp. 338–345. Google Scholar
M. O. RABIN, Journal of ACM 36, 335 (1989). Crossref, Web of Science, Google Scholar
A. A. RESCIGNO, Parallel Processing Letters 7, 57 (1997). Link, Web of Science, Google Scholar
A. A. RESCIGNO and U. VACCARO, Parallel Processing Letters 8, 221 (1998). Link, Web of Science, Google Scholar
S. SUR and P. K. SRIMANI, Computers Math. Applic. 25, 87 (1993). Crossref, Web of Science, Google Scholar