在分散式系統中，多個節點共享各種網路資源，因此延伸出資源共享的互斥問題(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.

【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.