(清大紙本館藏)
      系統編號:GH000848310
論文名稱:自我穩定之邊緣標記與其應用
The Self-stabilizing Edge-Token and Its Applications
研究生:洪淑慎 Su-Shen Hung
指導教授:黃興燦 Shing-Tsaan Huang
學位類別(Degree):博士
學校名稱(School):國立清華大學
系所名稱(Department):資訊工程學系
學號(Student Number):848310
畢業學年度(Academic Year):93
語文別(Language):中文
英文
出版年(Thesis Year):民94
關鍵字:分散系統 Distributed System
自我穩定 Self-Stabilization
邊緣標記 Edge Token
電子全文說明(Fulltext description):封面
摘要
誌謝辭
目錄
第一章
第二章
第三章
第四章
第五章
第六章
第七章
第八章
參考文獻
附錄

  論文頁數(Page):93
摘要:本論文首先提出邊緣標記(Edge Token)的觀念,同時採用自我穩定(Self-Stabilizing)演算法實施。邊緣標記可應用於許多傳統的分散系統問題上,如環狀同向問題( Ring Orientation ) 、主管選任問題( Leader Election )、標記環繞問題( Token Circulation )以及相鄰同步問題( Neighborhood Synchronization )。
無論系統起始狀態如何,自我穩定系統保證在有限時間內將系統收斂至穩定狀態(Legitimate State)。也就是說在系統發生錯誤時,無需外部介入自我穩定系統即可自行恢復正常。此特性是分散系統考慮容錯功能時非常重要的需求。
將分散系統視為一個含有節點(Node)與邊緣(Edge)連接的圖形。而邊緣標記就是在每一個邊緣上保持一個標記( Token ),此標記只能屬於由邊緣所連接的兩節點其中一個節點。邊緣標記可因應用需求在兩個節點間互傳。基於邊緣標記的互斥特性,運用不同的邊緣標記保留策略可以有效解決許多傳統的問題。
在論文裡,我們共提出四個應用邊緣標記觀念的自我穩定演算法,分別解決環狀同向問題、樹狀主管選任問題、樹狀標記環繞問題以及樹狀相鄰同步問題。這些演算法都是個體無差異演算法 (Uniform Algorithm),同時使用讀寫分制方法(Read/Write Atomicity)運作於分散排程系統。特別的是,在所提出的演算法中,每個節點只需參考自己的狀態就可以決定後續運作,因此方法非常簡單而且直覺。其結果不論在收斂速度或演算法精簡度上都超越既有的方法。此外,我們亦提出另外二個相關問題的自我穩定演算法,包括平面圖形塗色法以及非應用邊緣標記之相鄰同步演算法。
In this dissertation, we first propose the concept of edge token and present a self-stabilizing algorithm to implement it. Based on the concept of edge token, many traditional problems are reconsidered and are solved more elegantly, such as ring orientation problem, leader election problem, token circulation problem and neighborhood synchronization problem.
A self-stabilizing system guarantees to converge to a legitimate state in a finite time no matter what initial state it may start with. An attractive feature for a self-stabilizing system is that the system can recover from transient faults automatically without any outside intervention. This feature is highly desirable for distributed systems with fault-tolerance consideration.
Consider the distributed system as a connected graph with processes (or nodes) and edges. An Edge Token with respect to an edge is a token maintained by the two processes connected by the edge. The token is held by one of the two processes and is passed between them as needed. Due to the exclusive property of edge token, different kinds of strategies for edge token holding can be used to solve the traditional problems efficiently.
In the dissertation, we propose four self-stabilizing algorithms based on edge tokens: ring orientation, leader election for trees, token circulation for trees and neighborhood synchronization for trees. All the proposed algorithms are uniform and work under the distributed scheduler with read/write atomicity. Moreover, since each process only refers to its local state, these algorithms are simple and intuitive. The results are better than the previous works either in time complexity or in their elegancy. Beside that, a related self-stabilizing algorithm for planar graph coloring is proposed and the approach for neighborhood synchronization that does not use edge tokens is also given in Appendix for reference.
論文目次
Table of Content
:
Chapter 1 Introduction………………………………………………1
1.1 The self-stabilization system………………………………2
1.2 The self-stabilization Edge Token and related problems5
1.2.1 Ring orientation problem……………………………………6
1.2.2 The leader election problem for uniform trees………7
1.2.3 The token circulation problem……………………………7
1.3 The related mutual exclusion problems……………………8
1.3.1 The neighborhood synchronization problem………………9
1.3.2 The planar graph coloring problem…………………… 10
1.4 Organization of the dissertation……………………………11
Chapter 2 The Self-Stabilizing Edge Token……………………13
2.1 Introduction………………………………………………………13
2.2 The self-stabilizing Edge Token algorithm………………15
2.3 Correctness proof and Time complexity analysis…………19
2.4 Conclusion………………………………………………………………21
Chapter 3 A self-stabilizing uniform ring orientation
algorithm by edge tokens…………………………22
3.1. Introduction……………………………………………………………22
3.2. The ring orientation algorithm……………………………23
3.3. Correctness proof and complexity analysis………………26
3.3.1 Correctness proof……………………………………………26
3.3.2 Complexity analysis…………………………………………29
3.4. Conclusion……………………………………………………………30
Chapter 4 A self-stabilizing leader election algorithm
for trees by edge tokens…………………………31
4.1. Introduction…………………………………………………………31
4.2. The leader election algorithm for trees………………32
4.3. Conclusion……………………………………………………35
Chapter 5 A self-stabilizing token circulation algorithm
for trees by edge tokens……………………………...36
5.1.Introduction……………………………………………………36
5.2. The token circulation algorithm…………………………38
5.3. Correctness proof and complexity analysis……………41
5.3.1 Correctness proof…………………………………………42
5.3.2 Complexity analysis………………………………………43
5.4. Conclusion……………………………………………………46
Chapter 6 A self-stabilizing neighborhood synchronization
algorithm for trees by edge tokens …………………47
6.1 Introduction……………………………………………………47
6.2 The proposed algorithm………………………………………49
6.3 Correctness proof and Analysis……………………………50
6.4 Conclusions……………………………………………………52
Chapter 7 A uniform self-stabilizing planar graphs
coloring algorithm ……………………………………53
7.1 Introduction……….…………………………………………53
7.2 The proposed algorithm………………………………………55
7.3 The Correctness Proof and Analysis………………………60
7.4 Conclusion………………………………………………………64
Chapter 8 Conclusions and future works………………………65
8.1 Conclusions……………………………………………………65
8.2 Future works……………………………………………………67
References…………………………………………………………68
Appendix……………………………………………………………72
參考文獻
Reference
:
[AN99]
A. Arora and M.Nesterenko. Stabilization-preserving atomicity refinement. DISC’99 Proceedings of the Thirteenth International Symposium on Distributed Computing, pp. 254-268, 1999.
[AS96]
G. Antonoiu and P. K. Srimani, A Self-stabilizing leader election algorithm for tree graphs, Journal of Parallel and Distributed Computing, 34, p.227-232, 1996.
[BD95]
J. Beaquier J, O. Debas, An optimal self-stabilizing algorithm for mutual exclusion on bidirectional non uniform rings, Proc. Second Workshop Self-Stabilizing System, 1995.
[BDGM00]
J. Beauquier, A. K. Datta, M. Gradinariu, and F. Magniette. A Self-stabilizing local mutual exclusion and daemon refinement. DISC’00 Proceedings of the Fourteen International Symposium on Distributed Computing, 2000.
[BP89]
J. E. Burns, J. Pachl, Uniform self-stabilizing rings. ACM Trans. Program Lang. Syst. 11(2): 330-344, 1989.
[D71]
E.W. Dijkstra Hierarchical Ordering of Sequential Processes. Acta Informatica 1 (1971), 115-138
[D74]
E.W. Dijkstra. Self stabilizing systems in spite of distributed control. Communications of the Association of the Computing Machinery, 17:643-644, 1974.
[DI97]
S. Dolev, A. Israeli, and S. Moran. Uniform dynamic self-stabilizing leader election, IEEE Trans. On Parallel and Distributed Systems. Vol.8, No 4, April 1997.
[DIM93]
S. Dolev, A. Israeli, and S. Moran, Self-stabilizing of dynamic systems assuming only read/write atomicity. Distributed Computing, 7:3-16, 1993.
[DJPV00]
A. K. Datta, C. Johnen, F. Petit and V. Villain, Self-stabilizing depth-first token circulation in arbitrary rooted networks. Distributed Computing, 13: 207-218, 2000.
[GK93]
S. Ghosh and M.H. Karaata, A self-stabilizing algorithm for coloring planar graph, Distributed Computing, pp. 7:55-59, 1993.
[GH99]
M. G. Gouda and F. Haddix. The alternator. Proc. the 3rd Workshop on Self-stabilizing Systems (published in association with Proc. the 19th IEEE International Conference on Distributed Computing Systems), pp. 48-53, 1999.
[GT00]
M. Gradinariu and S. Tixeuil, Self-stabilizing vertex coloring of arbitrary graphs, OPODIS’2000, pp.17-36, 2000.
[H00]
S. T. Huang. The fuzzy philosophers. Lecture notes in Computer Science 1800, IPDPS 2000 Workshops, Cancun, Mexico, May 1-5, 2000, pp. 130-136.
[H94]
J. H. Hoepman, Uniform deterministic self-stabilizing ring orientation on Odd-Length Ring, Proc. Eighth Int’l Workshop Distributed Algorithms, pp.265-279, 1994.
[H98]
J. H. Hoepman, Self-stabilizing ring orientation using constant space, Information and Computation, Vol.144, No 1 ,pp. 18-39, 1998.
[HC00]
S. T. Huang and B. W. Chen. The optimal 1-fair alternators. Information processing Letter. 2000.
[HC93]
S. T. Huang and N. S. Chen, Self-stabilizing depth-first token circulation on networks. Distributed Computing, 7:61-66, 1993.
[HJS03]
S.T. Hedetniemi, D.P. Jacobs and P.K. Srimani, Linear time self-stabilizing colorings, Information Processing Letters, 87:251-255, 2003.
[HP92]
D. Hoover and J Poole. A distributed self-stabilizing solution to the dining philosophers problem. Information Processing Letters, 41:209-213, 1992.
[HR96]
H. J. Hoover and P. Rudnicki, Uniform self-stabilizing orientation of unicyclic networks under read/write atomicity. Chicago Journal of Theoretical Computer Science, 1996.
[HW97]
S. T. Huang and L.C. Wuu, Self-stabilizing token circulation in uniform networks. Distributed Computing, 10:181-187, 1997.
[HWT94]
S. T. Huang, L.C. Wuu and M. S. Tsai, Distributed execution model for self-stabilizing systems, Proc. of the 14th IEEE International Conference on Distributed Computing System, 1994.
[IJ90]
A. Israeli and M. Jalfon, Self-stabilizing ring orientation, Proc. Fourth Int’l Workshop Distributed Algorithms, pp. 1-14, 1990.
[IJ93]
A. Israeli and M. Jalfon, Uniform self-stabilizing ring orientation, Information and Coputation, vol. 104, pp. 175-196, 1993.
[JABD97]
C. Johnen, G. Alari, J. Beaquier and A.K. Datta, Self-stabilizing depth-first token passing on rooted networks. In WDAG97 Distributed Algorithms 11th International Workshop Processings, Springer-Verlag LNCS:1320, pp. 260-274,1997.
[JADT99]
C Johnen, LO Alima, AK Datta, and S Tixeuil. Self-stabilizing neighborhood synchronizer in tree networks. In ICDCS99 The 19th IEEE International Conference on Distributed Computing Systems, pp. 487-494, 1999.
[JBD95]
C. Johnen and J. Beaquier, O. Debas, Space-efficient distributed self-stabilizing depth-first token circulation. In proceedings of the second Workshop on Self-Stabilizing Systems, p.4.1-4.15, 1995.
[JT95]
T.R. Jensen and B. Toft, Graph coloring problems, John Wiley & Sons, New York, 1995.
[L96]
N. Lynch, Distributed Algorithms, Morgan Kaufmann,1996.
[LH97]
T. J. Liu and S.T. Huang, Leader election in uniform trees, Proc. 10th International Conference on Parallel and Distributed Comuting Systems, pp. 477-180, 1997.
[P01]
F. Petit, Fast Self-stabilizing depth-first token circulation. The 5th International Workshop on Self-Stabilizing Systems (WSS '01), LNCS 2194, pp. 200-215, 2001.
[P97]
F. Petit, Highly space-efficient self-stabilizing depth-first token circulation for trees. In OPOSDIS'97, International Conference On Principles Of Distributed System Proc., p221-235. 1997.
[PV00a]
F. Petit, V. Villain, Time and space optimality of distributed depth-first token circulation algorithms. DIMACS Workshop on Distributed Data and Structures, Carleton Univerty Press, pp. 91-106, 1999. Also presented at Dagsthul Workshop on SS (October 2000).
[PV00b]
F. Petit, V. Villain, Optimality and self-stabilization in rooted tree networks. Parallel Processing Letters, 10(1):3-14, 2000.
[PV97]
F. Petit, V. Villain, Color optimal self-stabilizing depth-first token circulation. Third International Symposium on Parallel Architectures, Algorithms and Networks (I-SPAN'97), IEEE Computer Society Press, pp. 317-323, 1997.
[SR94]
S. Shukla, D.Rosenkrantz and S. Ravi, Development self-stabilizing coloring algorithms via systematic randomization. In Processing of the International Workshop on Parallel Processing, pp. 668-673, 1994.
[SS93]
S. Sur and P.K. Srimani, A self-stabilizing algorithm for coloring bipartite graphs. Information Science, 69:2219-227, 1993.
[TH95]
M. S. Tsai and S. T. Huang, Self-stabilizing ring orientation protocols, Proc. Second Workshop Self-Stabilizing System, 1995.
[UKY98]
N. Uemoto, H. Kakugawa, and M. Yamashita, A self-stabilizing ring orientation algorithm with a smaller number of processor States, IEEE Trans. On Parallel and Distributed Systems. Vol.9, June 1998.

                                                                                                                    
預覽及輸出檢索結果
記錄 欄位

本頁 1 筆
記錄 1 至 1
選擇之記錄
標題
全部欄位
選擇之欄位
CMARC 機讀格式 (BIG5碼)
CSMARC 機讀格式 (CCCII碼)
CMARC 機讀格式 (UNICODE)
USMARC 機讀格式 (BIG5碼)
USMARC 機讀格式 (CCCII碼)
USMARC 機讀格式 (UNICODE)
 e-mail 地址  
 e-mail 標題

系統規劃:國立清華大學圖書館
系統製作:飛資得資訊有限公司