Distributed Locking Algorithms (Distributed Locking Algorithms)

From Algorithm Wiki
Jump to navigation Jump to search


The purpose of a lock is to ensure that among several nodes that might try to do the same piece of work, only one actually does it (at least only one at a time). That work might be to write some data to a shared storage system, to perform some computation, to call some external API, or suchlike. At a high level, there are two reasons why you might want a lock in a distributed application: for efficiency or for correctness.


$n$: number of clients

$f$: number of files

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Leases (Cary G Gray and David R Cheriton) 1989 $O(n)$ $O(f)$? Exact Deterministic Time
Chubby (Mike Burrows) 2006 $O(n)$ $O(f)$? Exact Deterministic Time
Tushar Deepak Chandra and Sam Toueg 1996 $O(n)$ Exact Deterministic Time

Time Complexity Graph

Distributed Locking Algorithms - Time.png