Abstract
本論文是在個體無差異系統中做自我穩定的探討與研究。我們稱一系統為個體無差異系統(uniform system)假如這系統的每一工作元都有相同的工作能力且執行相同的程式。我們知道任何一個系統，常會因為一些外來非預期性的干擾，使得系統進入不穩定狀態以致無法正常操作；我們希望設計一些系統使其具有〝自我穩定〞(self-stabilization)的能力，即當系統受到干擾後，在有限時間內系統能自動偵測錯誤並修改之，使得系統恢復至一合理的穩定狀態。本論文首先探討個體無差異系統工作元的自我穩定命名問題─同步環的命名(identity assignment in uniformsynchronous rings)，及單一方向環的命名(identity assignment inuniform unidirectional rings)。接著，我們探討個體無差異系統的自我穩定token環繞問題─(token circulation on uniform networks)。由於假設條件的不同造成一自我穩定系統有不同的執行模式，本文將之區分為四類：順序執行模式(Serial Model)、同步執行模式(SynchronousModel)、分散同步執行模式(Synchronized Distributed Model)及分散執行模式(Distributed Model)。在這四種執行模式中，分散執行模式是最實際的一種模式，但也是最難設計和證明其正確性的一種執行模式。本文針對分散執行模式的證明提出一轉換技術，利用此轉換技術可使得證明一系統在分散執行模式是否有自我穩定的能力變得容易些。In this dissertation, we design self-stabilizing protocols onuniform systems. A system is uniform if all the processors areanonymous and execute the same program. Self-stabilizingprotocols have been considered more robust than traditionalfault tolerance protocols in face of transient faults. This isbecause a self-stabilizing protocol need not be initialized toany particular state: every processor can be started in anarbitrary state. This makes a self-stabilizing protocol beable to handle all kinds of transient faults. The protocolsproposed here in this dissertation are for identity assignmentin uniform synchronous rings, identity assignment in uniformunidirectional rings, and token circulation on uniformnetworks. All the proposed protocols are shown having self-stabilizing property. There are several execution models forself-stabilizing protocols discussed in the literature. Herein this dissertation we classify them into four categories:Serial model, Synchronous model, Synchronized Distributed modeland Distributed model. Among these execution models, thedistributed model is most realistic. Yet, proving that aprotocol has the self-stabilizing property with the distributedmodel is most difficult. In this dissertation, we not onlydesign self-stabilizing protocols on uniform systems, but alsopropose a transform technique which makes the proof whether theprotocols is self- stabilizing with the distributed model mucheasier.