Algorithm Description

The algorithm of Ricart and Agrawala resolves conflicts between processes by sending messages with time stamps. For this purpose a process which changes its state to hungry sends messages, called request, to all its neighbours. A request message includes information about the unique identifier of the sender and a time stamp. The time stamp is the local clock of the sending process when the message was created. It is increased when a request message is sent or received. Before sending a set of request messages the local clock is increased by one, while on the receiving of request the local clock will be set to

$$\mbox{\em new value}:=\max(\mbox{\em old value}, \mbox{\em received value})+1.$$

The time tuple $(\mbox{\em local clock}, \mbox{\em unique identifier})$ gives a lexical order of events. Although in real time the events might occur in a different order than the received lexical order of events, it still results in an equivalent execution. Hence, on the receiving of a request message a process which is competing with another process for a resource can distinguish whether receiver or sender were requesting first for a resource assuming the lexical order of events.

Therefore, a process p that receives a request message from process q does the following depending on its state:

• If p is thinking, then it sends a fork message to q. Sending a fork message symbolizes that a process gives access to a resource and guarantees not to access the resource until it has itself received a fork message.
• If p is hungry, then it is competing with q for the same resource. This means that p sent a request message to q before, so p compares, by using the lexical order of events, which process sent its message the earliest. If p has sent its message later then it replies by sending a fork message. Otherwise, it delays the sending of a fork message until it has finished with accessing its critical section.
• If p is eating it also delays sending the fork message until it has finished with its critical section.

A process may access its critical section, when it received a fork message from all its neighbours. When it has finished it sends to all neighbours which requested access to a resource, fork messages and changes its state to thinking.

11/16/1999