雙分圖著色之錯誤抑制自我穩定演算法

A fault-containing self-stabilizing algorithm

劉瑜琳(Yu-Lin Liu)

指導教授 ： 林基成 ； 黃哲志

元智大學/資訊學院/資訊工程學系/碩士(2000年)

摘要

本篇論文針對雙分圖著色問題，提出一個具有錯誤抑制的自我穩定演算法。一個分散式系統在任意的初始狀態下，不需外力的介入便可自動調整錯誤，並保證在有限步驟之內，使系統恢復到合理狀態。實際上，一個處於合理狀態的分散式系統，其一次只有一個node發生transient fault的機率會遠大於多個nodes同時發生transient fault的機率，因此對single fault改善的演算法會較具有時價值。到目前為止，針對雙分圖著色問題所設計的自我穩定演算法，在發生single transient fault之後，會有n-2個nodes的資料會被改變( n為系統中所有node之個數)且其stabilization time為W(n2)。而本篇之演算法，只有一個nodes的資料會被改變且stabilization time亦縮為O(min(D2,n))。(D為maximum node degree )

關鍵字

自我穩定 ； 錯誤抑制 ； 雙分圖

並列摘要

Proposed here is a fault-containing self-stabilizing algorithm which induces a 2-coloring for a system with a bipartite graph topology. Our approach is taken after Gupta ,[2],[4],[5],[6] and our algorithm is an enhancement of that by [3]. In the single-fault situation, the stabilization time in the worst case of the algorithm in [3] is W(n2) and the contamination number is at least n-2, where n is the number of all nodes in the system; whereas the stabilization time of our algorithm is O(min(D2,n)), and the contamination number is 1。

並列關鍵字

Self-stabilizing ； fault-containing ； bipartite graphs

參考文獻

[1] E.W.Dijkstra, “Self-Stabilizing System in Spite of Distributed control.”

[3] S Sur and PK Srimani. “A self-stabilizing algorithm for coloring bipartite

graphs.” Information Sciences, 69:219-227, 1993.

[6]S Ghosh, A Gupta. “An exercise in fault-containment: self-stabilizing leader election.” Information Processing Letters, 59:281-288, 1996.

Communication of ACM, Vol.17, No.11, p.643-644, 1974