An Efficient Coterie-Based Mutual Exclusion Scheme With Fault-tolerance Capability

The performance of a mutual exclusion algorithm is measured by the number of messages exchanged per critical section execution and the delay between successive executions of the critical section. There is a message complexity and synchronization delay trade-off in mutual exclusion algorithms. Maekawa's algorithm reduces message complexity to O( p N); however, it increases the synchronization delay to 2T . This paper presents an algorithm which reduces the synchronization delay to T (average message delay) and still has the low message complexity O(K) (K is the size of the quorum, which can be as low as log N ). A correctness proof and detailed performance analysis are provided. The paper identifies one possible deadlock in Maekawa's algorithm and proposes a fix for it. Key words: Coteries, mutual exclusion, fault-tolerance. This work is supported in part by NASA under grant No. NAGW-4080, and by the National Science Foundation (NSF) under Grant No. CDA-9313624. 1 Introduction I..