標題: Optimal k-fault-tolerant networks for token rings
作者: Sung, TY
Ho, TY
Chang, CP
Hsu, LH
資訊工程學系
Department of Computer Science
關鍵字: distributed systems;fault tolerance;hamiltonian cycles;hamiltonian graphs;processor failures;link failures;token rings
公開日期: 1-May-2000
摘要: 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 subset of V boolean OR E with F less than or equal to 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.
URI: http://hdl.handle.net/11536/30562
ISSN: 1016-2364
期刊: JOURNAL OF INFORMATION SCIENCE AND ENGINEERING
Volume: 16
Issue: 3
起始頁: 381
結束頁: 390
Appears in Collections:Articles