低空間需求之分散式最佳同步交互器

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：13

、訪客IP：3.145.60.29

姓名

賴博淵(Pao-Yuan Lai) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

低空間需求之分散式最佳同步交互器
(Optimal Alternators with Reduced Space Complexity)

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

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

摘要(中)

從排程的角度來看，分散式系統中的交互器（alternator）其實可視為一種排程器（scheduler），它確保每次所排定能夠執行臨界步驟的處理器構成一個獨立集而且每個處理器能夠隨著無窮的計算序列執行無限次數。先前的研究指出了排程與塗色之間的關聯，從這當中我們證明了一個具備公平性的最佳排程必定具備強公平性並探究對於一般情形下的交互器設計其最佳塗色為何。
在原先提出用以設計俱備最佳公平性之交互器的一般性方法中，空間需求主要來自最佳塗色與相位同步，我們進一步移除相位同步的步驟使得空間需求降低，然後提出一個改良過的一般性設計方法。接著以這個方法為基礎，我們展示了一個適用於單向一致任意大小之環狀拓墣結構上空間需求最少的最佳交互器並分析其共時性（concurrency）與公平性（fairness）。研究成果較先前改良許多，無論是從空間複雜度、模型假設…等等來比較均是如此。

摘要(英)

From the viewpoint of scheduling, an alternator in a distributed system can be regarded as a scheduler which ensures that each time the scheduled processors executing their critical steps constitute an independent set and that each processor is scheduled infinitely often along any infinite computation sequence. Recent work relates scheduling to coloring. According to the relation, we prove that an optimal fair
scheduling is strongly fair and clarify what is an optimal coloring in general for the design of optimal 1-fair alternators.
The space complexity of the previous proposed general approach to designing optimal 1-fair alternators comes from an optimal coloring and clock synchronization.We further remove the need to perform clock synchronization. This leads to an improved general approach to designing optimal 1-fair alternators with reduced space
complexity.
Based on the improved general approach, we demonstrate an optimal two-state alternator on synchronous uniform unidirectional rings of any size and analyze its concurrency as well as fairness. Our results greatly dominate the previous work in terms of space complexity, model assumptions and so forth.

關鍵字(中)

★ 交互器
★ 作業率
★ 自我穩定
★ 塗色問題
★ 局部互斥
★ 公平性
★ 排程

關鍵字(英)

★ graph homomorphism
★ scheduling
★ r-coloring
★ operating rate
★ alternator
★ fairness
★ self-stabilization
★ local mutual exclusion
★ interleaved multicoloring

論文目次

1. Introduction...............................................................1
2. Scheduling and coloring............................................2
3. The improved general approach................................5
4. The optimal two-state design on rings of any size.....9
5. Correctness of the optimal two-state design.............11
6. Analysis of the optimal two-state design..................12
7. Comparisons with the previous work.......................14
8. Conclusion...............................................................16
References...................................................................16

參考文獻

[1] V. C. Barbosa, An atlas of edge-reversal scheduling, Chapman & Hall/CRC, pp. 34, 2000
[2] V. C. Barbosa, The interleaved multichromatic number of a graph, Annals of Combinatorics 6 pp. 249-256, 2002
[3] J. Beauquier, A.K. Datta, M. Gradinariu and F. Magniette, Self-stabilizing local mutual exclusion and daemon refinement, DISC’00 Proc. the 14th Int'l Symposium on Distributed Computing, pp. 223-237, 2000.
[4] Bui, A. Datta, F. Petit and V. Villain, State-optimal snap-stabilizing PIF in tree networks, Proc. the 3rd Workshop on Self-stabilizing Systems (published in association with Proc. The 19th IEEE International Conference on Distributed Computing Systems), pp. 78-85, 1999.
[5] E.W. Dijkstra, Self-stabilizing systems in spite of distributed control, Comm. ACM 17 643-644, 1974.
[6] M.G. Gouda and F. Haddix, The Alternator, ICDCS Workshop on Self-Stabilizing Systems, 1999.
[7] F. Haddix, Alternating parallelism and the stabilization of distributed systems, Ph. D. Dissertation, Department of Computer Sciences, the University of Texas 17 at Austin, Austin, Texas, 1998.
[8] T. Herman, Probabilistic Stabilization, Information Processing Letters, 35: 63-67, 1990.
[9] S.T. Huang, The fuzzy philosophers, in: IPDPS 2000 Workshops, Cancun, Mexico, Lecture Notes in Comput. Sci., Vol. 1800, Springer, Berlin, 2000, pp. 130-136.
[10] S.T. Huang and B.W. Chen, Optimal 1-fair Alternators, Information Processing Letter, pp. 159-163, 2001.
[11] S.T. Huang, Y.S. Huang and S.S. Hung, Alternators on Uniform Rings of Odd Size, Distributed Computing, 2002.
[12] H. Kakugawa and M. Yamashita, Self-stabilizing local mutual exclusion on networks in which process identifiers are not distinct, the 21st IEEE Symposium on Reliable Distributed Systems, Oct. 2002.
[13] H.G. Yeh and X. Zhu, Resource-sharing system scheduling and circular chromatic number, submitted to Theoretical Computer Science, under revision.

指導教授

黃興燦(Shing-Tsaan Huang)

審核日期

2004-7-6

推文