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.