Abstract
在本論文中，我們研究自發穩定系統(self-stabilizing systems)之演算法設計．自發穩定系統擁有以下的特性：不論該系統的初始狀態為何，且不論該系統中各個處理器執行的順序為何，此系統終將在有限的步驟內達到且停留在一個合法的穩定狀態(legitimate state)．換言之，當系統受到干擾時，一個自發穩定系統能在有限的時間內自動偵測錯誤並修改之，使得系統恢復至穩定狀態．自發穩定系統依假設條件不同可區分為四種執行模式(execution models)：順序執行模式(serial model)，同步模式(synchronous model)，同步分散模式(synchronized distributed model)，及分散模式(distributed model)．前人對自發穩定系統之研究多限於順序執行模式或同步模式下之分散式控制協定(distributed controlprotocol)及非加權圖(unweighted graph)上之演算法設計，本論文之研究則著重於分散模式下之加權圖(weighted graph)上的演算法設計．我們討論了以下問題：單一出發點的最短路徑問題，建立最小擴散樹，檢查聯接圖 (connected graph)中的每一個邊是否為一座橋(bridge)，以及同質環 (uniform ring)的方向調整(orientation)問題．我們嘗試不同的途徑來設計這些演算法，並且提出了一個可以簡化自發穩定系統設計的方法．我們也提出了一個方法來簡化証明一個自發穩定系統在可以在分散模式(distributed model)下執行．In this dissertation, we study the problem of designing self-stabilizing algorithms. A self-stabilizing algorithm has theproperty that regardless of the initial state of the system andthe execution sequence of the processors, the system will reacha legitimate state within a finite number of moves. Mostprevious self-stabilizing algorithms deal with distri- butedcontrol problems such as token passing, and problems onunweighted graphs such as spanning tree construction. We haveput our efforts on weighted graphs. The following problems arestudied: finding the shortest paths from a source node to theother nodes, constructing the minimal spanning tree of anundirected graph, identifying the bridges of a connected graph,and finding a consistent orientation of the processors of auniform unoriented ring. We use different approaches to designalgorithms for these problems, and proposed a concept which maysimplify the task of converting a non self-stabilizingalgorithm into a self-stabilizing one. We show that all thesealgorithms can work well without a central demon. We alsodevelop a new approach to make the correctness reasoning underthe distributed model easier.