Pathpushing algorithm in Distributed deadlock detection Here, the wait-for dependency, the information about the wait-for dependencies, is circulated, propagated in the form of a path, right? So, every site will inform the next site about the wait-for dependency, right? And also, the individual site maintains its own local wait-for graph, right? In that graph, there will be a special node called P_external (P_ex), an external node, right? Always, right? For example, if there are two processes,? Suppose, in a local site, P_i is requesting or waiting for P_j, and P_j, in turn, is waiting for another resource that is available in the external site. Then, we have to put a P_ex, right? So, this is how it works. Because this P_ex, this resource, is not available in the local site; it is somewhere else, no? That’s why the local wait-for graph will contain P_ex, right? Okay. So, there are two cases: 1. A local process is requesting an external resource. 2. P_ex is requesting P_j, meaning a process at an external site is requesting the local site’s resource, right? So, that’s the meaning of this notation and algorithm. Coming to the algorithm, if any local wait-for graph contains a cycle that doesn’t involve any P_ex node of Dina, then the deadlock detector, right? There is a local wait-for graph. I already mentioned there is a P_ex that exists in the matrix pattern. Suppose if a cycle exists, and if the external process node P_ex at S_i sends a message to S_j, then now what will happen is S_j, the receiving site, forms a WFG (wait-for graph) with new information to detect deadlock. This is what the simple algorithm does. Now, example, if you see, you can understand the algorithm, which is CS1, and another site, which is CS2, and one more site, which is H3, right? Now, site S1, site S1 has process P1, which is waiting for P2, right? But P2 in turn is waiting for P_x, so P_x waits for P1. And inside site S2, there are two processes—sorry, one process P3, which is waiting for another external process P_ex. So we can say we have to complete the loop like this. And in site S3, there is process P4, which is again waiting for an external process like this. Now, here site S2 is said to be an initiating site, let’s say, right? So this sends a path pushing message to S3. What will happen here is the local wait-for graph of S2 will be added with S3, right? So here, what happens is the local wait-for graph of S2 is P3, right? And here, look, S3 has P4, and one common external request. So P3 is requesting P_ex, and similarly, P4 is requesting P_ex, right? So P3 is, in turn, requesting P4. Now, on getting this message, S3 sends a message to S1, which in turn—if S3 sends a WFG (wait-for graph) update—then S1 will receive the WFG from S2 plus S3. In S1, what will happen here? Already, we have P_x, P3, P4, P_x1, and next P2, then P3, and then P4. So here, already P1 waits for P2, and now at site S1, there is a deadlock detector. Okay, so this is how the path pushing algorithm works. So, S2 pushes the path forward to S3, right? S3 updates it accordingly. Similarly, like this, right? And then, when this WFG (wait-for graph) is circulated to S1, this particular WFG is constructed, where there are no more sites in the line. So, at S1, it is decided that there is a cycle in the wait-for graph, meaning a deadlock is detected, right? So this is how the path pushing algorithm works.