DocumentCode :
1860307
Title :
A delay-optimal quorum-based mutual exclusion scheme with fault-tolerance capability
Author :
Cao, Guohong ; Singhal, Mukesh ; Deng, Yi ; Rishe, Naphtali ; Sun, Wei
Author_Institution :
Dept. of Comput. & Inf. Sci., Ohio State Univ., Columbus, OH, USA
fYear :
1998
fDate :
26-29 May 1998
Firstpage :
444
Lastpage :
451
Abstract :
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. Lamport´s (1978) algorithm and Ricart and Agrawal´s (1981) algorithm both have a synchronization delay of T, but their message complexity is O(N). Maekawa´s (1985) 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. 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
Keywords :
communication complexity; concurrency control; delays; distributed algorithms; fault tolerant computing; resource allocation; synchronisation; algorithm performance; communication link failures; correctness proof; delay optimal scheme; fault tolerance; message complexity; message exchange; quorum based mutual exclusion scheme; synchronization delay; Computer science; Costs; Delay effects; Fault tolerance; Fault tolerant systems; Information science; Merging; Performance analysis; Sun; Synchronization;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Distributed Computing Systems, 1998. Proceedings. 18th International Conference on
Conference_Location :
Amsterdam
ISSN :
1063-6927
Print_ISBN :
0-8186-8292-2
Type :
conf
DOI :
10.1109/ICDCS.1998.679773
Filename :
679773
Link To Document :
بازگشت