Ricart–Agrawala algorithm

The Ricart - Agrawala algorithm comes in a distributed system to regulate the application for access to a critical section and to guarantee mutual exclusion. In this case, the algorithm is based on the exchange of messages and dialing numbers by the nodes of a computer network. He was released from Glen Ricart and Ashok K. Agrawala in 1981.

If a host wants to enter a critical section in a network, this a request message must be connected to all the other computers on the network send a self-selected number. Compare all nodes then their number dialed with the received. The computer with the smallest number dialed is allowed to enter the critical section. If a computer is in possession of a higher number, he must inform the computers with smaller number dialed to defer and sends a response. Otherwise, the answer and the computer with the larger number is omitted is to be added to a list notified later to the purpose. If a host response messages received from all other machines on a network, it can enter the critical area as desired.

Algorithm

The algorithm runs on any computer in the network is divided into two parallel running processes. The one main process is to be allowed to enter the critical section for the request for granting the authorization, responsible and steps into the end section. A second process receives the response messages from the other computer.

In the main process, a number is first selected. This is communicated to all the other computers in a request message and then wait for the arrival of the reply messages. Are all response messages arrived, the critical section is entered.

But the other computers in the network may have the interest to enter the critical section and also send a request message with their number. In parallel, a second process is executed from any computer. This constantly receives the request messages of the other computer and compares the numbers. Is when comparing own dialed number greater than that of the other computer, this computer will be immediately sent a reply message so that it can enter the critical section. If the own number, however, the smaller, the computer in a " delay list " is noted.

If a computer could enter the critical section, it sends after leaving the section within the main process response messages to all processes that are noted in the " delay list ".

Message complexity

In a network with nodes fall for each node that wants to enter the critical section of news: There will be shipped request messages and also receive response messages. Hence arise messages when each of the nodes will enter the critical section. For the worst case that all processes want to enter the critical section, the message complexity of the algorithm can therefore be expressed as using the Landau symbols. By the quadratic News expense of the algorithm is inefficient in larger networks.

Example

Suppose there exist three computers A, B and C. Each randomly chooses a number:

• A: 3
• B: 7
• C: 9

After the election, all send each other the numbers in messages to. For example, A sends 3 to B and C. The other act accordingly. Since A has chosen the smallest number of the other two adds to its " delay list ". At the same time he receives from B and C response messages and can enter the critical section. B receives a reply message from C, because B's value is less than that of C. Also, B adds the computer C to its " delay list ". Since B has, however, a larger number is selected as A, it sends a response message to a. If A has left the critical section, A sends to all the computers in his " delay list" response message. The computer C with the largest number can only send the reply messages to A and B, and then have to wait until it receives the response messages from A and B, after they have each left the critical section.