Abstract
在這篇論文中，我們提出一個可以在分散式自我穩定系統中尋找橋之演算法。橋是圖形中的一個邊，如果移去這個邊會使原來的圖形不連接。一個分散式自我穩定系統是一個有限狀態機器的網路而有下列性質：假如系統開始在任何，可能非法的狀態，它保證在有限時間內會收斂到一個合法的狀態。那也就是說，這種系統可以在有限時間從任何不可預期的擾亂中恢復，而無需任何外在的介入。這種性質在容錯(FAULT TO-LERANCE)系統的領域中是非常需要而且是一個非常重要的問題。對於每個處理器 (PROCESSOR)，我們定義特權這個名詞，它是一個定義域為自己狀態和鄰居狀態的函數。當這個函數為真時，我們說這個特權是存在的 (PRESENT)。為了使演算法正確，我們需要一個中央控制 (CENTRAL DEMON)，可以選擇一個有特權存在的處理器去執行，這個處理器可以執行一個移動從舊狀態到新狀態，而新的狀態是一個舊狀態和其鄰居狀態的函數，假如有很多特權存在，則中央控制會隨機選擇其中一個來執行。大部分分散式圖形演算法可以分成好幾個階段，每個相鄰的階段有一明顯的界線。當每一個處理器欲執行某一個階段的指令和規則(RULE)時，只有在某前一個階段被完成時才可。這種明顯的界線，可以使得設計這種演算法變的容易控制。不論如何，在分散式自我穩定系統中，由於不可預期的初始狀態和隨機的特權選擇，規則的執行可能開始在任何一個階段，這也是設計分散式自我穩定演算法的基本困難所在。所以我們在這篇論文提出一個觀念。一個分散式自我穩定演算法可能由 K個階段組成。每個階段有其自己的規則和變數。一個階段的規則執行可以改變其變數，但是只能讀比其低階段的變數。每一個階段必須要自我穩定。假如我們可使每一個階段 1到K-1 都失去特權當階段 K是穩定的且當低階段未穩定時，比其高的階段會失去特權。則整個演算法滿足自我穩定的要求。這篇論文所提出尋求橋之演算法是建構在這個觀念上。