Maekawa's algorithm: Difference between revisions

Revision as of 15:17, 21 February 2009

Revision as of 15:18, 21 February 2009

Line 11:

=== 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>.

'''Receiving Sitesite''':

* Upon reception of a <math>request(ts, i)</math> message, the receiving site <math>P_j</math> will:

** If site <math>P_j</math> does not have an outstanding <math>grant</math> message (that is, a <math>grant</math> message that has not been released), then site <math>P_j</math> sends a <math>grant(j)</math> message to site <math>P_i</math>.

Line 27:

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

'''Critical Sectionsection''':

* Site <math>P_i</math> enters the critical section on receiving 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 Setset (<math>R_x</math>)''':<br />

A quorum set must abide by the following properties:

# <math>\forall i \forall j [R_i \bigcap R_j \ne \empty ]</math>