在被複製的有向無迴路圖上之可靠度分析

Abstract

在分散式系統上執行之工作可以一個有向圖來表示, 圖上的每個節點與每 個邊都給定一個會斷掉的機率, 則此一工作會被正確執行的機率即定義為 該工作之可靠度. 本篇論文的主題在於找到兩個演算法來分別計算出有向 無迴路圖(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.