在樹狀網路上尋找中心點的高率效錯誤抑制自我穩定演算法

An efficient fault-containing self-stabilizing algorithm for finding centers on a tree network

張書銘

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

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

摘要

本篇論文中，我們設計一個在分散式系統中尋找中心點的錯誤抑制自我穩定演算法，我們的演算去在單一錯誤下，worse case的stabilization time是O(∆)，∆是最大的degree number，優於其它同一問題的研究，而contamination number是１。

關鍵字

self-stabilizing ； fault-containing ； center

並列摘要

In this thesis, we design a fault-containing self-stabilizing algorithm which finds centers for a distributed system. Our algorithm is based on the algorithm in [5]. In the single-fault situation, the worst case stabilization time of our algorithm is O(∆) which is much better than all existing algorithms for the same problem, where ∆ is the maximum node degree. The contamination number of our algorithm is 1.

並列關鍵字

HASH(0xcfd158c)

參考文獻

[1] E. W. Dijkstra, ``Self-stabilizing system in spite of distributed,"Commun. ACM,vol. 17, no. 11, pp. 643-644, 1974.

[3] E. W. Dijkstra, ``A belated proof of self-stabilization,''

Distrib. Comput., vol. 1, no. 1, pp. 5-6, 1986.

[6] S. Ghosh and A. Gupta, ``An exercise in fault-containment:

[9] A. Gupta, Fault-containing in self-stabilizing distributed