跳到主要內容

臺灣博碩士論文加值系統

(44.223.39.67) 您好!臺灣時間:2024/05/22 17:01
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:曾志宏
研究生(外文):Chi-Hung Tzeng
論文名稱:一個空間效率高之自我穩定樹狀結構建立演算法
論文名稱(外文):A Space Optimal, Self-stabilizing Algorithm for Constructing Spanning Trees
指導教授:黃興燦黃興燦引用關係
指導教授(外文):Thing-Tsaan Huang
學位類別:碩士
校院名稱:國立清華大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2003
畢業學年度:91
語文別:中文
論文頁數:40
中文關鍵詞:自我穩定半均勻系統同步模式
外文關鍵詞:self-stabilizationsemi-uniformsynchronous model
相關次數:
  • 被引用被引用:0
  • 點閱點閱:111
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:1
本論文提出一個所需空間最佳化(Space optimal)的樹狀結構建立(Tree construction )演算法,此演算法具有自我穩定(Self-stabilizing)的特性,即系統不論發生任何資料上的錯誤,都可以在有限的時間內回復到穩定的狀態。在那之後,系統就會一直維持於穩定的狀態。換句話說,自我穩定演算法具有容錯的優點。
在一個一般連通圖中,要如何建立出一個樹狀結構是一個基本且重要的問題,在過去所有解這個問題的演算法中,大部分的演算法都需要讓系統裡的節點得知整個系統所有節點總數目,即每個節點所需要的空間複雜度是O(f(n)),其中n是系統的節點總數,f(n)是和n有關的函數。由於每個節點知道一些有關於整個系統的資訊,他們就可以判斷自己是不是位於正確的樹狀結構上,若是位於不正確的樹狀結構的話,節點就必須把自己加到對的那邊去,使得整個系統最後會只有一棵樹存在。這個方法的缺點是它不適用於會動態變化的系統上,因為只要系統的節點數超過一個上限,這些演算法就不會正常地運作。
本論文的主要貢在提出一個空間複雜度為8*D的演算法,D為系統的分枝度(Degree),8是每個節點可能出現的狀態總數。由於每個節點所用的空間複雜度接近常數,這個演算法可以應用到一些專門用簡單元件構成的系統裡,這個演算法的另外一個特性是系統可以無限制地增長,而且不會產生任何錯誤。

Tree construction problem is always an interesting topic under fault-tolerant distributed systems. In this thesis, we present a deterministic self-stabilizing spanning tree construction algorithm, which runs in a non-uniform network with general graph topology. It requires only extremely small memory space per node. Each node only keeps a pointer to identify its parent and three 1-bit variables to interact with its neighbors. The Stabilizing time of the algorithm is O(n2), where n is the number of nodes in the system.

第一章 緒論……………………………………………………………II
第二章 計算模型………………………………………………………III
第三章 演算法及其正確性……………………………………………IV
第四章 結論……………………………………………………………V
英文附錄 …………………………………………………………………VI

[Ang80] D. Angluin. Local and global property in networks of processors. In Proceeding of the 11th Annual ACM Symposium on Theory of Computing, p82-93,1980.
[AG94] A. Arora, M. Gouda. Distributed reset, IEEE Transactions on Computers, 43 p1026-1038, 1994.
[AS95] G. Antonoiu, P. K. Srimami. A self-stabilizing distributed algorithm to construct an arbitrary spanning tree on a connected graph. Computers & Mathematics with Applications, v30, n9, p1-7,1995.
[CDPV01] A. Cournier, A. K. Datta , F. Petit, V. Villain. Self-Stabilizing PIF algorithm in arbitrary rooted networks. The 21st International Conference on Distributed Computing Systems, April 16-19, 2001.
[DIM93] S. Dolev, A. Israeli, S. Moran. Self-stabilization of dynamic systems assuming only read/write atomicity. Distributed Computing, 7 p3-16, 1993.
[DIM97] S.Dolev, A.Israeli, S.Moran. Uniform dynamic self-stabilizing leader election. IEEE transactions on parallel and distributed systems, v8, n4, p424-440,1997.
[Joh97] Colette Johnen. Memory efficient, self-stabilizing algorithm to construct BFS spanning trees. Proc. of the third Workshop on Self-Stabilizing System (WSS'97), p125-140, Santa Barbara, Californie, Etats-Unis, August, 1997.
[Dij74] E. W. Dijstra. Self-stabilizing systems in spite of distributed control. Communications of the ACM, v17, n11, p643-644. 1974.
[HC92] S.T. Huang, N.S. Chen. A self-stabilizing algorithm for constructing breadth-first trees. Information Processing Letters, 41, p109-117. Feb 1992.
[Hua93] S.T. Huang. Leader election in uniform rings. ACM Transactions on Programming Languages and Systems. v15, n3, p563-573. July 1993.
[Kes88] J. L. W. Kessels. An exercise in proving self-stabilization with a variant function. Information Processing Letters.29 , p39-42, 1988.
[Kru79] H.S.M. Kruijer. Self-Stabilization(in spite of distributed control) in tree-structured systems. Information Processing Letters, v8 , n2, p91-95. Feb 1979.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top