在樹狀網路尋找雙中心點的一個允許不公平排程之自我穩定演算法

A self-stabilizing algorithm for finding 2-center in a tree which allowed unfair demon

李汪得(Uang-Der Lii)

指導教授 ： 林基成

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

摘要

本論文要設計一個在樹狀結構的分散式系統中，允許不公平排程尋找雙中心點的自我穩定演算法。我們的演算法是以[4, 5, 6, 7, 8]的演算法為基礎。Karaata演算法讓我們能找到樹狀網路的中心點（center），黃、林、陳演算法則讓我們能進一步找到樹狀網路的雙中心點（2-center）。在黃、林、陳的演算法中，假設系統為公平排程。而我們的演算法，即使在不公平的排程之下，也能達到合理狀態。當系統的運算停止，系統鎖死，即為合理狀態，此時系統便能正確辨識出樹狀網路的雙中心點。

關鍵字

自我穩定演算法 ； 中心點 ； 雙中心點 ； 公平 ； 不公平

並列摘要

無資料

並列關鍵字

self-stabilizing algorithm ； center ； 2-center ； fair ； unfair

參考文獻

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

[2] EW Dijkstra. EWD391 Self-stabilizing systems in spite of distributed control. Selected Writings on Computing: A Personal Perspective, pages 41-46, 1982. EWD391’s original date is 1973.

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

[5] M.H. Karaata, S.V. Pemmaraju, S.C. Bruell and S. Ghosh, Self-stabilizing algorithms for finding centers and medians of trees. Technical Report TR94-03, University of Iowa, (1994).

[6] M.H. Karaata, S.V. Pemmaraju, S.C. Bruell and S. Ghosh, Self-stabilizing algorithms for finding centers and medians of trees. SIAM Journal on Computing Volume 29 (2), 600-614, (1999).