How can you implement mutual exclusion in distributed systems?

2 Ricart-Agrawala algorithm

Ricart-Agrawala algorithm is an optimization of Lamport's algorithm for mutual exclusion in distributed systems. It reduces the number of messages exchanged by using the concept of deferred replies. When a process wants to enter a critical section, it sends a request message to all other processes with its current logical clock value and the resource identifier. Each process compares its request message with the sender's request message - if the sender has a higher priority, it replies with an acknowledgement message and updates its logical clock, and if the sender has a lower priority, it defers the reply until it exits the critical section or gives up the request. When a process receives acknowledgements from all other processes, it enters the critical section. Upon exiting the critical section, it sends a release message to all other processes with its current logical clock value and the resource identifier, as well as any deferred replies that were not acknowledged before.

3 Token-based algorithms

A different approach for mutual exclusion in distributed systems is to use token-based algorithms, which rely on a special message called a token that circulates among the processes. The process that holds the token has the exclusive right to enter the critical section. Token-based algorithms come in two varieties: ring-based and tree-based. Ring-based algorithms arrange the processes in a logical ring and the token is passed from one process to the next in a fixed order. The Suzuki-Kasami algorithm is an example of this, using a token with a vector of requests from each process and a queue of pending requests. Tree-based algorithms organize the processes in a logical tree and the token is passed from the root to the leaves and back. An example of this is the Raymond algorithm, which uses a token with the identity of the process that requested it last. When a process wants to enter the critical section, it sends a request message to its parent in the tree. If it receives the token, it enters the critical section and returns it to its parent with the identity of the next requester.