Mutual Exclusion: Difference between revisions

Revision as of 14:04, 15 February 2023

Mutual exclusion is a property of concurrency control; which is instituted for the purpose of preventing race conditions.

n: number of processors?

Name	Year	Time	Space	Approximation Factor	Model	Reference
Lamport's bakery algorithm	1974	$O(n)$	$O({1})$ per process, $O(n)$ total?	Exact	Deterministic	Time & Space
Szymanski's algorithm	1988	$O(n)$	$O({1})$ per process, $O(n)$ total?	Exact	Deterministic	Time & Space
Taubenfeld's black-white bakery algorithm	2004	$O(n)$	$O({1})$ per process, $O(n)$ total?	Exact	Deterministic	Time & Space
Maekawa's algorithm	1985	$O(n^{0.5})$	$O({1})$ per process, $O(n)$ total?	Exact	Deterministic	Time & Space
Raymond's algorithm	1997	$O(logn)$? (originally this had $O(n)$)	$O({1})$ per process, $O(n)$ total?	Exact	Deterministic	Space
Suzuki-Kasami's algorithm	1985	$O(n)$? (originally this had $O(logn)$)	$O({1})$ per process, $O(n)$ total?	Exact	Deterministic	Time & Space
Dekker's algorithm	1963	$O(n)$		Exact	Deterministic
Peterson's algorithm	1981	$O(n)$	$O(n)$ total	Exact	Deterministic	Time
Naimi-Trehel's algorithm	1996	$O(logn)$	$O({1})$ per process, $O(n)$ total?	Exact	Deterministic	Time
Chan-Singhal-Liu	1990	$O(logn)$	$O({1})$ per process, $O(n)$ total?	Exact	Deterministic	Time

@@ Line 27: / Line 27: @@
 |-
 | [[Suzuki-Kasami's algorithm ( Mutual Exclusion)|Suzuki-Kasami's algorithm]] || 1985 || $O(n)$? (originally this had $O(logn)$) || $O({1})$ per process, $O(n)$ total? || Exact || Deterministic || [https://cse.iitkgp.ac.in/~agupta/distsys/Mutex-SuzukiKasami.pdf Time] & [https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.135.825&rep=rep1&type=pdf Space]
+|-
+| [[Dekker's algorithm (2-thread Mutual Exclusion Mutual Exclusion)|Dekker's algorithm]] || 1963 || $O(n)$ ||  || Exact || Deterministic ||
 |-
 | [[Peterson's algorithm ( Mutual Exclusion)|Peterson's algorithm]] || 1981 || $O(n)$ || $O(n)$ total || Exact || Deterministic || [https://zoo.cs.yale.edu/classes/cs323/doc/Peterson.pdf Time]
@@ Line 36: / Line 38: @@
 |}
-== Time Complexity graph ==
+== Time Complexity Graph ==
 [[File:Mutual Exclusion - Time.png|1000px]]
-== Space Complexity graph ==
+== Space Complexity Graph ==
 [[File:Mutual Exclusion - Space.png|1000px]]
-== Pareto Decades graph ==
+== Pareto Frontier Improvements Graph ==
 [[File:Mutual Exclusion - Pareto Frontier.png|1000px]]