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.

所屬典藏

期刊論文
顯示完整詮釋資料 統計資料

引用此條目

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

BibTeX RIS

引用文字依 APA 第 7 版格式自動產生,使用前請再核對。

分享

永久網址:https://ir.lib.nycu.edu.tw/handle/11536/30562