(3.238.240.197) 您好!臺灣時間:2021/04/12 02:27
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:林敏勝
研究生(外文):Min-Sheng Lin
論文名稱:分散式計算系統中程式可靠度的分析與研究
論文名稱(外文):Program Reliability Analysis in Distributed Computing Systems
指導教授:陳登吉陳登吉引用關係
指導教授(外文):Deng-Jyi Chen 
學位類別:博士
校院名稱:國立交通大學
系所名稱:資訊工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:1994
畢業學年度:82
語文別:英文
論文頁數:84
中文關鍵詞:可靠度分散式計算系統分散式程式可靠度
外文關鍵詞:reliabilityistributed computing systemdistributed program reliability
相關次數:
  • 被引用被引用:1
  • 點閱點閱:120
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:1
對於分散式計算系統的可靠度,其決定於通訊網路線的可靠度和節點的可
靠度,並且和其資源(例如:程式,檔案)的分散情形也有關係。這一篇
論文提出了一個演算法,此演算法是用來計算假設節點是完全可靠之下的
分散式計算系統之可靠度。此演算法稱為FREA (Fast Reliability
Evaluation Algorithm),是以factoring定理為基礎,並使用了許多可靠
度的化簡技巧。我們同時提出了兩個演算法用來計算假設節點不是完全可
靠之下的分散式計算系統之可靠度。第一個演算法稱為SM(Symbolic
Method),是以符號為主的兩次處理計算。第二個演算法稱為FM(
Factoring Method),同時對通訊網路線和節點做factoring的動作。和其
他的演算法作比較,由其結果可知我們所提的演算法對於計算大型分散式
計算系統的可靠度較有效率。為了縮小此問題的大小,我們提出了對於分
散式計算系統一般化的化簡方法。這些化簡方法可以很有效的縮小分散式
計算系統的大小,如此也就加快了計算可靠度的時間。這篇論文也證明了
此計算可靠度的問題是一個NP-hard問題,即使對於序列─平行網路,2─
樹網路,樹狀網路,星狀網路也是NP-hard問題。我們同時也提出了兩個
演算法,用來分別計算線性和環狀網路的可靠度,並且可以在polynomial
的時間之內得到答案。
The reliability of a distributed computing system depends on
the reliability of its communication links and nodes, as well
as on the distribution of its resources, such as programs and
data files. This thesis presents an algorithm for computing the
reliability of a distributed computing system with perfect
nodes. The algorithm, called FREA (Fast Reliability Evaluation
Algorithm), is based on the factoring theorem employing several
reliability-preserving reductions techniques. We also propose
two algorithms for computing the reliability of a distributed
computing system with imperfect nodes. Algorithm one, called SM
(Symbolic Method), is based on a symbolic approach that
consists two passes of computation. Algorithm two, called FM
(Factoring Method), employs a general factoring technique on
both nodes and edges. Comparisons with existing methods show
the effectiveness of the proposed algorithms for large
distributed computing systems. In order to reduce the size of
the problem, we will propose several general reduction methods
for computing the reliability of distributed computing systems.
These reduction methods can dramatically reduce the size of a
distributed computing system, and therefore speed up the
reliability computation. This thesis also shows that solving
this reliability problem is NP-hard even when a distributed
computing system is restricted to a series-parallel, a 2-tree,
a tree, or star structure. Two polynomial-time algorithms are
proposed for computing the reliability of a distributed program
which runs on a linear and a ring distributed computing
systems, respectively.
COVER
ABSTRACT IN CHINESE
ABSTRACT
ACKNOWLEDGMENTS
TABLE OF CONTENTS
LIST OF FIGURES
LIST OF TABLES
1 INTRODUCTION
1.1 Distributed Computing Systems
1.2 Motivation
1.3 Reliability Measures of Distributed Computing Systems
1.3.1 Source-to-Multiple-Terminal Reliability
1.3.2 Survivability Index
1.3.3 Multiterminal Reliability
1.3.4 K-terminal Reliability
1.4 Problem Statement
1.5 Notation and Definitions
1.6 Organization of the Thesis
2 RELATED WORKS
2.1 MFST Algorithm
2.2 FARE Algorithm
2.3 FST-SPR Algorithm
3 THE DISTRIBUTED PROGRAM RELIABILITY ANALYSIS WITH PEREECT NODES
3.1 The Generalized Factoring Theorem
3.2 Basic Reduction Methods
3.3 FREA Algorithm
4 THE DISTRIBUTED PROGRAM REELLABILITY ANALYSIS WITH IMPERFECT NODES
4.1 SM Algorithm
4.2 FM Algorithm
5 ALGORITHM COMPARISON
6 GENERAL REDUCTION METHODS FOR THE RELIABILITY ANALYSIS OF DISTRIBUTED COMPUTING SYSTEMS
6.1 Properties of DCS Graphs
6.2 General Reliability-Preserving Reductions for the DPR Problem
6.3 The Identification of U v
7 COMPUTATIONAL COMPLEXITY OF THE RELIABILITY PROBLEM ON DISTRIBUTED COMPUTING SYSTEMS
7.1 The Basic Strategy
7.2 Computational Complexity of the DPR Problem
8 TWO POLYNOMIAL-TIME ALGORITHMS FOR COMPUTING DPR
8.1 An O(1E21F1)Algorithm for Computing DPR Over a DCS with a Ring Structure
9 CONCLUSIONS AND FUTURE WORK
9.1 Conclusions
9.2 Future Work
FERENCES
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