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

Optimal

**Ting-Yi Sung ^{+}, Tung-Yang Ho^{++}, Chien-Ping Chang
**

and Lih-Hsing Hsu

Academia Sinica

Taipei, Taiwan 115, R.O.C.

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

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.