臺灣博碩士論文加值系統

本論文提出一個所需空間最佳化(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.