在1974年，Dijkstra發表了自我穩定的概念。一個分散式系統不論其初始狀態為何，最後都會收斂至正確的系統狀態稱之為自我穩定系統。近年來，自我穩定演算法不用初始化的特性受到許多研究者的重視。在本研究中，首先我們探討了自我穩定演算法在最大配對問題上的設計。Hsu和Huang針對分散式網路中最大配對問題提出了自我穩定演算法，並利用變數函數分析法，證明了此演算法需耗用的時間複雜度為O(n3) ，然而Tel針對此一演算法提出不同的變數函數，證明最多需要O(n2) 的時間複雜度。我們除了探討Hsu-Huang以及Tel所提出的研究之外，亦闡述了如何以圖形變化分析Hsu-Huang演算法的時間複雜度，證明了Hsu-Huang的最大配對問題之自我穩定演算法的時間複雜度為Theta(n2)。
接著，我們將自我穩定系統的理論應用在完全圖上的最大權重配對問題，設計出包含五個規則的自我穩定演算法，並針對此自我穩定演算法的正確性進行證明分析。最大權重問題是指當節點兩兩配對之後，其線段權重兩兩交換並不會找到更大的值，也就是除了希望在圖中找到最大配對之外，更進一步能夠使配對的權重達到最大。因此我們結合了Hsu-Huang最大配對自我穩定演算法，以及嶄新的交換配對規則，保留自我穩定系統容錯及自我穩定的特性，設計了時間複雜度為O(n2+nk)的一個最大權重配對問題之自我穩定演算法。
除此之外，自我穩定演算法在穩定婚姻問題上的研究亦屬於創新的研究。在本研究中我們發現根據穩定婚姻配對問題的定義，穩定婚姻問題與最大權重配對問題同樣以交換的方式求出解答，也就是說在穩定婚姻問題中男生、女生兩兩任意配對之後，再根據各自的喜好配對表調整交換各好的配對。本研究應用交換配對方式，以及系統不需初始化的特性找出穩定婚姻組合，並保證系統會在O(n3)的時間內達到合法穩定狀態。

In 1974, Dijsktra defined a self-stabilizing system as a system which is guaranteed to arrive at a legitimate state in a finite number of steps regardless of its initial state. Since his introduction, self-stabilizing algorithms gained wide-spread research interest. The objectives of this research are to design and analyze self-stabilizing algorithms for maximal matching and stable-marriage problems. Firstly, we discuss Hsu-Huang's self-stabilizing algorithm for finding a maximal matching in distributed networks. Hsu and Huang proved that the time complexity of their algorithm is O(n3) , where n is the number of nodes in the graph. In 1994, Tel introduced a variant function to show that the time complexity of Hsu-Huang's algorithm is O(n2) . In this research, we present a new method to expose that this algorithm has a time complexity of Theta(n2) .
Secondly, we design a self-stabilizing algorithm for maximal weight matching problem for complete graphs and prove its correctness. The maximal weight matching problem is defined not only to find the maximal matching of the complete graph, but also to let the total weight of the matching edges be maximal. We combine Hsu-Huang's maximal matching algorithm and new swapping rules. This system possesses the properties of fault tolerance and self-stabilization and has a time complexity O(n2+nk) , where k is the largest weight over all edges in the graph.
Thirdly, the stable-marriage problem is that of matching n men and n women, each of them has ranked the members of the opposite sex in order of preference, so that no unmatched couple both prefer each other to their partners under the matching. In the research, we also use the swapping rule according to the preference to make the matching couple stable. Our self-stabilizing algorithm guarantees that the system will reach a legitimate stable state in O(n3) steps to find one stable matching from any initial state.

