Abstract
在分散式網路中，我們稱一個節點(node)或一條連線(edge)為一個元件。在本文中，我們以不同之觀點來定義網路之重要元件(crit- icalelement)，並提出分散式計算方法來搜尋這些重要元件。首先，以拓樸的觀點，如果將一個元件從一連接(connected)網路去除，而會造成網路的斷裂(disconnected)，我們便稱此元件為重要元件。推廣之，如果將兩個元件從一連接網路去除，而會造成網路的斷裂，我們也可稱這些元件為重要元件。在本研究中，我們發展一套分散式計算方法來解決下列問題：1.橋之搜尋(bridge finding)； 2.（線，線）截集(2-edge cutset)；3.（點，線）截集((node,edge )-cutset)；和（點，點）截集(2-nodecutset)。以在最小連接樹(minimum spanning tree)上做廣播之費用來看，如果在此連接樹上有一連線或節點失去功能，則必需找一替代之連接樹，而這棵樹必需是廣播費用最少，以此觀點，我們定義出所謂緊要點(vital node)和緊要線(vital edge)。並且，我們發展一套分散式計算方法來搜尋緊要點及緊要線。在此研究內，我們還探討了另一類重要元件問題，稱做資料敏感問題(data critical problem)。當有些資料被儲存於一分散式網路中，而我們需用這些資料來解決某一問題，在此情況下，針對此問題及這些資料，我們有一答案集；另當網路上某一節點失去工能，而使在這節點上之資料無法再被使用，此時有兩種狀況，一種是這些資料不影響此問題之答案集，另一狀況是這些資料會影響此問題之答案集，前者我們稱此節點為非敏感點(non-critical node)，後者我們稱此節點為敏感點(critical node)；所謂資料敏感問題是指針對某一特定問題和某組資料，我們如何尋找所有敏感點。在本研究中，我們探討的資料敏感問題有殼集問題(convex hull problem)、極大元素問題(maxima problem)、和交集問題(set intersection problem)。