在樹狀網路找雙中心點的自我穩定演算法

A Self-stabilizing Algorithm which Finds 2-centers of Trees

陳學仁(Hsueh-Jen Chen)

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

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

摘要

本篇論文設計了一個可以在樹狀網路找雙中心點（2-center）的自我穩定演算法（self-stabilizing algorithm）。我們
的演算法是以參考文獻[13, 14]所提出的演算法為基礎。參考文獻[13, 14]所提出的演算法可以使我們找出樹狀網
路的中心點（center）。如果我們將一棵樹（tree）從它的中心點部分作切割，則我們會得到兩棵子樹(subtrees)。
本篇論文的主要工作之一就是要證明：如果我們從兩棵子樹分別挑出一個中心點，則此兩點構成樹的一組雙中
心點。因此我們設計我們的演算法使它可以〝察覺〞到兩棵子樹，而且能分別在兩棵子樹中找到中心點。

關鍵字

分散式系統 ； 自我穩定演算法 ； 中心點 ； 雙中心點 ； 樹

並列摘要

In this paper, we design a self-stabilizing algorithm which
finds a 2-center for a distributed system with a tree topology.
Our algorithm is based on the algorithm in [13, 14]. The latter
algorithm enables us to find the center (or centers) for the
tree. If we sever the tree from the center, we obtain two
subtrees. One of the major works in this paper is to show that
if we pick a center from each subtree, the two picked centers
will constitute a 2-center for the original tree. With this in
mind, we design our algorithm, so that it is equipped with the
ability of " sensing " the two subtrees and then finding out a
center in each of them.

並列關鍵字

distributed systems ； self-stabilizing algorithms ； centers ； 2-centers ； trees

參考文獻

[2] N. Christofides. GRAPH THEORY: An Algorithmic Approach, pp.101.

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

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

[6] AK Datta, TF Gonzalez, and V Thiagarajan. Self-stabilizing algorithms for tree metrics. ICAPP95 IEEE First International Conference on Algorithms and Architectures for Parallel Processing, pages 471-479, 1995.

[7] S Dolev, A Israeli, and S Moran. Self-stabilization of dynamic systems assuming only read/write atomicity. Distributed Computing, 7:3-16, 1993.