分散式系統之自我穩定極小控制集演算法與凱氏圖之正負號星控制數

Abstract

圖論的控制集問題的研究始於1960年代。一個分散式系統(例如：一個隨意網路)可以用一個無向簡單圖G=(V,E)來表示，其中V表示點集，而E表示點跟點之間的聯結關係。圖G的點集V的子集合D被稱為是控制集，若此子集D具有性質：V中的任一元素v屬於D或與D中的元素相鄰。如果一個控制集不真包含另一控制集，則稱其為極小控制集(簡記為MDS)。極小控制集在無線網路中的應用之一是使所需的資源中心保持為較少數目。 自我穩定是一個可用於設計分散式系統容忍暫時性錯誤的一個概念，並且是在1974年由Dijkstra提出。一個分散式系統是自我穩定的，如果它滿足：不論初始組態為何，系統總是能保證在有限時間內達到一個合法的(正確的)組態。此處所稱的系統組態是由系統中所有節點的狀態所組成。一個自我穩定演算法由一些規則所組成，每個規則都有其觸發條件及其對應動作，該動作能通過更新節點的變數來改變節點的狀態。每執行一個規則稱為是一步。本論文所提出的演算法的效能皆是以執行總步數來計算。自我穩定演算法有許多不同的執行模式，且執行模式是以排程器的概念來呈現。排程器分為公平的及不公平的兩種。眾所皆知，不公平的分散式排程器比其他類型的排程器更貼近實際使用狀況。 令n表示給定的分散式系統的節點數。在2007年，Turau對於MDS問題，提出了不公平的分散式排程器下的第一個線性時間的自我穩定演算法，此演算法在最多9n步之後穩定。在2008年，Goddard等人改進了上述演算法並做到最多5n步。我們將在本論文中提出一個採用不公平分散式排程器下最多4n步的自我穩定MDS演算法。 理想中，MDS演算法是希望能做到MDS-靜止的，亦即，若分散式系統的初始組態已經是一個MDS，則演算法將不執行任何動作。值得注意的是，在正常模式中，一個節點只能取得其一步內鄰居的資訊，我們稱這些資訊為1步資訊。不幸的是，在本論文中，我們將證明：1步資訊不足以建立一個MDS-靜止的演算法。在本論文中，我們將討論此一問題，並針對自我穩定MDS演算法提出一個新的性能評量，稱為穩定性。我們推廣這部份的結果至其他自我穩定演算法，並將自我穩定演算法分類為四個層次。特別的是，我們將證明：在2步資訊模式下，可建構出自我穩定MDS-靜止的演算法，且其穩定時間之上界為2n步。 在2005年，Xu提出了圖的帶正負號星控制集的概念，在2007年，Wang給出了完全圖的帶正負號控制數，詳細定義請參見本論文的第五章。在2010年，Atapour等人定義了帶正負號星控制劃分數，並利用完全圖具有可完全1-因子分解或可完全漢米爾頓圈分解的性質，計算出完全圖的帶正負號星控制劃分數。在2012年，我與印度學者Chelvam等人合作，定義了有向圖的帶正負號星控制數，給出了全部有向凱式圖的帶正負號星控制數，與無向凱式圖的帶正負號星控制數的部份結果，並推廣這些結果至可完全{2,1}-因子分解的正則圖。

The study of the domination problem in graph theory began in the nineteen-sixties. A distributed system such as an ad hoc network can be modeled by an undirected simple graph G = (V;E), where V represents the set of nodes (i.e., processes) and E represents the set of interconnections between processes of the distributed system. A subset D of the vertex set V of G is a dominating set if each vertex v in V is either a member of D or adjacent to a vertex in D. A dominating set of G is a minimal dominating set (MDS) if none of its proper subsets is a dominating set of G. An MDS has an application of clustering in wireless networks and is maintained for minimizing the number of required resource centers. Self-stabilization is a concept of designing a distributed system for transient fault toleration and was introduced by Dijkstra in 1974. A distributed system is self-stabilizing if, regardless of its initial configuration, the system is guaranteed to reach a legitimate (i.e., correct) configuration in a finite time. Here the system configuration consists of the state of every process. A self-stabilizing algorithm comprises a collection of rules and each rule has a trigger precondition and an action. The action changes the state of the node by updating its variables. An execution of a rule is called a move. The performance of the proposed algorithms of this thesis is measured by the total number of moves executed by an algorithm. Various execution models have been used in self-stabilizing algorithms and these are encapsulated with the notion of daemons. A daemon can be fair or unfair. It is well-known that an unfair distributed daemon is more practical than other types of daemons. Let n denote the number of nodes (processes) in a given distributed system. In 2007, Turau proposed the first linear-time self-stabilizing algorithm for the MDS problem under an unfair distributed daemon; this algorithm stabilizes in at most 9n moves. In 2008, Goddard et al. improved the result to a 5n-move algorithm. It is interesting to develop an algorithm that takes less moves than the best known result—5n moves using an unfair distributed daemon. In this thesis, we will present a 4n-move self-stabilizing MDS algorithm using an unfair distributed daemon. It is desired that an MDS algorithm is MDS-silent, which means that if the original configuration of the distributed system is already an MDS, then the algorithm should not make any move. Note that in the normal model, a node can only access the information of its 1-hop neighbors and we call such information distance-1 information. Unfortunately, in this thesis we will prove that distance-1 information is not sufficient for building up an MDS-silent algorithm for a distributed system. In this thesis, we will discuss this problem and propose a new performance measure, called stableness, for self-stabilizing MDS algorithms. We also generalize this result to categorize all self-stabilizing algorithms into four levels. In particular, we will show that a self-stabilizing MDS-silent algorithm can be built up under the distance-2 model and the stabilizing time is upper bounded by 2n. Let G be a simple connected graph with vertex set V (G) and edge set E(G). A function f : E(G)→{-1,1} is called a signed star dominating function (SSDF) on G if Σ_{e in E}(v) f(e) >=1 for every v in V(G), where E(v) is the set of all edges incident to v. The signed star domination number of G is defined as SS(G) = min weight sum of f which is an SSDF on G. Let Ω be a symmetric generating subset of nonidentity elements of Γ. The Cayley graph Cay(Γ; Ω) corresponding to Γ and Ω is the ordinary graph with vertex set Γ and edge set E. In this thesis, we obtain exact values for the signed star domination number of all Cayley digraphs CayD(Γ; S) and certain classes of Cayley graphs Cay(Γ; Ω), which is later generalized to f2; 1g-factorable graphs. Note that these solutions are from a joint work with Chelvam and Kalaimurugan.