Chandy–Misra–Haas algorithm resource model

K. Mani Chandy, Jayadev Misra and Laura M Haas devised the Chandy-Misra-Haas algorithm for Resource Model. It checks whether there is any deadlock in a distributed system or not.

Locally Dependent

Locally Dependent

Consider there are n process P₁,P₂,P₃,P₄,P₅............,P_n which are being performed in a single system(controller). P₁ is locally dependent on P_n, if P₁ depends on P₂,P₂ on P₃ so on till P_n-1 on P_n. P₁ is said to be locally dependent to itself if it is locally dependent on P_n and P_n depends on P₁.

Description

The Algorithm uses a message called probe(i,j,k) to transfer a message from controller of process P_j to controller of process P_k. It specifies message was started by process P_i to find whether a deadlock has occurred or not. Every process P_j maintains a boolean array dependent_j which contains the information about the process which are depending on it. Initially the value of each array is "false".

Controller sending a probe

The algorithm works like this: before sending the probe the controller checks whether P_j is locally dependent to itself or not. If it is locally dependent to itself then a deadlock has occurred.If it is not dependent to itself then it checks whether P_j,P_k are in different controllers, locally dependent and P_j is waiting for the resource that is locked by P_k. Once all the conditions are satisfied it sends the probe.

Controller receiving a probe

In the receiving side, the controller checks whether P_k is performing any task or not. If it is not idle, then it neglects the probe. Otherwise, it checks the responses given P_k to P_j and dependent_k(i) is false. Once it verifies then it assign true to dependent_k(i). After going through all those steps, in the end it checks whether k is equal to i. If both are equal then a deadlock has been occurred or else it sends probe to next dependent process.

Algorithm

Controller sending a probe

if Pj is locally dependent on itself
     then declare deadlock
else for all Pj,Pk  such that
     (i) Pi is locally dependent on Pj,
     (ii) Pj is waiting for 'Pk and
     (iii) Pj, Pk are on different controllers.
send probe(i, j, k).

Controller receiving a probe

if
     (i)Pk is idle,
     (ii) dependentk(i) = false, and
     (iii)requests responded by Pk to Pj
then begin
     "dependents""k"(i) = true;
     if k == i
     then declare that Pi  is deadlocked
     else for all Pa,Pb  such that
            (i) Pk is locally dependent on Pa,
            (ii) Pa is waiting for 'Pb and
            (iii) Pa, Pb are on different controllers.
     send probe(i, a, b).
end

Example

occurrence of deadlock in distributed system

In the shown example, P₁ initiates the deadlock detection. C₁sends the probe saying P₂ depends on P₃. Once the message is received by C₂, it checks whether P₃ is idle. P₃ is idle because it is locally dependent on P₄ and updates dependent₃(2) to True.

Same as above, C₂ sends probe to C₃ and C₃ sends probe to C₁. At C₁ P₁ is idle so it update dependent₁(1) to true. Therefore it can be declared a deadlock has occurred.

Complexity

Consider that there are "m" controllers and "p" process to perform, to declare whether a deadlock has occurred or not, it need to visit in worst case all controllers and process. Therefore, it takes O(m+p) to detect a deadlock. It can be said the time complexity is O(n).