簡易檢索 / 詳目顯示

研究生: 劉康佑
論文名稱: 分散式容錯的K-互斥演算法研究
The Study of Distributed Fault-Tolerant K-Mutex Algorithm
指導教授: 葉耀明
學位類別: 碩士
Master
系所名稱: 資訊教育研究所
Graduate Institute of Information and Computer Education
畢業學年度: 87
語文別: 中文
論文頁數: 92
中文關鍵詞: 互斥問題分散式系統1-互斥K-互斥PMQ演算法Two_Token演算法
英文關鍵詞: Mutual exclusion, Distributed system, 1-Mutex problem, K-Mutex problem, PMQ Algorithm, Two_Token Algorithm
論文種類: 學術論文
相關次數: 點閱:137下載:0
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報
  • 在分散式系統中,多個節點共享各種網路資源,因此延伸出資源共享的互斥問題(mutual exclusion)。所謂互斥問題就是一個資源在同一個時間內只允許一個節點取用。若有一個共享資源,即為1-互斥問題(1-mutex),若K個共享資源,則為K-互斥問題(K-mutex)。互斥問題是一個非常重要的課題,許多分散式系統的操作包括資料複製、分散式共享記憶體等機制都需要解決資源共享的互斥問題。
    本論文提出了兩個解決互斥問題的演算法,第一個方法為PMQ演算法,是一種許可基礎演算法,以Coterie來降低解決互斥的通訊成本,並提供容錯能力。第二個方法為Two_Token演算法,是一種權杖基礎演算法,利用兩種權杖(一為A_Token,另一為C_Token)來提高容錯能力。這兩個演算法都可以解決1-互斥及K-互斥的問題,並能提供比現有演算法更佳的容錯能力。

    In the distributed system, network resources shared by many nodes results in the mutual exclusion problem of the shared resources. Mutual exclusion require that a resource can only be assignned to a node at a time. If the system has one shared source, it is called 1-mutex problem. When a system has k shared sources, it is called k-mutex problem. Mutual exclusion is crucial for the design of a distributed system. Many operations such as data replication and distributed memory sharing all require the mutual exclusion mechanism to solve the coordination of resource sharing.
    In this thesis, we devise two new distributed algorithms to achieve mutual exclusion. The first method is called PMQ algorithm. It is a permission-based algorithm, which not only reduces the communication cost using coterie, but also provides high fault-tolerant capability. The second method is called Two_Token algorithm. It is a Token-based algorithm, which uses two tokens (one is A_Token; the other is C_Token) to provide the fault tolerant capability. Both algorithms can solve 1-mutex and K-mutex problem, and provide better fault-tolerant capability than the existing algorithm.

    目 錄 附表目錄 iv 附圖目錄 v 第一章 緒論 1 1.1 研究背景 1 1.2 分散式系統的互斥問題 2 1.3 國內外相關研究情形 2 第二章 相關研究深入探討 5 2.1 Lamport’s演算法 5 2.2 Maekawa’s演算法 6 2.3 Agrawal 和Abbadi’s演算法 7 2.4 LeLann’s演算法 9 2.5 Suzuki和Kasami’s演算法 10 2.6 Raymond’s演算法 11 第三章 1-互斥問題 14 3.1 Pseudo Majority Quorum演算法(PMQ Algorithm) 14 3.1.1 基本定義 14 3.1.2 1-互斥PMQ演算法 18 3.1.3 PMQ演算法的通訊協定 20 3.2 Two_Token演算法 30 3.2.1 基本定義 30 3.2.2 1-互斥Two_Token演算法 36 第四章 分析和比較 40 4.1 傳輸成本 40 4.1.1 許可基礎演算法在傳輸成本上的考量 40 4.1.2 權杖基礎的演算法在傳輸成本上的考量 42 4.2 容錯能力 45 4.2.1 許可基礎演算法在容錯方面的考量 45 4.2.2 權杖基礎演算法在容錯方面的考量 48 第五章K-互斥問題 51 5.1有關k-互斥問題的相關研究深入探討 51 5.1.1 Raymond’s演算法 51 5.1.2 Kakugawa等多位學者所提出的演算法 53 5.1.3 Y. C. Kuo和S. T. Huang所提出的演算法 55 5.1.4利用幾何的圖形建構k-coterie 56 5.1.5利用Cohort結構來建構k-coterie 58 5.2 解決k-互斥問題的演算法 60 5.2.1 k-互斥PMQ演算法的基本定義 60 5.2.2 k-互斥PMQ演算法的表示法 63 5.3 K-互斥Two_Token演算法 65 5.3.1 K-互斥Two_Token演算法的基本定義 65 5.3.2 K-互斥Two_Token演算法 72 5.4效能評估 79 第六章 結論與未來發展 86 6.1結論 86 6.2未來發展方向 89 參考文獻 91

    【1】 L. Lamport, “Time Clocks and Ordering of Events in Distributed Systems,” Communications of the ACM, Vol. 21, No. 7, pp. 558-565, July 1978.
    【2】 G. Ricart and A. Agrawala, “An Optimal Algorithm for Mutual Exclusion in Computer Networks,” Communications of the ACM, Vol. 24, No. 1, pp. 9-17, January 1981.
    【3】 M. Maekawa, “A Algorithm for Mutual Exclusion in Decentralized Systems,” ACM Trans. On Computer Systems, Vol. 3, No. 2, pp. 145-159, May 1985.
    【4】 D. Agrawal and A. E. Abbadi, “An Efficient and Fault-Tolerant Solution for Distributed Mutual Exclusion,” ACM Trans. Computer Systems, Vol. 9, No. 1, pp. 1-20, February 1991.
    【5】 G. LeLann, “Algorithms for Distributed Data Sharing Systems Which Use Tickets,” Proc. 3rd Berkeley Workshop Distributed Data Management and Computer Networks, pp. 259-272, 1978.
    【6】 I. Suzuki and T. Kasami, “A Distributed Mutual Exclusion Algorithm,” ACM Trans. Computer Systems, Vol. 3, No. 4, pp. 344-349, November 1985.
    【7】 K. Raymond, “A Tree Based Algorithm for Distributed Mutual Exclusion,” ACM Trans. On Computer Systems, Vol. 7, No. 1, pp. 61-77, February 1989.
    【8】 A. Kumar, “Hierarchical Quorum Consensus: A New Algorithm for Managing Replicated Data,” IEEE Trans. Computers, Vol. 40, No. 9, pp. 996-1004, September 1991.
    【9】 R. H. Thomas, “A Majority Consensus Approach to Concurrency Control for Multiple Copy Databases,” ACM Trans. Database Systems, Vol. 4, No. 2, pp. 180-209, June 1979.
    【10】 M. Stumm and S. Zhou, “Algorithms Implementing Distributed Shared Memory,” Computer, Vol. 23, No. 5, pp. 54-64, May 1990.
    【11】 H. Garcia-Molina and D. Barbara, “How to Assign Votes in a Distributed System,” J. ACM., Vol. 32, No. 4, pp. 841-860, Oct. 1985.
    【12】 K. Makki, “An Efficient Token-based Distributed Mutual Exclusion Algorithm,” Journal of Computer and Software Engineering, December 1994.
    【13】 W. Jia, J. Kaiser and E. Nett, “RMP: Fault-Tolerant Group Communication,” IEEE Micro, Vol. 10. No. 2, PP 59-67, April 1996.
    【14】 K. Raymond, “A Distributed Algorithm For Multiple Entries to a Critical Section,” Information Processing Letters, Vol. 30, pp. 189-193, February 1989.
    【15】 H. Kakugawa, S. Fujita, M. Yamashita, and T. Ae, “Availability of k-Coterie,” IEEE Trans. Comput. Systems, Vol. 42, No. 5, pp553-558, May 1993.
    【16】 S.M. Yuan and H.K. Chang, “Comments on”Availability of k-Coterie”,” IEEE Transactions on Computers, Vol. 43, No. 12, pp. 1457, December 1994.
    【17】 Y.C. Kuo and S.T. Huang, “A Simple Scheme to Construct k-Coterie with O( ) Uniform Quorum Sizes,” Information Processing Letters, Vol. 59, pp. 31-36, 1996.
    【18】 Y.C Kuo and S.T. Huang, “A Geometric Approach for Construction Coteries and k-Coteries,” IEEE Transactionw on Parallel and Distributed Systems, Vol. 8, No. 4, pp. 402-411, April 1997.
    【19】 J.R. Jiang, S.T. Huang and Y.C. Kuo, ”Cohorts Structrues for Fault-Tolerant k Entries to a Critical Section,” IEEE Transactions on Computers, Vol. 46, No. 2, pp. 222-228, February 1997.
    【20】 H. Kakugawa. S. Fujita, M. Yamashita and T. Ae, “A Distributed k-Mutual Exclusion Algorithm Using k-Coterie,” Information Processing Letters, Vol. 49, pp. 213-218, 1994.
    【21】 P.K. Srimani and R.L. Reddy, “Another Distributed Algorithm for Multiple entries to a Critical Section,” Information Processing Letters, Vol. 41, pp. 51-57, January 1991.

    無法下載圖示
    QR CODE