錯誤抑制的自我穩定演算法 — 通用的方法

Fault-containing Self-stabilizing Algorithms - a General Approach

林時誠(Shih-Cheng Lin)

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

元智大學/資訊學院/資訊工程學系/碩士(2002年)

摘要

在本篇論文中，我們設計了一種轉換的方法，能夠把一個不具錯誤抑制特性的自我穩定演算法轉變成為錯誤抑制的自我穩定算法。 當系統處於單一錯誤的狀況時，經由我們轉換後的演算法其時間複雜度為 O(∆)，而 ∆ 為節點的最大分支度。因此，經由我們所轉換後的演算法其效率比現存的任一種轉換法好得多。

關鍵字

錯誤抑制 ； 自我穩定算法 ； 時間複雜度

並列摘要

In this thesis, we design a general transformer that can transform a non-fault-containing self-stabilizing algorithm into a fault-containing self-stabilizing algorithm. In the single-fault situation, the worst case stabilization time of the algorithm induced by our transformer is O(∆), where ∆ is the maximum node degree. Therefore, the efficiency of the algorithm induced by our transformer is much better than the existing one.

並列關鍵字

fault-containing ； self-stabilizing algorithm

參考文獻

1. Dijkstra, E. W.: Self-stabilizing system in spite of distributed control.

Commune ACM 17(11), 643-644 (1974).

2. Dijkstra, E. W.: Self-stabilizing system in spite of distributed control

3. Dijkstra, E. W.: A belated proof of self-stabilization. Distributed

Computing 1(1), 5-6 (1986).