Luggage locks

The Ricart-Agrawala Algorithm is an algorithm for mutual exclusion on a distributed system. This algorithm is an extension and optimization of Lamport’s Distributed Mutual Exclusion Algorithm, by removing the need for <math>release</math> messages.

Algorithm

Terminology

• A site is any computing device which is running the Ricart-Agrawala Algorithm
• For any one request of the critical section:
  • The requesting site is the site which is requesting entry into the critical section.
  • The receiving site is every other site which is receiving the request from the requesting site.
• 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>request(ts, i)</math> to all sites.

Receiving Site:

• Upon reception of a <math>request(ts, i)</math> message, the receiving site <math>P_j</math> will immediately send a timestamped <math>reply(ts, j)</math> message if and only if:
  • <math>P_j</math> is not requesting or executing the critical section OR
  • <math>P_j</math> is requesting the critical section but sent a request with a higher timestamp than the timestamp of <math>P_i</math>
• Otherwise, <math>P_j</math> will defer the <math>reply</math> message.

Critical Section:

• Site <math>P_i</math> enters its critical section only after receiving all <math>reply</math> messages.
• Upon exiting the critical section, <math>P_i</math> sends all deferred <math>reply</math> messages.

Performance

• Number of network messages; 2*(N-1)
• Synchronization Delays: One message propagation delay

Common Optimizations

Once site <math>P_i</math> has received a <math>reply</math> message from site <math>P_j</math>, site <math>P_i</math> may enter the critical section without receiving permission from <math>P_j</math> until <math>P_i</math> has sent a <math>reply</math> message to <math>P_j</math>

Problems

One of the problems in this algorithm is failure of a node. In such a situation a process may starve forever.
This problem can be solved by detecting failure of nodes after some timeout.

See also

• Lamport’s Bakery Algorithm
• Lamport’s Distributed Mutual Exclusion Algorithm
• Maekawa’s Algorithm
• Suzuki-Kasami’s Algorithm
• Raymond’s Algorithm

• Tags: algorithm, luggage locks, Uncategorized //