Ricart-Agrawala algorithm

The Ricart-Agrawala algorithm is used in a distributed system to regulate access to a critical section and to guarantee mutual exclusion . The algorithm is based on the exchange of messages and the selection of numbers by the nodes of a computer network. It was published by Glen Ricart and Ashok K. Agrawala in 1981.

If a computer in a network wants to enter a critical section, it must send a request message with a number chosen by itself to all other computers in the network. All nodes then compare their dialed number with the received ones. The computer with the lowest number dialed is allowed to enter the critical section. If a computer is in possession of a higher number, it must give priority to the computers with the lower number dialed and sends a corresponding response. Otherwise there is no answer and the computer with the larger number is added to a list with the purpose of being notified later. If a computer has received reply messages from all other computers in a network, it can enter the critical area as desired.

algorithm

The algorithm that runs on every computer in the network is divided into two parallel processes. One main process is responsible for the request for permission to enter the critical section and then ultimately enters the section. A second process receives the reply messages from the other computers.

In the main process, a number is first dialed. This is transmitted to all other computers in a request message and then the response message is waited for. If all reply messages have arrived, the critical section is entered.

But the other computers in the network may also be interested in entering the critical section and also send a request message with their number. A second process is carried out in parallel by each computer. This constantly receives the request messages from the other computers and compares the numbers. If, during a comparison, your own number is larger than that of the other computer, a reply message is sent to this computer immediately so that it can enter the critical section. If, on the other hand, your own number is smaller, the computer is noted in a "delay list".

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

Message complexity

In a network with nodes, messages are generated for each node that wants to enter the critical section : Inquiry messages are sent and response messages are also received. As a result, messages arise when each of the nodes wants to enter the critical section. For the worst case that all processes want to enter the critical section, the message complexity of the algorithm can thus be expressed using the Landau symbols . Due to the quadratic message cost, the algorithm is inefficient in larger networks. ${\ displaystyle n}$ ${\ displaystyle 2 * (n-1)}$ ${\ displaystyle (n-1)}$ ${\ displaystyle (n-1)}$ ${\ displaystyle n * (2 * (n-1))}$ ${\ displaystyle n}$ ${\ displaystyle {\ mathcal {O}} (n ^ {2})}$

example

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

A: 3
B: 7
C: 9

After the election, everyone sends the numbers to each other in messages. For example, A sends 3 to B and C. The others do the same. Since A has chosen the lowest number, he adds the other two to his "delay list". At the same time he receives reply messages from B and C and can enter the critical section. B receives a reply message from C because B's value is smaller than C's. B also adds computer C to its "delay list". However, since B chose a larger number than A, it sends A a reply message. When A has left the critical section, A sends the reply message to all computers in its "delay list". The computer C with the largest number can only send the reply messages to A and B and then has to wait until it has received the reply messages from A and B after they have left the critical section.

literature

G. Ricart, AK Agrawala: An Optimal Algorithm for Mutual Exclusion in Computer Networks . Communications of the ACM, January 1981, Issue 24, Number 1, pp. 9-17
Mordechai Ben-Ari: Principles of Concurrent and Distributed Programming. 2nd Edition. 2006. P. 216 ff. ISBN 0-321-31283-X