Optimal k-fault-tolerant networks for token rings
檔案
本條目沒有附加檔案。
日期
2000-05-01
類型
系所
期刊名稱
JOURNAL OF INFORMATION SCIENCE AND ENGINEERING
卷期與頁次
第 16 卷第 3 期,頁 381–390
ISSN
1016-2364
語言
英文
摘要
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.
關鍵詞
distributed systemsfault tolerancehamiltonian cycleshamiltonian graphsprocessor failureslink failurestoken rings所屬典藏
期刊論文引用此條目
Sung, T., Ho, T., Chang, C., & Hsu, L. (2000). Optimal k-fault-tolerant networks for token rings. JOURNAL OF INFORMATION SCIENCE AND ENGINEERING, 16(3), 381–390. https://ir.lib.nycu.edu.tw/handle/11536/30562
引用文字依 APA 第 7 版格式自動產生,使用前請再核對。
分享
永久網址:https://ir.lib.nycu.edu.tw/handle/11536/30562