樹狀網路上找尋中心點的有效率錯誤抑制自我穩定演算法

Abstract

本篇論文提一個在樹狀網路找中心點(centers)的自我穩定演算法，具有以下兩點特性：當系統發生 single transient fault ，(1)只有 faulty node 會去修正資料，(2)stabilization time 為 O(min(△2,n))，△為 maximal nod degree，n 為 nodes 的個數。若一分散式系統在任何起始狀態(initial states)下，皆能不經外力的介入，而在有限步驟之內恢復到正確的狀態，且一直維持在正確的狀態，我們稱這個系統為自我穩定系統(self-stabilizing system)。實際上，分散式系統一次只有一個 node 發生 transient faul 的機率大於多個 nodes 同時發生 transient faul。到目前為止在樹狀網路找中心點的自我穩定演算法，當系統發生 single transient faul 時，會有 O(n) 個 nodes 的資料被影響，而 stabilization time 為 O(n2)。