JISE


  [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21]


Journal of Information Science and Engineering, Vol. 26 No. 1, pp. 57-69


An Improved Quorum-Based Algorithm for Extended GME Problem in Distributed Systems


ABHISHEK SWAROOP* AND AWADHESH KUMAR SINGH+
*Department of Computer Science and Engineering 
G.P.M. College of Engineering 
Delhi, 110036 India 
E-mail: asa1971@gmail.com 
+Department of Computer Engineering 
National Institute of Technology 
Kurukshetra, Haryana, 136119 India


    The extended GME (group mutual exclusion) problem is a natural extension of the GME problem. In extended GME problem, processes are allowed to request more than one resource at a time, in order that the processes that can proceed by having access to any one of the requested resource can be allowed to do so. Manabe-Park suggested a quorum based solution for the extended GME problem. However, the worst case message complexity of the Manabe-Park algorithm is 9q, where q is the quorum size. Further, the synchronization delay of Manabe-Park algorithm is 4T, where T is the maximum message propagation delay. In the present paper, we propose a quorum based solution for the extended GME problem. The worst case message complexity of our algorithm is 7q and synchronization delay is 3T. Moreover, in the best case, the synchronization delay and message complexity come down to 2T and 3q respectively.


Keywords: concurrency, quorum, distributed systems, unnecessary blocking, group mutual exclusion

  Retrieve PDF document (JISE_201001_05.pdf)