Coordination and Agreement

Coordination and Agreement

Mutual Exclusion in DS

- Mutual exclusion is a mechanism that prevent interference and ensure consistency when accessing the resources by a collection of processes.
- In distributed system, shared variables i.e. semaphores and local kernel can not be used to implement mutual exclusion. Because of this, distributed mutual exclusion arises which is based only on message passing.
- The basic requirements for mutual exclusion mechanism are:
1. At most one process may execute in the critical section at a time.
2. A process is granted entry to critical section if no any other process is executing within critical section.

Mutual Exclusion Algorithms

Non- Token Based Algorithm

- Each process competes for gaining access to use the shared resources.
- Requests are arbitrated by central control site or by distributed agreement.
- It includes central coordinator algorithm and Ricart-Agrawala algorithm.

Central Coordinator Algorithm

- A central coordinator is present within the distributed system which is responsible to grant access to enter a critical section.
- The coordinator makes a request queue to handle multiple requests.

Algorithm:
1. A process sends a request message to coordinator to enter critical section and continues its other work while waiting for a reply.
2. The reply from coordinator gives right to access critical section which is based on request queue.
3. After finishing critical section operation, the process notifies coordinator with a release message.

Advantages:
1. It is easy to implement.
2. It requires only three messages per access of critical section.

Disadvantages:
1. The performance of the system may degrade.
2. If a coordinator crashes, a new coordinator must be created using election algorithm.

Ricart-Agrawala Algorithm

- It makes use of distributed agreement to implement mutual exclusion.
- All the processes are assumed to keep Lamport's logical clock.
- The process requiring access to critical section multicast request message to all other process competing for same resource.
- A process enters critical section when all processes reply to the message.
- Each process keeps its state with respect to critical section as released, requested or held.

Algorithm:

1. Rule for initialization (performed by each process Pi)
         StatePi := RELEASED
2. Rule for access request to CS
       StatePi := REQUESTED
       TPi := Value of local logical clock
       Pi sends request message of form ( TPi, i) to all processes
       Pi waits until it receives replies from all other n-1 processes
3. Rule for executing the CS
      statePi := HELD
4. Rule for handling incoming requests
       if statePi = HELD or [(statePi = REQUESTED) and {(TPi, i) < (TPj, j)}] then:
                   queue request from Pj without replying
       else
                reply immediately to Pj
       end if
5. Rule for releasing CS
       statePi :=RELEASED
       Pi replies to all queued requests.

Problems
1. It is expensive to handle message traffic [2(n-1) messages]
2. Failure of one involved process blocks the progress.

Token Based Algorithm

- A logical token is passed among the processes.
- A token represents access right to the shared resources.
- The process which holds the token is granted access to critical section.
- It includes Ricart-Agrawala second algorithm and token ring algorithm.

Ricart-Agrawala second Algorithm

- A process can access critical section if it has token.
- To get token, it sends request to all other processes with logical clock and its identifier.
- When Pi leaves critical section, it passes token to the one of the waiting process based on request queue. If no process is in queue, Pi retains the token.
- Each process Pi records time stamp corresponding to last request from Pj in Pi[j] and token records timestamp of Pj's last holding of token. If request Pi[j] > token[j]; Pj has pending request.

Algorithm:

1. Rule for process initialization
         statePi := NO-TOKEN for all processes Pi except one process Px for which statePx := TOKEN-PRESENT

token[k] initialized to 0 for all k = 1 to n
request Pi [k] initialized to 0 for all Pi and k = 1 to n

2. Rule for access request and execution of CS
if statePi = NO-TOKEN then
Pi sends request message to all processes in the form (TPi, i)
Pi waits until it receives token
end if
statePi := TOKEN-HELD
Pi enters CS

3. Rule for handling incoming requests
requestPi[j] := max (requestPi[j], TPi)
if statePi = TOKEN- PRESENT then
Pi releases the resource
end if

4. Rule for releasing CS
statePi := TOKEN-PRESENT
for k = [i+1, i+2, ..........., n, 1, 2, .............., i-2, i-1] do
if requestPi[k] > token[k] then
statePi := NO-TOKEN
token[i] := CPi
Pi sends token to Pk
break
end if
end for

Advantages:
1. It requires only n-1 requests and one reply.
2. Failure of process which is not holding token does not prevent progress.

State Diagram:
The state diagram is shown in given figure:

Token Ring Algorithm

- The n processes are arranged in a logical ring as shown in given figure:

Algorithm:
1. Token is initially given to one process.
2. When a process requires to enter CS, it waits until it gets token from its left neighbor and retains it. After it left CS, it passes token to its neighbor in clockwise direction.
3. If a process gets token but does not require to enter CS, it immediately passes token along the ring.

Problem:
1. It adds load to the network as token should be passed even the process do not need it.
2. If one process fails, no progress is possible until the faulty process is extracted from the ring.
3. Election process should be done if the process holding the token fails.

Distributed Election

- Election algorithm is an algorithm for choosing a unique process to play a particular role.
- Any process can be elected but only one process must be elected and all other processes must agree on it.
- Election started after a failure of current coordinator.
- Election process has two phases:
1. Selection of new leader
2. Information to all processes about the elected process

Bully Algorithm

- Any process can crash during the election.
- It assumes that the system is synchronous.
- It assumes that each process knows identifiers of other processes and it can communicate with process with higher identifier.
- It has three types of messages : election message, answer message and coordinator message.

- When a process Pi detects a failure and election is to be held, it sends election message to all processes with higher identifier and waits for the answer message.
1. If no answer arrives within a time limit, Pi becomes coordinator and sends coordinator message to all other processes.
2. If answer message arrives, Pi knows another process has to be a coordinator and waits for coordinator message. If coordinator message fails to arrive within a time limit, Pi resends the election message.

1. Rule for election process initiator
         statePi := ELECTION-ON
         Pi sends election message to processes with higher identifier
         Pi waits for answer message
         if no answer message before timeout then
                Pi is coordinator and sends coordinator message to all processes
         else
                Pi waits for coordinator message
                if no coordinator message arrives before timeout then
                           restart election procedure
                end if
         end if

Best Case Scenario:
- The process with second highest identifier notices coordinator's failure, it then selects itself as coordinator and sends (n-2) coordinator messages.

Worst Case Scenario:
- The process with lowest identifier indicates election. It sends (n-1) election messages to processes which themselves initiate an election. So, O(n2) messages are required.

Ring Based Algorithm

- The processes are arranged in a logical ring.
- Each process knows address of one other neighbor process in the clockwise direction.
- It assumes no any failures during election.
- It assumes that the system is asynchronous.
- By default, the state of a process is NON-PARTICIPANT

Algorithm:

1. Rule for election process initiator
           statePi := PARTICIPANT
           Pi sends election message with message.id := i to its neighbor