具局部錯誤修正的自我穩定演算法應用於極小控制集

Abstract

極小控制集（minimal dominating set, MDS）在解決優化問題方面有廣泛的應用，特別是在分散式系統中。本論文以分散式系統作為應用背景，這些系統通常由多個相互連接的計算機節點組成，透過網絡進行通信和協作。然而，這種分散式環境中的系統設計面臨著多重挑戰，如節點故障、通信延遲和節點間的不一致性狀態。 為了應對這些挑戰，本研究採用了自我穩定演算法（self-stabilizing algorithms）。自我穩定演算法能夠使系統在面對節點狀態變化或故障時自動恢復到一個合法的運行狀態，而無需中央控制的介入。我們提出了兩種基於自我穩定演算法的設計，分別應用於不同距離的圖形模型，並證明他們皆能夠在距離為3的範圍內達到穩定狀態。其中，第二個演算法在距離為2的更短圖形模型上運行，但所需的移動次數和輪數的上界僅比第一個演算法高出常數倍。 此外，我們證明任何演算法穩定所需的時間都必然與節點數量成線性關係，因為無法輕易破壞圖形對稱性。在一個任意起始狀態下的圖形中，我們的第一個演算法從最近的邱等人[3]那篇研究最多需要$2n$的移動次數減少至$n$，而第二個演算法除了與先前在完全相同的衡量標準上進行比較外，還新增了一個重要特性:具有局部修正的能力，能有效地防止錯誤的傳播，因此，我們的演算法實際需要的穩定時間與系統中被修改（即出現錯誤）的節點數量成正比。

The minimal dominating set (MDS) is widely applied in optimization problems, particularly in distributed systems. This thesis focuses on distributed systems where multiple interconnected computing nodes communicate and collaborate via networks. However, designing systems in such distributed environments presents several challenges, including transient faults, communication delays, and inconsistent node states. To address these challenges, this study employs self-stabilizing algorithms. These algorithms enable systems to automatically recover to a legitimate configuration in response to node state changes or transient faults, without the need for centralized control intervention. We propose two self-stabilizing algorithms under different distance models, demonstrating their ability to achieve system stabilization within a distance of 3 hops. The second algorithm, although designed for a shorter distance-2 model, requires only a constant factor more moves and rounds than the first algorithm to stabilize. Furthermore, we prove that the stabilization time required by any algorithm must inherently scale linearly with the number of nodes, due to the difficulty in breaking graph symmetry. Starting from any initial configuration, we have reduced the number of moves required by the first algorithm from a maximum of $2n$ to $n$, improving upon the latest research by Chiu et al. [3]. Additionally, our second algorithm, while maintaining the same performance standards as the latest research by Chiu et al., introduces a significant new property: localized error correction. This feature effectively prevents error propagation, resulting in the stabilization time being proportional to the number of nodes that have been modified (i.e., contain errors).