樹狀網路上找尋中心點的有效率錯誤抑制自我穩定演算法

An efficient fault-containing self-stabilizing algorithm for finding centers of trees

周政佑(Cheng-Yu Chou)

指導教授 ： 黃哲志 ； 林基成

元智大學/工程學院/電機與資訊工程研究所/碩士(1998年)

摘要

本篇論文提出一個在樹狀網路找中心點(centers)的自我穩定演算法，具有以下兩點特性：當系統發生single transient fault，(1)只有fault node會去修正資料，(2)stabilization time為O(min(D^2,n))，D為maximum node degree，n為nodes的個數。若一系統在任何起始狀態(initial states)下，皆能不經外力的介入，而在有限步驟之內恢復到正確的狀態，會一直維持在正確的狀態，我們稱這個系統為自我穩定系統(self-stabilizing system)。實際上，分散式系統一次只有一個node發生transient fault的機率遠大於多個node同時發生transient fault。到目前為止在樹狀網路找中心點的自我穩定演算法，當系統發生single transient fault，會有O(n)個nodes的資料會被影響，而stabilization time為O(n^2)。

關鍵字

自我穩定演算法 ； 中心點 ； 錯誤抑制

並列摘要

In the thesis we propose an efficient fault-containing self-stabilizing algorithm for finding centers of trees. For the proposed algorithm: (1) only faulty node will correct it’s data after single transient fault occurs. (2) the stabilization time in single fault situation is O(min(D^2,n)), where D is the maximum node degree and n is number of nodes. We call a system self-stabilizing if the system will return to legitimate state in finite number of moves from any initial state, without any external introversion. In fact, single transient fault in expected to occur more frequently in practice. For the best previous algorithm, these are O(n) nodes will be influenced and stabilization time is O(n^2) in single fault situation.

並列關鍵字

self-stabilizing algorithm ； center ； fault-containing

參考文獻

Distributed control.”Communication of

[Dij86] E.W.Dijkstra.“A Belated Proof of Self-Stabilization”.

(Special issue on the English International Conference

Canada, June 1996.).

[Dij74] E.W.Dijkstra.“Self-Stabilizing System in Spite of