Maekawa's algorithm: Difference between revisions

Revision as of 15:58, 28 February 2006

Revision as of 10:39, 7 March 2006

Line 2:

== Algorithm ==

=== Terminology ===

* A ''site'' is any computing device which is running the Ricart-Agrawala Algorithm

Line 13 ⟶ 12:

'''Requesting Site''':

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

'''Receiving Site''':

Line 28 ⟶ 26:

** Delete <math>P_i</math> from its request queue.

** Send a <math>grant(j)</math> message to the request on the top of its request queue.

'''Critical Section''':

* Site <math>P_i</math> enters the critical section on reciving a <math>grant</math> message from all sites in <math>R_i</math>.

* Upon exiting the critical section, <math>P_i</math> sends a <math>release(i)</math> message to all sites in <math>R_i</math>.

'''Quorum Set (<math>R_x</math>)''':<br />

Line 41 ⟶ 37:

# <math>\forall i [ |R_i| = K ]</math>

# Site <math>P_i</math> is contained in exactly <math>K</math> request sets

:Therefore:

:* <math>|R_i| = \sqrt{N}</math>

=== Performance ===

Line 51 ⟶ 45:

* Synchronization delay: Two message propagation delay

== See Alsoalso ==

* [[Lamport's bakery algorithm]]

* [[Lamport's distributed mutual exclusion algorithm]]