A HYBRID DISTRIBUTED MUTUAL EXCLUSION ALGORITHM

This paper presents a hybrid approach to distributed mutual exclusion in which two algorithms are combined such that one minimizes message t raffic and the other minimizes time delay. In a hybrid approach, sites are divided into groups, and two different algorithms are used to res olve local (intra-group) and global (inter-group) conflicts. In this p aper, we develop a hybrid distributed mutual exclusion algorithm which uses Singhal's dynamic information structure algorithm [15] as the lo cal algorithm to minimize time delay and Maekawa's algorithm [7] as th e global algorithm to minimize message traffic. Compared to Maekawa's algorithm which needs O(root N) messages, but two time units delay bet ween successive executions of the Critical Section (CS) (where N is th e number of sites in the system), the proposed hybrid algorithm can re duce message traffic by 52% and time delay by 29% at the same time.