loading...
A Dynamic Group Mutual Exclusion Algorithm Using Surrogate-Quorums
Columbus, Ohio, USA June 06-June 10
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ICDCS.2005.525th IEEE International Conference on ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Ranganath Atreya, Amazon.com, Inc.
Neeraj Mittal, University of Texas at Dallas
The group mutual exclusion problem extends the traditional mutual exclusion problem by associating a type with each critical section. In this problem, processes requesting critical sections of the same type can execute their critical sections concurrently. However, processes requesting critical sections of different types must execute their critical sections in a mutually exclusive manner. In this paper, we provide a distributed algorithm for solving the group mutual exclusion problem based on the notion of surrogatequorum. Intuitively, our algorithm uses the quorum that has been successfully locked by a request as a surrogate to service other compatible requests for the same type of critical section. Unlike the existing quorum-based algorithms for group mutual exclusion, our algorithm achieves a low message complexity of O(q), where q is the maximum size of a quorum, while maintaining both synchronization delay and waiting time at two message hops. Moreover, like the existing quorum-based algorithms, our algorithm has high maximum concurrency of n, where n is the number of processes in the system. The existing quorum-based algorithms assume that the number of groups is static and does not change during runtime. However, our algorithm can adapt without performance penalties to dynamic changes in the number of groups. Simulation results indicate that our algorithm outperforms the existing quorum-based algorithms for group mutual exclusion by as much as 50% in some cases.
Citation:
Ranganath Atreya, Neeraj Mittal, "A Dynamic Group Mutual Exclusion Algorithm Using Surrogate-Quorums," icdcs, pp.251-260, 25th IEEE International Conference on Distributed Computing Systems (ICDCS'05), 2005
Usage of this product signifies your acceptance of the Terms of Use.