Full metadata record
DC FieldValueLanguage
dc.contributor.author洪維駿en_US
dc.contributor.authorHung, Wei-Jiunnen_US
dc.contributor.author徐力行, 宋定懿en_US
dc.contributor.authorLi-Hsing Hsu, Ting-Yi Sungen_US
dc.date.accessioned2014-12-12T02:15:09Z-
dc.date.available2014-12-12T02:15:09Z-
dc.date.issued1995en_US
dc.identifier.urihttp://140.113.39.130/cdrfb3/record/nctu/#NT840394001en_US
dc.identifier.urihttp://hdl.handle.net/11536/60440-
dc.description.abstract多處理機的容錯設計已經被廣泛的應用在線上交易處理, 以及可靠度較 低的大型平行處 理系統. 多處理機系統的容錯設計主要有兩方面, 一是 處理機的容錯設計,一是連接線的容錯設計. 在不同網路架構上, 前人的 研究大都只考慮到處理機的容錯設計, 或只考慮到連接線的容錯設計方 面. 在本篇論文中, 我們則討論在 token rings 上, 處理機與連接線可 同時發生錯誤的容錯設計. 其中 "k faults" 表示處理機與連接線共有 k 個錯誤發生. 在 token ring 中設計一個最佳化的 k 容錯網路, 就等於 建造一個 k-hamiltonian圖形, 其中 k 是一個正整數, 對應著錯誤發生 的個數. 一個圖形 G 是 k-hamiltonian 圖形, 若 G-V'-E' 是一個 hamiltonian 圖形, 其中 V' 屬於 V , E' 屬於 E 且 V'+ E' <= k. 一 個有 n 個頂點的 k-hamiltonian 圖形是最佳的, 若這個 k-hamiltonian 圖形含有最少邊. 在本篇論文中, 我們建造出當 k=2,3 的時候, 最佳化 的 k-hamiltonian 圖形; 那也就是在 token rings 上的最佳化的 k 容 錯網路. Fault-tolerant multiprocessors are widely used in on-line transactionprocessing. Fault tolerance is also desirable in massive parallel systemsthat have a relatively high failure probability. Two types of failures in amultiprocessor system are of interest, processor failures and link failures.Most of previous research in designing optimal fault-tolerant topologies wascincentrated on the cases that only processor failures were allowed, or the cases that only link failures were allowed. In this paper, we discuss the caseof a combination of processor failures and link failures for token rings. By"k faults" we mean k-component faults in any combination of processor faultsand link faults. Designing an optimal k-fault-tolerant network for token rings is equivalent to constructuring an optimal k- hamiltonian graph, where k is a postive integer and corresponds to the number of faults. A graph G is k-hamiltonian if G-V'-E' is hamiltonian for any sets V' in V and E' in E withV'+E'<= k. An n-node k-hamiltonian graph is optimal if it contains the leastnumber of edges among all n-node k-hamiltonian graphs. In this paper, we are going to construct optimal k-hamiltonian graphs with k=2 and 3, which are optimal k-fault-tolerant networks with respect to token rings.zh_TW
dc.language.isozh_TWen_US
dc.subject標誌環zh_TW
dc.subject容錯zh_TW
dc.subject網路zh_TW
dc.subject平行處理zh_TW
dc.subject分散式系統zh_TW
dc.subject最佳化zh_TW
dc.subjectToken Ringsen_US
dc.subjectFault Toleranceen_US
dc.subjectNetworken_US
dc.subjectParallel Processingen_US
dc.subjectDistributed Systemen_US
dc.subjectOtimalen_US
dc.title標誌環上最佳化之 k 容錯網路設計zh_TW
dc.titleOptimal k-Fault-Tolerant Networks for Token Ringsen_US
dc.typeThesisen_US
dc.contributor.department資訊科學與工程研究所zh_TW
Appears in Collections:Thesis