環狀及星狀分散式計算系統中程式可靠度的分析與研究

Abstract

對於分散式計算系統中程式可靠度，其決定於通訊網線路的可靠度和節點的可靠度，並且和其資源 ( 例如: 程式、檔案 ) 的分散情形也有關係。這一篇論文主要是研究環狀及星狀分散式計算系統中程式可靠度。在環狀分散式計算系統，我們提出兩種環狀網路分散式程式可靠度分析的情形。第一種情形是程式及資料檔均只有一份，第二種情形是程式及資料檔可有多重備份。針對此兩種情形，我們設計出不同Polynomial Time演算法評估分散式程式可靠度。而在環狀網路中的Ring of Tree 拓樸，當程式及資料檔有多重備份時，我們亦證明此種問題是NP-hard問題。 在星狀網路架構，我們亦證明此種問題是NP-hard問題。但若對程式和資料檔案的分佈做某種程度的限制時，我們則提出Polynomial Time演算法來評估星狀網路分散式程式可靠度。 最後，當星狀網路拓樸無法設計出Polynomial Time演算法來計算分散式程式可靠度之正確解時，我們亦提出Polynomial Time演算法來求其可靠度之逼近解。

Distributed Computing System (DCS) has become very popular for its high fault-tolerance, potential for parallel processing, and better reliability performance. One of the important issues in the design of the DCS is the reliability performance. Distributed Program Reliability is addressed to obtain this reliability measure. The Distributed Program 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. In this thesis, we study distributed program reliability (DPR) on ring and star distributed computing systems. In the ring structure, We will discuss the distributed program reliability of ring network and ring of tree topology. We have proposed algorithms for computing DPR in ring network. We have also shown that computing the distributed program reliability of ring of tree topology is NP-hard. In star topologies, We have shown that computing the distributed program reliability of star topology in general is NP-hard. Two polynomially solvable cases are developed for computing distributed program reliability when some additional file distribution is restricted on the star topology. We also propose a polynomial time algorithm for computing distributed program reliability with approximate solution when the star topology is not satisfied with the additional file distribution.