Abstract
在分散式系統中所討論的問題可以分成二個主要的範圍：(1) 與分散式操作系統有關的軟體問題, 其中主要包括程式終止偵測 (Program Termination Detection), 死結偵測 ( Deadlock detection), 閒置程序收集(Garbage Processes Collection), 及自我穩定系統 (Self-Stabilizing Systems) 等等; (2) 與網路結構有關的硬體問題, 包括交連網路 (Interconnection Networks) 和路徑控制問題 (Routing Control)等等, 在本論文的研究中包含了這二個主要部份, 其一是軟體問題, 另一個是硬體問題。在第一個部份中，我們研究分散式系統的穩定性質 (Stable Properties)。所謂的穩定狀態是指系統一旦進入了這個狀態就會一直保持著不會改變；除非有外在的因素使其改變。穩定性質的研究在分散式系統中是非常重要的，程式終止偵測(TerminationDetection) 在分散式系統中就是一個典型的尋找穩定狀態的問題。我們可以把穩定狀態分成二個種類: 一類是系統希望達到的狀態 (Desired Stable States), 另一類是系統不希望達到的狀態 (Undesired Stable States), 第一類的穩定狀態像是程式終止和自我穩定系統等等。另一方面像 Deadlock processes 和 Garbage Processes則是屬於等二類的穩定狀態。在我們的研究中包含了這二類的穩定狀態。我們設計了一個能夠建構廣度優先樹 (Breadth-First Trees)的自我穩定系統; 是屬於第一類的穩定狀態。另外我們也提出了一個計算方法 (Algorithm)用來偵測分散式計算 (Dis-tributed Computations)中的 Garbage Processes; 這是屬於第二類的穩定狀態。在第二個部份中，我們研究多處理機系統的交連網路 (Interconnection Networks )問題。大家都知道訊息的傳遞 (Message Passing)在多處理機系統中是一個非常重要的因素; 所以尋找能夠提供快速訊息傳遞的好結構 (Topology) 是非常需要的。其中有一種 Shuffle-Exchange Networks已經被証明是一種可以提供有效的訊息傳遞的網路。在文獻上被廣泛研究的 Multistaged Interconnection Networks (MIN) 幾乎都是使用 Shuffle來連接的。但是在先前的研究中，Switching Eelements 的考慮都是2x2 的, 我們的研究把2x2 的 Switching Elements 推廣到 KxK。另一方面，我們也提出一種新的可重排性 (Rearrangeable)的網路, 叫作串接式的地爾它網路 (Casca-ded Delta Networks )。由於我們用了比較一般化的連接型式 (Link Patterns), 地爾它網路可以含蓋大部份的可重排性網路。