分散式計算系統上之可靠度問題的計算複雜度的分析與研究

Abstract

一個在分散式計算系統裡所執行的程式,往 往要透過網路去讀取在其它處理器上的資料. 所以在分散式計算系統所執行的程式,它的可 靠度就決定於(1)這個分散式計算系統的架構; (2)傳輸線路的可靠度;(3)程式和資料的分佈情 形;(4)程式執行時所需要讀取的資料.本計畫希 望能夠分析出這個可靠度問題在不同的網路架 構上所呈現出來的複雜度,同時也希望提出一 些很有效率的演算法,來計算一些具有特殊網 路架構的分散式計算系統的可靠度.特別地我 們將深入探討下列不同網路架構之分散式程式 可靠度以及其複雜度.(1)平面網路;(2)樹狀網路; (3)星狀網路;(4)環狀網路;(5)線狀網路;(6)串連- 並連網路等等.本計畫完成之主要成果包括:(1) 完成分散式計算系統上的可靠度問題的複雜度 分析;(2)具體的提出一些很有效率(Polynomial-time) 的可靠度計算演算法;(3)對於大型的分散式計 算系統能很有效率的計算出其可靠度.