臺灣博碩士論文加值系統

本論文提出了一個尋找最大獨立集（maximal independent set）之自我穩定演算法，具有以下兩點特性，當系統中只有一個節點發生 transient fault：（1）只有錯誤節點或其鄰居二者之一會修正資料，（2）系統回復正常的時間複雜度為 O(△)，其中△為 maximum node degree。若一個分散式系統在任何起始狀態下，經有限步驟的系統運作後能自動的回復到正確的狀態，則我們稱該系統為自我穩定系統。事實上，分散式系統中一次只有一個節點發生 transient fault 的機率要遠大於多個節點同時發生 transient fault 的機率，所以我們所提出的演算法更具實用價值。

In this thesis, we propose an efficient fault-containing self-stabilizing algorithm for finding a maximal independent set. For the proposed algorithm : (1) only faulty node or one of it's neighbors ( not both ) will correct data after single transient fault occurs, (2) the time complexity from any single fault is O(△), where △ is the maximum node degree. We call a system self-stabilizing if, regardless of the initial state, the system will return to legitimate state after finite number of moves. In fact, single transient fault in expect to occur more frequently in practice, so it is more valuable from practical point of view.

第一章 導論
1-1背景介紹
1-2自我穩定系統
1-3 錯誤抑制之自我穩定演算法
1-4 Shukla 等人所提出的演算法
1-4-1 Maximal Independent Set
1-4-2 符號定義
1-4-3 Shukla 的演算法
1-4-4 Shukla 的演算法缺點
第二章 演算法簡介與分析
2-1 變數定義及假設
2-2 演算法簡介
2-3 演算法分析
2-3-1考慮 faulty node由 1 變 0
2-3-2 考慮 faulty node 由 0 變 1
第三章 演算法證明
3-1 自我穩定之證明
3-2 錯誤抑制之證明
第四章 未來研究目標
參考文獻

[Dij74] E.W.Dijkstra, "Self-stabilizing system in spite of distributed control" ,
Communication of ACM , Vol.17, No.11, p.643-644, 1974.
[Dij86] E.W.Dijkstra , "A belated proof of self-stabilization" , Distributed
Computing , Vol.1, No.1, p.5-6, 1986.
[FDG94] M. Flatebo, A.K. Datta, S. Ghosh, "Self-stabilization in distributed systems" ,
Readings in Distributed Computing Systems , p.100-114, TL Casavant and
M Signal Editors, 1994.
[GGHP96] S. Ghosh, A. Gupta, T. Herman, S.V. Pemmaraju, "Fault-containing self-
stabilizing algorithms" , PODC 96 Proceedings of the Fifteenth Annual
ACM Symposium on Principles of Distributed Computing , P.45-54, 1996.
[GP97] S. Ghosh, S.V. Pemmaraju, "Tradeoffs in fault-containing self-stabilization",
Proceedings of the Third Workshop on Self-Stabilizing Systems , P.157-169,
1997.
[Gup97] Arobinda Gupta . "Fault-containment in self-stabilizing distributed
Systems", Technique Report TR97-06, Iowa, 1997.
[Sch93] M. Schneider. "Self-stabilization". ACM Computing Surveys, 25(1), p.45-67,
1993.
[SRR95] S.K. Shukla, D.J. Rosenkrantz, S.S. Ravi, "Observations on self-stabilizing
graph algorithms for anonymous networks" , Proceedings of the Second
Workshop on Self-Stabilizing Systems , p.7.1-7.5, 1995.
[WH95] L.C. Wu, S.T. Huang . "Distributed self-stabilizing systems" , Journal of
Information Science and Engineering , Vol.11, p.307-319, 1995