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

摘要

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 AT, 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 Iq and synchronization delay is 3T. Moreover, in the best case, the synchronization delay and message complexity come down to 2T and 3q respectively.