Delay-optimal quorum-based mutual exclusion scheme with fault-tolerance capability Conference

Cao, G, Singhal, M, Deng, Y et al. (1998). Delay-optimal quorum-based mutual exclusion scheme with fault-tolerance capability . 444-451.

cited authors

  • Cao, G; Singhal, M; Deng, Y; Rishe, N; Sun, W



  • 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 tradeoff in mutual exclusion algorithms. Lamport's algorithm and Ricart-Agrawal algorithm both have a synchronization delay of T, but their message complexity is O(N). Maekawa's algorithm reduces message complexity to O(√N); however, it increases the synchronization delay to 2T. After Maekawa's algorithm, many quorum-based mutual exclusion algorithms have been proposed to reduce message complexity or increase the resiliency to site and communication link failures. Since these algorithms are Maekawa-type algorithms, they also suffer from long synchronization delay 2T. In this paper, we propose a delay-optimal quorum-based mutual exclusion algorithm which reduces the synchronization delay to T 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.

publication date

  • January 1, 1998

start page

  • 444

end page

  • 451