在非公平central demon計算模式下運作的可以尋找所有橋的自我穩定演算法

A Self-stabilizing Bridge-finding Algorithm under the Non-Fair Central Demon Model

紀雁綺(Yen-Chi Chi)

指導教授 ： 林基成

共同指導教授 ： 黃哲志

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

https://doi.org/10.6838/YZU.2007.00013

摘要

Karaata與Chaudhuri在1999年已設計了一個在fair demon計算模式下尋找橋的自我穩定演算法。在本論文中，我們將Karaata與Chaudhuri的演算法修改為一個在 (non-fair) central demon計算模式下尋找橋的自我穩定演算法。此外，我們提供了此演算法的正確性証明。如同Karaata與Chaudhuri的演算法，我們的演算法也假設系統中已存在一個breath-first search spanning tree。

關鍵字

尋找橋 ； 自我穩定 ； Fair demon計算模式 ； Central demon計算模式

並列摘要

A self-stabilizing bridge-finding algorithm under the fair demon model was designed by Karaata and Chaudhuri in 1999. In this thesis, we modify Karaata and Chaudhuri’s algorithm into a self-stabilizing bridge-finding algorithm under the (non-fair) central demon. In addition, a correctness proof of the algorithm is provided. Like Karaata and Chaudhuri’s algorithm, our algorithm also assumes that a breadth-first search spanning tree of the system is available.

並列關鍵字

Bridge finding ； Self-stabilization ； Fair demon ； Central demon

參考文獻

[1] Edsger W. Dijkstra: Self-stabilizing systems in spite of distributed control. Communications of the Association of the Computing Machinery 17 (11), 643-644, (1974)

[3] Edsger W. Dijkstra: A belated proof of self-stabilization. Distributed Computing 1 (1), 5-6 (1986)

[4] Shing-Tsaan Huang and Nian-Shing Chen: Self-stabilizing depth-first token circulation on networks. Distributed Computing 7 (1), 61-66 (1993)

[5] Anish Arora and Mohamed Gawdat Gouda: Distributed reset. IEEE Transactions on Computers 43 (9), 1026-1038 (1994)

[6] Lih-Chyau Wuu and Shing-Tsaan Huang: Distributed self-stabilizing systems. Journal of Information Science and Engineering 11, 307-319 (1995)