[Previous [1] [2] [3] [4] [5] [6] [7] [8]

Journal of Inforamtion Science and Engineering, Vol. 16, No. 3, pp. 381-390 (May 2000)

Optimal k-Fault-Tolerant Networks for Token Rings*

Ting-Yi Sung+, Tung-Yang Ho++, Chien-Ping Chang
and Lih-Hsing Hsu
+Institute of Information Science
Academia Sinica
Taipei, Taiwan 115, R.O.C.
++Department of Industrial Engineering and Management
TaHwa Institute of Technology
Hsinchu, Taiwan 307, R.O.C.
Institute of Computer and Information Science
National Chiao Tung University
Hsinchu, Taiwan 300, R.O.C.

Fault-tolerant multiprocessors are widely used in on-line transaction processing. Fault tolerance is also desirable in massively parallel systems that have a relatively high failure probability. Two types of failures in a multiprocessor system are of interest, processor failures and link failures. Most of the previous research in designing optimal fault-tolerant topologies was concentrated on the cases that only processor failures were allowed [1, 2, 4, 6], or the cases that only link failures were allowed [3, 5, 7, 8, 11-15]. In this paper, we discuss the case of a combination of processor failures and link failures for token rings. By k faults?we mean k-component faults in any combination of processor faults and link faults. Designing an optimal k-fault-tolerant network for token rings is equivalent to constructing an optimal k-hamiltonian graph, where k is a positive integer and corresponds to the number of faults. A graph G is k-hamiltonian if G - F is hamiltonian for any sets F V E with |F| < k. An n-node k-hamiltonian graph is optimal if it contains the least number of edges among all n-node k-hamiltonian graphs. In this paper, we construct optimal k-hamiltonian graphs with k = 2 and 3, which are optimal k-fault-tolerant networks with respect to token rings.

Keywords: distributed systems, fault tolerance, hamiltonian cycles, hamiltonian graphs, processor failures, link failures, token rings

Full Text () Retrieve PDF document (200005_05.pdf )

Received October 1, 1997; revised March 25, 1998; accepted May 1, 1998.
Communicated by Shing-Tsaan Huang.
*This work was supported in part by the National Science Council of the Republic of China under grant NSC87-2213-E009-100.