Abstract
自我穩定(self-stabilizing)這個名詞最早是由Dr.Dijkstra 所提出。無論系統處在任何起始狀態，保證一定在有限時間內收斂到一正常狀態並繼續保持下去。這種特性使得系統在面臨無常的錯誤(transient error) 時，具有高度可靠性。本文討論樹(trees) 的自我穩定方法。目的是設計有關的演算法，在分散式系統上維持樹結構。G(V,E)是一連通圖形 (connected graph)。V 是點的集合而 E是邊的集合。我們以這樣一個圖形來表示 n個處理器之分散式系統。每個節點表示一個處理器，直接有邊相連的節點互稱鄰近點。我們的目標是設計能自我穩定的演算法，在圖形上維持一個函蓋樹(spanning tree) 或廣度優先樹(breadth-first tree)。而每一節點知道自己在樹中的正確層數 (level)。對每一個處理器而言，我們定義一些‘特權’(privilege) 。它是由處理器本身狀態及其鄰近點狀態所共同形成的布林函數(boolean function)。當此函數值為真，則稱特權呈現 (present)，此時處理器才有機會動作(move)，即可以走到一個新狀態。每個處理器依據相同的行動規則 (rules)。規則由兩部分組成–特權及動作。當特權呈現，處理器可進行相對應的動作。在某些狀況，可能同時有一個以上的處理器具有特權。雖然，我們設計的規則不具非干擾性 (non-interfering)，但多個處理器同時動作是不成問題的。在我們的問題中，系統若維持在樹狀態則稱其正常，否則為不正常。無論起始狀態為何，且無論每次動作的次序為何，我們所設計的演算法，必須保證在有限次動作後將系統狀態帶到一個正常態，即一涵蓋樹或一廣度優先樹。一旦完成，則不再動作。若再有非預期的混亂發生，那麼此演算法會再度被執行，直到系統恢復正常。因此，對此種自我穩定有以下三點定義：(1) 在不正常狀態時，至少有一個特權會呈現。(2) 當系統已達正常狀態則不再有任何特權會呈現。(3) 無論任何起始狀態，更無論選擇一個特權來進行下一次動作，系統保證在有限次動作後收斂到一正常狀態。相似於其他分散式演算法的證明，自我穩定性的證明並不是那麼直接。首先，必須證明當系統尚未穩定時一定會有機會動作。其次，給定一個有界函數(bounded functi-on) ，其值跟著每次動作而遞減。我們成功的將此法用在函蓋樹的證明。然而，有界函數並不容易找到，例如廣度優先樹，我們運用了一些技巧，才找到配合的函數。