View source for Distributed Locking Algorithms

{{DISPLAYTITLE:Distributed Locking Algorithms (Distributed Locking Algorithms)}}
== Description == 

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.

== Parameters == 

$n$: number of clients

$f$: number of files

== Table of Algorithms == 

{| class="wikitable sortable"  style="text-align:center;" width="100%"

! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference

|-

| [[Leases (Cary G Gray and David R Cheriton) (Distributed Locking Algorithms Distributed Locking Algorithms)|Leases (Cary G Gray and David R Cheriton)]] || 1989 || $O(n)$ || $O(f)$? || Exact || Deterministic || [https://web.stanford.edu/class/cs240/readings/89-leases.pdf Time]
|-
| [[Chubby (Mike Burrows) (Distributed Locking Algorithms Distributed Locking Algorithms)|Chubby (Mike Burrows)]] || 2006 || $O(n)$ || $O(f)$? || Exact || Deterministic || [https://dl-acm-org.ezproxy.canberra.edu.au/doi/10.5555/1298455.1298487 Time]
|-
| [[Tushar Deepak Chandra and Sam Toueg (Distributed Locking Algorithms Distributed Locking Algorithms)|Tushar Deepak Chandra and Sam Toueg]] || 1996 || $O(n)$ ||  || Exact || Deterministic || [https://www.cs.utexas.edu/~lorenzo/corsi/cs380d/papers/p225-chandra.pdf Time]
|-
|}

== Time Complexity Graph == 

[[File:Distributed Locking Algorithms - Time.png|1000px]]