【1】 B. Awerbuch, S. Kutten, Y. Mansour, B.P. Ddhamir, G. Varghesse, Time optimal self-stabilizing synchronizationm, Proceedings of the 25th Annual ACM Symposium on Theory of Computing,（1993）652-661.
【2】 J. Beauquier, S. Delaet, Probabilistic self-stabilizing mutual exclusion in uniform rings, Principles of Distributed Computing, 8（1994）378.
【3】 N. S. Chen, F. P. Yu and S. T. Huang, A self-stabilizing algorithm for constructing spanning trees, Inform. Process. Lett., 39（1991）147-151.
【4】 Z. Collin, S. Dolev, Self-stabilizing depth-first search, Inform Process. Lett., 49（1994）297-301.
【5】 A. K. Datta, T. F. Gonzalez, V. Thiagarajan, Self-stabilizing algorithms for tree metrics, Parallel Process. Lett., 8（1）（1998）121-133.
【6】 J. Desel, E. Kindler, T. Vesper, R. Walter, A simplified poof for a self-stabilizing protocil: a game of cards, Inform. Process. Lett., 54（1995）327-328.
【7】 S. Dolev, A. Israeli, S. Moran, Uniform dynamic self-stabilizing leader election, IEEE Transactions on parallel and distributed systems, 8（4）（1997）.
【8】 E. W. Dijsktra, Self-stabilizing systems in spite of distributed control, Comm. ACM, 17（1974）643-644.
【9】 O. Flauzac, V. Villain, An implementable dynamic automatic self-stabilizing protocol, International Symposium on Parallel Architectures, Algorithms and Networks, IEEE, （1997）91-97.
【10】 D. Gale and L. S. Shapley, College admissions and the stability of marriage, Amer. Math. Monthly, 69（1962）9-15.
【11】 S. Ghosh, Binary self-stabilization in distributed Systems, Inform Process. Lett., 40（1991）153-159.
【12】 S. Ghosh and M. H. Karaata, A self-stabilizing algorithm for coloring planar graphs, Distributed Computing, 7（1）（1993）55-59.
【13】 S. Ghosh, A. Gupta and S. V. Pemmaraju, A self-stabilizing algorithm for the maximum flow problem, Distributed Computing , 10（4）（1997）167-180.
【14】 S. Ghosh, A. Gupta, T. Herman and S. V. Pemmaraju, Fault-containing self-stabilizing algorithms, Proceedings of the 15th ACM Principle of Distributed Computing, （1996）45-54.
【15】 D. Gusfield, The structure of the stable roommate problem: efficient representation and enumeration of all stable assignments, SIAM J. Comput., 17（4）（1988）742-769.
【16】 D. Gusfield, Three fast algorithms for four problems in stable marriage, SIAM J. Comput., 16（1987）111-128.
【17】 T. Herman, Probabilistic self-stabilization, Inform Process. Lett., 35（29）（1990）63-67.
【18】 D. Hoover, J. Poole, A distributed self-stabilizing solution to the dining philosophers problem, Inform. Process. Lett., 41（1992）209-213.
【19】 S. C. Hsu and S. T. Huang, A self-stabilizing algorithm for maximal matching, Inform. Process. Lett., 43（2）（1992）77-81.
【20】 S. T. Huang and N. S Chen, A self-stabilizing algorithm for constructing breadth-first trees, Inform Process. Lett., 41（1992）109-117.
【21】 J. S. Hwang, The algebra of stable marriages, Intern. J. Computer Math., 20（1986）227-243.
【22】 R. W. Irving, An efficient algorithm for the "stable roommates" problem, Journal of Algorithms, 6 （1985）577-595.
【23】 P. Jalote, Fault Tolerance in Distributed Systems, Prentice-Hall（1994）.
【24】 J. L. W. Kessels, An exercise in proving self-stabilization with a variant function, Inform. Process. Lett., 29（1988）39-42.
【25】 D. E. Knuth, Stable Marriage and its Relation to Other Combinatorial Problems, American Mathematical Society, （1997）.
【26】 L. Lamport, Solved problems, unsolved problems and non-problems in concurrency, In Proceedings of the 3rd ACM Symposium on Principles of Distributed Computing, （1984）1-11.
【27】 D. G. McVitie and L.B. Wilson, Three procedure for the stable marriage problem, Common. ACM, 14（1971）491-492.
【28】 M. Papatriantafilou, P. Tsigas, On self-stabilizing wait-free clock synchronization, Parallel Processing Letters, 7（3）（1997）321-328.
【29】 M. Schneider, Self-stabilization, ACM Computing Surveys, 25（1）（1993）45-67.
【30】 G. Tel, Maximal matching stabilizes in quadratic time, Inform. Process. Lett., 49（1994）271-272.
【31】 C. A. Wang, Self-stabilizing algorithms for Distributed systems, MS.D Thesis, Department of Computer Science and Information Engineering, National Taiwan University, Taiwan（1995）.