臺灣博碩士論文加值系統

分散式系統之，無法利用一個集中之控制位單來進行互斥性資源之控制。法團系統(quorum system)可以有效的解決這個種類的問題。群體互斥性(group mutual exclusion)問題是傳統互斥性問題的延伸，其允許一個以上的程序去使用相同的資源，但是同時只允許一種資源被使用。本篇論文中，我們提出一個演算法，利用group k-arbiter法團系統，來解決於分散式系統上之群體k互斥(group mutual k-exclusion)問題，其可以允許至多k個不同的資源被同時使用。我們提出使用較小的輕量化法團(lightweight quorum)之方式來降低訊息複雜度(message complexity)。我們的演算法有下列優勢：(1)使用較小的輕量化法團，以降低訊息傳輸量。(2)程序可以在一個要求訊息中一次要求多個不同的資源，不需分成多次。(3)可以同時使用資源的程序數目不受限制。(4)不會因為單一節點故障而導致系統整個停止運作。

In the distributed system, there is no central unit to control mutual exclusive resources. Quorum system is a useful concept to deal with this kind of problem. Group mutual exclusion is an extension of mutual exclusion problems, which allows many process to use the same resource simultaneously, but only one resource can be accessed at the same time. We proposed an algorithm to solve group mutual k-exclusion problem by using group k-arbiters, which allows up to k different resources to be accessed at the same time. In this study, a new quorum concept called lightweight quorums is introduced to reduce the message complexity, thanks for small quorum size. The proposed algorithm has the following advantages: (1) Less message complexity by using small lightweight quorum. (2) It allows a process to request many resources in one request message. (3) The degree of concurrency is unbounded. (4) It is free from a single node failure to crash system.

誌謝 i
摘要 ii
Abstract iii
List of Tables v
1. Introduction 1
2. Related works 5
2.1 Group Mutual Exclusion 5
2.2 k-arbiter quorum system 8
3. Method 11
3.1 Group k-Arbiter 11
3.2 Proposed Algorithm 16
4. Correctness 31
6. Conclusion 41
7. References 43

[1]R. Atreya and N. Mittal, "A distributed group mutual exclusion algorithm using surrogate-quorums," Technical Report, The University of Texas at Dallas, 2003.
[2]J. Beauquier, S. Cantarell, A. K. Datta, and F. Petit "Group mutual exclusion in tree networks," Journal of Information Science and Engineering, Vol. 19, No. 3, pp. 415-432, 2003
[3]Jehn-Ruey Jiang, "A distributed group k-exclusion algorithm using k-write-read coterie," Proc. 2004 International Computer Symposium ICS’04,2004.
[4]Yuh-Jzer Joung, "Quorum-based algorithms for group mutual exclusion," IEEE Transactions on Parallel and Distributed Systems, Vol. 14, No. 5, pp. 463-476, 2003.
[5]Yuh-Jzer Joung, "Asynchronous group mutual exclusion, " Distributed Computing, Vol. 13, No. 4, pp. 189-206, 2000.
[6]Y.-C. Kuo, "A simple scheme to construct k-arbiters with uniform quorum sizes," Journal of the Chinese Institute of Engineers, Vol. 26, No. 5, pp. 709-714, 2003.
[7]Yoshifumi Manabea, Roberto Baldonib, Michel Raynalc, Shigemi Aoyagia, "k-Arbiter: A safe and general scheme for h-out of-k mutual exclusion," Theoretical Computer Science, Vol. 193, No. 1-2, pp. 97-112, 1998.
[8]Mie Toyomura, Sayaka Kamei, Hirotsugu Kakugawa, "A quorum-based distributed algorithm for group mutual exclusion," Proc. 4th International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT), pp. 742-746, Chengdu, Sichuan, China, Aug. 27-29, 2003
[9]K. Vidyasankar, "A simple group mutual l-exclusion algorithm," Information Processing Letters, Vol. 85, pp. 79-85, 2003.