Mutual Exclusion

Description

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

Parameters

$n$: number of processors

Table of Algorithms

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(\log n)$? (originally this had $O(n)$)	$O(1)$ per process, $O(n)$ total?	Exact	Deterministic	Time & 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(\log n)$	$O(1)$ per process, $O(n)$ total?	Exact	Deterministic	Time
Chan-Singhal-Liu	1990	$O(\log n)$	$O(1)$ per process, $O(n)$ total?	Exact	Deterministic	Time

Time Complexity Graph

Space Complexity Graph

Time-Space Tradeoff