最大配對問題的錯誤抑制自我穩定演算法

A Fault-Containing Self-Stabilizing Algorithm for Maximal Matching

張昇亮(Sheng-Liang Chang)

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

元智大學/工程學院/電機與資訊工程研究所/碩士(1998年)

摘要

在本篇論文中，我們提出一個具錯誤抑制功能的分散式系統中最大配對問題的自我穩定演算法。當系統只有單一節點發生transient fault的時候，我們的演算法能夠抑制主要變數的錯誤，使錯誤不會擴散並且污染到其他的節點。在實際情況?芊A系統會有相當高的機率發生單一錯誤。因為我們的演算法能更有效地處理這種情況，所以此演算法更具備實用上的價值。

關鍵字

自我穩定演算法 ； 最大配對 ； 錯誤抑制

並列摘要

In this thesis, we propose a fault-containing self-stabilizing algorithm for maximal matching in a distributed system. When only one node in the system is incurred a transient fault, our algorithm is capable of containing the fault of its primary variable so that the fault does not spread out and contaminate other nodes. In practice, the probability for a system to encounter the single-fault situation is quite high. Since our algorithm cope with this situation more effectively, it is more valuable from practical point of view.

並列關鍵字

self-stabilizing algorithm ； maximal matching ； fault containing

參考文獻

[DIJ74] E.W.Dijkstra "Self-Stabilizing System in Spite of Distributed control."

[DIJ86] E.W.Dijkstra "A Belated Proof of Self-Stabilization."Distributed

[MFA94] Mitchell Flatebo and Ajoy Kumar Datta,Two-State Self-Stabilizing

Algorithms for Token Rings,(1994) IEEE.

in Concurrency."Proc.3rd ACM Symposium on Principles of