We propose a new self-stabilizing 1-maximal matching algorithm which is silent and works for any anonymous networks without a cycle of length of a multiple of 3 under a central unfair daemon.
A lot of computers are connected and working in a coordinated manner in the modern society. Robust distributed algorithms are necessary in order to tolerate faults in a computer network. Many concepts achieving fault toler- ance are proposed by a lot of researchers, and self-stabilization (self-stabilizing algorithm) is one of them.
Maximum or maximal matching is a well-studied fundamental problem for distributed networks. And 1-maximal matching is a 2/3-approximation to the maximum matching. Self-stabilizing algorithms solving these problems can be used in distributed applications to make pairs of nodes.
Let n and e be the numbers of nodes and edges in a graph, respectively. The time complexity of the proposed algorithm is O(e) moves. Therefore, the complexity is O(n) moves for trees or rings whose length is not a multiple of 3.
We evaluate the time complexity of proposed algorithm by counting move of each node under unfair central daemon. A node is a state machine which changes its state by actions. According to an execution of the algorithm, nodes change its state asynchronously. We call the changing state by a node move. Moves of nodes are scheduled by a daemon. A central daemon chooses one priv- ileged node at one time, and the selected node atomically moves. A daemon is unfair in a sense that it can choose any node among privileged nodes. The pro- posed algorithm is silent. It means the system reaches a terminal configuration where no node can move from any arbitrary initial configuration.
The algorithm of Goddard et al. works for anonymous trees and anonymous rings without a cycle of length of a multiple of 3. And the time complexity is O(n4) moves. Proposed algorithm in this thesis works for any anonymous networks without a cycle of length of a multiple 3. And the time complexity is O(e) moves. Thus the result in this thesis is a significant improvement from the best existing results.