建 立 一 深 先 樹 的 自 我 穩 定 演 算 法

A self-stabilizing algorithm for constructing depth-first trees

楊朝元(Chau-Yuan Yang)

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

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

摘要

本論文提出了一個在網路上建立深先搜尋樹（Depth-First Search Tree）的自我穩定演算法（self-stabilizing algorithm）。
自我穩定系統，就是系統起始的狀態可以是任何可能的狀態，但是在經過有限步驟的執行，整個系統會到達正確的狀態。而且系統就會一直維持在正確的狀態。
之前提出的相同研究需要nlog n的空間來儲存變數，我們的演算法只需要log n的空間就可以解決這個問題。

關鍵字

自我穩定 ； 深先樹

並列摘要

In this thesis, we propose a self-stabilizing algorithm for constructing depth-first trees.
In self-stabilizing system ,the initial state can be any kind of state . After finite time of move , the system will reach the legitimate state. And the system will state in legitima-te state.
In our algorithm , we only use log n space to solve the problem. The other one algori-
thm should used nlog n space to solve this problem.

並列關鍵字

self stabilizing ； depth first tree

參考文獻

[A89] Y. Afek and G. Brown. Self-stabilization of the alternating bit protocol. In

Proceedings of the 8th IEEE Symposium on Reliable Distributed Systems,

pages 80-83, 1989.

[A95] G Antonoiu and Pk Srimani. A self-stabilizing distributed algorithm to construct an arbitrary spanning tree of a connected graph. Computers and Mathematics with Application, 30:1-7, 1995

[B89] JE Burns and J Pachl. Uniform self-stabilizing rings. ACM Transactions on