分散式排程下的解決極小控制集問題的高效率自我穩定演算法

An efficient self-stabilizing algorithm for the minimal dominating set problem under a distributed scheduler

蔡詩妤(Shih-Yu Tsai)

指導教授 ： 陳秋媛

國立交通大學/理學院/應用數學系暨研究所/碩士(2011年)

https://doi.org/10.6842/NCTU.2011.00236

摘要

本篇論文考慮的是設計解決極小控制集（MDS）問題的更具有效率的自我穩定演算法（self-stabilizing algorithms）。設n為分散式系統裡的節點數目。若一個自我穩定演算法在給定的分散式系統執行至多t次動作後，即可到達合理狀態（legitimate configuration），則稱此自我穩定演算法為t-動作演算法（t-move algorithm）。在2007年，Turau提出了一個分散式排程下的解決MDS問題的9n-動作演算法。隨後，在2008年，Goddard等人提出一個分散式排程下的解決MDS問題的5n-動作演算法。設計一個執行動作少於5n次的分散式排程下的解決MDS問題的演算法，確實是一個挑戰。本篇論文的目的就在於設計出這樣的演算法。具體來說，我們提出了一個分散式排程下的解決MDS問題的4n-動作演算法；此外，採用我們演算法，需要4n-1個動作才可以到達合理狀態的例子也被提出。

關鍵字

自我穩定演算法 ； 容錯 ； 分散式計算 ； 圖形演算法 ； 控制

並列摘要

This thesis considers designing efficient self-stabilizing algorithms for solving the minimal dominating set (MDS) problem. Let n denote the number of nodes in a distributed system. A self-stabilizing algorithm is said to be a t-move algorithm if when it is used, a given distributed system takes at most t moves to reach a legitimate configuration. In 2007, Turau proposed a 9n-move algorithm for the MDS problem under a distributed scheduler. Later, in 2008, Goddard et al. proposed a 5n-move algorithm for the MDS problem under a distributed scheduler. It is indeed a challenge to develop an algorithm that takes less than 5n moves under a distributed scheduler. The purpose of this thesis is to propose such an algorithm. In particular, we propose a 4n-move algorithm under a distributed scheduler; an example such that our algorithm takes 4n − 1 moves to reach a legitimate configuration has also been proposed.

並列關鍵字

Self-stabilizing algorithms ； Fault tolerance ； Distributed computing ； Graph algorithms ； Domination

參考文獻

[1] E. W. Dijkstra, Self-stabilizing systems in spite of distributed control, Communication of the ACM 17 (11) (1974) 643-644.

[3] S. Dolev, A. Israeli, and S. Moran, Self-stabilization of dynamic systems assuming only read/write atomicity, Distributed Computing 7 (1) (1993) 3-16.

[4] W. Goddard, S. T. Hedetniemi, D. P. Jacobs, and P. K. Srimani, A self-stabilizing distributed algorithm for minimal total domination in an arbitrary system graph, in: Proc. 17th International Parallel and Distributed Processing Symposium, 2003.

[6] N. Guellati and H. Kheddouci, A survey on self-stabilizing algorithms for independent, domination, coloring, and matching in graphs, Journal Parallel and Distributed Computing 70 (4) (2010) 406-415.

[8] S. M. Hedetniemi, S. T. Hedetniemi, D. P. Jacobs, and P. K. Srimani, Self-stabilizing algorithms for minimal dominating sets and maximal independent sets, Computer Mathematics and Applications 46 (5-6) (2003) 805-811.