標題: 分散式排程下的解決極小控制集問題的高效率自我穩定演算法
An efficient self-stabilizing algorithm for the minimal dominating set problem under a distributed scheduler
作者: 蔡詩妤
Tsai, Shih-Yu
陳秋媛
Chen, Chiu-Yuan
應用數學系所
關鍵字: 自我穩定演算法;容錯;分散式計算;圖形演算法;控制;Self-stabilizing algorithms;Fault tolerance;Distributed computing;Graph algorithms;Domination
公開日期: 2010
摘要: 本篇論文考慮的是設計解決極小控制集(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.
URI: http://140.113.39.130/cdrfb3/record/nctu/#GT079822526
http://hdl.handle.net/11536/47522
Appears in Collections:Thesis


Files in This Item:

  1. 252601.pdf