完全圖上最大權重配對問題之自我穩定演算法的設計及分析

Abstract

在1974年，Dijkstra提出了自我穩定的概念。一個分散式系統不論其初始狀態為何，最後都會收斂至正確的系統狀態稱之為自我穩定系統。近年來，自我穩定演算法不用初始化的特性受到許多研究者的重視。Hsu和Huang針對分散式網路中「最大配對」問題提出了自我穩定演算法，並利用變數函數分析法，證明了此演算法需耗用的時間複雜度為O(n3)，然而Tel針對此一演算法提出不同的變數函數，證明最多需要O(n2)的時間複雜度。在本論文中，我們將自我穩定系統的理論應用在完全圖上的「最大權重配對」問題，設計出包含五個規則的自我穩定演算法，並針對此自我穩定演算法的正確性進行證明分析。最大權重問題是指當節點兩兩配對之後，其線段權重兩兩交換並不會找到更大的值，也就是除了希望在圖中找到最大配對之外，更進一步能夠使配對的權重達到最大。因此我們結合了Hsu-Huang最大配對自我穩定演算法，以及嶄新的交換配對規則，保留自我穩定系統容錯及自我穩定的特性，設計了時間複雜度為O(n2+nk)的一個最大權重配對問題之自我穩定演算法。

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 weight matching problem. Firstly, Hsu and Huang proved that the time complexity of their self-stabilizing algorithm for finding a maximal matching in distributed networks 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 paper, we design a self-stabilizing algorithm for maximal weight matching of the complete graph 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 alogrithm 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.