在雙向一致任意大小的環上之具自我穩定能力之相位同步

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：39

、訪客IP：13.58.82.79

姓名

柳青浩(Ching-Hao Liu) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

在雙向一致任意大小的環上之具自我穩定能力之相位同步
(Self-stabilizing phase synchronization on bidirectional uniform rings of any size)

相關論文

★ 在一致的環狀串列上具自我穩定能力之交換配對	★ 低空間需求之分散式最佳同步交互器
★ 利用區塊人臉特徵為基礎之混合式人臉辨識系統	★ 無線射頻辨識系統反碰撞協定
★ 同儕網路虛擬環境之高效能安全設計	★ 無線感測網路指向天線定位機制
★ 新一代GPS導航系統	★ 支援學習探索發問式閱讀之電子書
★ 評估電子書的螢幕數量及視窗管理影響學生學習及理解之成效	★ 運用體感互動建立學習系統中肢體與情境經驗之學習成效分析
★ 讓思考看得見：基於案例式推理學習的心思記錄器	★ 朝向利他性的學習評量系統
★ 可編輯情境的學習舞台	★ 展現寫作思考流程的範文閱讀平台

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

本篇論文中，我們提出了一個演算法來解決在雙向一致任意大小的環上去同步化相位時鐘的問題。此演算法擁有自我穩定的能力。也就是說，無論在什麼樣的開始設定下，所有處理器的時鐘最終將會有相同的值。
與以往的隨機演算法的方式解決此一問題不同之處在於，以往的演算法從頭到尾都是倚靠隨機選取的方式，來決定下一時間相位時鐘的值的變化；而我們僅用隨機選取的方式來打破對稱的情況，扣除打破對稱情況的動作外，此系統將非隨機地運作。我們用了72個額外的狀態(排除時鐘變數在外)且最差情況下達到穩定所需的時間為O(n^3)。

摘要(英)

In this thesis, we propose an algorithm to solve the problem of synchronizing phase clock on bidirectional uniform rings of any size. The algorithm has the self-stabilizing ability. That is, no matter under what initial configuration, clocks on every processors will have the same value eventually.
The difference with previous randomized algorithms is that previous ones are totally randomized to decide the value of phase clock of the next step. We just use randomization to break symmetry. Except symmetry breaking, the system works deterministically. We use 72 additional states(exclude the clock variable) and the stabilizing time in the worst case is O(n^3).

關鍵字(中)

★ 一致環
★ 相位同步
★ 自我穩定演算法
★ 隨機演算法

關鍵字(英)

★ Randomized algorithm
★ Uniform ring
★ Phase synchronization
★ Self-stabilization

論文目次

Chapter 1 Introduction…………………………………………1
Chapter 2 Computational Model……………………………… 4
Chapter 3 Protocol………………………………………………6
3.1 Main concept………………………………………………6
3.2 PFC scheme…………………………………………………6
3.3 Variables………………………………………………… 8
3.4 Tree structure……………………………………………9
3.5 Detailed protocol………………………………………12
3.6 Description of protocol………………………………16
Chapter 4 Correctness Proof…………………………………19
Chapter 5 Complexity Analysis………………………………27
Chapter 6 Conclusions…………………………………………29
References……………………………………………………… 30

參考文獻

[AD96] G. Alari, A.K. Datta, “Almost Two-State Self-Stabilizing for Token Rings”, IEEE, 1996.
[ADG91] A. Arora, S. Dolev, M.G. Gouda, “Maintaining Digital Clocks In Step”, Parallel Processing Letters, vol. 1, pp. 11-18, 1991.
[BDPV98] A. Bui, A.K. Datta, F. Petit, V. Villain, “Space Optimal and fast self-stabilizing PIF in tree networks. Technical Report RR 98-07, LaRIA, University of Picardie Jules Verne, 1998. Submitted.
[CDPV01] A. Cournier, A.K. Datta, F. Petit, V. Villain, “Self-Stabilizing PIF Algorithm in Arbitrary Rooted Networks”, 21st International Conference on Distributed Computing Systems (ICDCS 2001), pages 91-98, 2001.
[Cha82] E. Chang, “Echo algorithms：depth parallel operations on general graph”, IEEE Transactions on Software Engineering, SE-8：391, 1982.
[Dij74] E.W. Dijkstra, "Self Stabilizing Systems in Spite of Distributed Control." Comm. ACM, vol. 17, pp. 643-644, 1974.
[GH90] M.G. Gouda, T. Herman, “Stabilizing Unison”, Information Processing Letters, vol. 35, pp. 171-175, 1990.
[Her90] T. Herman, “Probabilistic Self-Stabilization”, Information Processing Letters, 1990.
[Her01] T. Herman, “A Phase Clock Tutorial”, 2001.
[HG95] T. Herman and S. Ghosh, "Stabilizing phase-clocks," Information Processing Letters, vol. 54, pp. 259-265, 1995.
[HL97] S.T. Huang, T.J. Liu, “Four-state stabilizing phase clock for unidirectional rings of odd size”, Information Processing Letters, 1997.
[HL99a] S.T. Huang, T.J. Liu, “Self-stabilizing 2m-clock for unidirectional rings of odd size”, Distributed Computing, 1999.
[HL99b] S.T. Huang, T.J. Liu, “Self-stabilizing k-clock for unidirectional rings”, Technical Report, Tsing-Hua University, 1999.
[Hua93] S.T. Huang. “Leader election in uniform rings”, ACM Transactions on Programming Languages and Systems. v15, n3, p563-573. July 1993.
[Jia99] J.R. Jiang, “Self-stabilizing, randomized k-value unison clocks for unidirectional uniform rings,” in Proceedings of 11th International Conference on Parallel and Distributed Computing and Systems, Boston, MA, Nov. 1999.
[Kes88] J. L. W. Kessels. “An exercise in proving self-stabilization with a variant function”, Information Processing Letters.29 , p39-42, 1988.
[LH01] T.J. Liu, S.T. Huang, “Phase Synchronization on Asynchronous Uniform Rings with Odd Size”, IEEE Transaction on Parallel and Distributed Systems, vol. 12, no. 6, June, 2001.
[LS95] C. Lin and J. Simon, "Possibility and Impossibility Results for Self-Stabilizing Phase Clocks on Synchronous Rings," In Proc. of 2nd Workshop on Self-Stabilizing Systems, pp. 10.1-10.15, 1995.
[MOY96] A. Mayer, R. Ostrovsky, M. Yung, “Self-Stabilizing Algorithms for Synchronous Unidirectional Rings”, 1996.
[Seg83] A. Segall. “Distributed network protocols”, IEEE Transactions on Information Theory, IT-29：23, 1983.

指導教授

黃興燦(Shing-Tsaan Huang)

審核日期

2003-6-22

推文