Mutual exclusion is a fundamental problem in distributed systems, where multiple processes need to access shared resources without interfering with each other. In this article, you will learn how to implement mutual exclusion in distributed systems using different algorithms and techniques.
Lamport's algorithm is a widely used mutual exclusion algorithm for distributed systems, created by Leslie Lamport. This algorithm is based on the concept of logical clocks, which are counters that each process maintains and increases whenever it sends or receives a message. To enter a critical section, a process sends a request message to all other processes containing its current logical clock value and the resource identifier. When a process receives a request message, it sends an acknowledgement message and updates its logical clock to the maximum of its own and the sender's values. The process with the smallest logical clock value has the highest priority to enter the critical section. If there is a tie, the process with the smallest identifier has the highest priority. Upon exiting the critical section, a release message is sent to all other processes containing its current logical clock value and the resource identifier.
Centralized Approach: One node acts as a coordinator. Processes request permission from this node to enter the critical section. The coordinator grants permission based on some policy, like FIFO. Distributed Approach: Processes communicate directly with each other to reach a consensus. Lamport's Timestamp Algorithm is commonly used here. Token Ring: A token circulates in the system. A process can enter the critical section only when it holds the token. After exiting, it passes the token to the next process in the ring. Two-Phase Commit: Used in transactional systems, it ensures that all nodes either commit or abort a transaction, maintaining consistency.
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.
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.
Note that there is also third way to implement mutual exclusion in distributed systems – quorum-based algorithms. A good simple example is Maekawa’s algorithm. This algorithm allows to enter critical section with permissions obrainted from subset of processes But this algorithm can lead to deadlocks, so it is not the best option in practice