標題: 在被複製的有向無迴路圖上之可靠度分析
Reliability Analysis of Replicated Directed Acyclic Graphs
作者: 王朱福
Ju-Fur Wang
簡榮宏
Rong-Hong Jan
資訊科學與工程研究所
關鍵字: 網路可靠度;有向無迴路圖;被複製的有向無迴路圖;Network Reliability;Directed Acyclic Graphs;Replicated Directed Acyclic Graphs
公開日期: 1994
摘要: 在分散式系統上執行之工作可以一個有向圖來表示, 圖上的每個節點與每
個邊都給定一個會斷掉的機率, 則此一工作會被正確執行的機率即定義為
該工作之可靠度. 本篇論文的主題在於找到兩個演算法來分別計算出有向
無迴路圖(DAG)及被複製的有向無迴路圖(RDAG)之可靠度.除此之外, 我們
也找到一個演算法來計算出在有向無迴路圖上之最佳的複製節點.
A computation task running in distributed systems can be
represented as a directed graph H(V,E) whose vertices and edges
may fail with known probabilities. The reliability of the task
is defined to be the probability that the task can be success-
fully executed. In this thesis, we consider the reliability
evaluation of a directed acyclic graph (DAG) and k-replicated
directed acyclic graph (k-RDAG). Two algorithms based on mini-
mum reduction are presented to compute the reliability of a DAG
and a k-RDAG. In addition, we consider a most replicable probl-
em. That is, a node is called the most replicable node in a
graph if it is replicated along with all its adjacent edges,
then the reliability of the resultant graph is maximized. We
present an algorithm based on minimum reduction for finding a
most replicable node in a DAG.
URI: http://140.113.39.130/cdrfb3/record/nctu/#NT830394072
http://hdl.handle.net/11536/59097
顯示於類別:畢業論文