Classification of Mutual Exclusion Algorithm in Distributed System: Distributed System

This lecture is dedicated to students and learners those are eager to know the concept of Mutual Exclusion in Distributed system.
by seeing this lecture you will be able to understand the concept of Mutual Exclusion classification. what is it and its significance.

classification :
permission based : centralized algo., decentralized , distributed, token ring algo.
token based

Token based Solution :
Pass a special message to all other process known as “Token”.
Only one token is available.
Who ever has that token is allowed to access the shared resource.
Draw Back :
If token is lost (it will take time to create new token ).

Permission Based solution:
1. Centralized algorithm :
One process is elected as a coordinator and it will grant or reject to access the resources.
single processor system.
If another process claimed resource:
Maintain queue
Service requests in FIFO order
Benefits :
Fair
All requests processed in order
Easy to implement, understand, verify.
Draw Back : if coordinator failed / crashed , system will be stopped.

2.De-Centralized algorithm :
It is solution of Centralized algorithm.
To access the shared resource , process will require the majority to vote coordinator.
All process will give their concern / respond to access resource.
Winning / recommended process will access resource firstly.

3. Distributed Algo (Ricart & Agrawala algorithm) :
There should be total ordering of all events in the system.
To access Resource , process will create a message that contain:
identifier (machine ID, process ID)
Name of resource
Timestamp (totally-ordered Lamport)/ Current Time.
Send request to all processes in the group including itself.
Wait until response of all process /everyone gives permission.
The Process will have lowest time will be allowed to access critical section / shared resource.

working :
When process receives request:
If receiver not interested:
Send OK to sender
If receiver is in critical section
Do not reply; add request to queue
If receiver just sent a request as well:
Compare timestamps: received & sent messages
Earliest wins
If receiver is loser, send OK
If receiver is winner, do not reply, queue
When done with critical section
Send OK to all queued requests

4. Token Ring algorithm :
“ Whenever a process want to access a Resource , it request for TOKEN(appointment) from server. “

Server maintain queue of request & execute each request in FIFO manner.
Construct logical ring in software
Process communicates with neighbor

Token Ring algorithm working flow :
Initialization
Process gets token for resource (R).
Only one process will have token at a time.
Mutual exclusion guaranteed
If token is lost (e.g. process died)
It will have to be regenerated
Token circulates around ring
From Pi to P(i+1)mod N
When process acquires token
Checks to see ‘if it needs to utilize the resource / enter critical section’
If no, send token to neighbor
If yes, access resource(R)
Hold token until done and release token after finish.

for more videos subscribe the channel and press the bell icon so that you will get notification of new video.