Maekawa's algorithm: Difference between revisions

Revision as of 23:38, 31 August 2009

Revision as of 17:41, 16 December 2009

Line 1:

{{Unreferenced|date=December 2009}}

{{Orphan|date=December 2009}}

'''Maekawa's algorithm''' is an algorithm for [[mutual exclusion]] on a [[distributed system]]. The basis of this algorithm is a quorum like approach where any one site needs only to seek permissions from a subset of other sites.

== Algorithm ==

=== Terminology ===

* A ''site'' is any computing device which is running the Maekawa's Algorithm

Line 9 ⟶ 12:

* ''ts'' refers to the local timestamp of the system according to its [[logical clock]].

=== Algorithm ===

'''Requesting site''':

* A requesting site <math>P_i</math> sends a message <math>\text{request}(ts, i)</math> to all sites in its quorum set <math>R_i</math>.

Line 41 ⟶ 44:

:* <math>|R_i| \geq \sqrt{N-1}</math>

=== Performance ===

* Number of network messages; <math>3 \sqrt{N}</math> to <math>6 \sqrt{N}</math>

* Synchronization delay: 2 message propagation delays

== See also ==

* [[Lamport's bakery algorithm]]

* [[Lamport's Distributed Mutual Exclusion Algorithm]]

Line 51 ⟶ 54:

* [[Raymond's algorithm]]

{{DEFAULTSORT:Maekawa's Algorithm}}

[[Category:Concurrency control algorithms]]

[[Category:Articles lacking sources (Erik9bot)]]

[[de:Maekawa-Algorithmus]]