Edge Chasing Algorithm Here, what we were given is Chandy-Misraha algorithm, right? K. Chandy-Misraha’s algorithm. Here, an adjacent, there is a special data structure called probe involved, which is a triplet. The probe is a triplet, right? It takes the form probe(i, j, k). That means, right? So here, i is the initiating process. Let’s say this is P_i, and j is the sending process who sends the probe, okay? So, which is P_j, and k is the receiving process which receives the probe, which is P_k, okay? In such a way, the probe is formulated and circulated. Now, coming to the example, right? So, in this example, there is site 1. In site 1, there are two processes, P_i and P_j, right? There is a dependency, and another site is here. In this site, one more process P_k resides. Now, if there is a problem, but now P_j at site S1 is waiting for site S2’s resource, right? So, that is a dependency that exists. Now, the probe can be written as follows. Here, because the initiating dependency starts from P_i, okay? So, this is what the i is in this side. So, i, j—j is the sending process. The probe is sent from P_j, which is the process at site 1, and P_k is the process receiving the probe at site 2. So, P_j, P_k. This is how an individual probe is developed, okay? Now, coming into the example, here, there are four different sites, right? Four different sites. Process P1 is waiting for P2. P2, in turn, is waiting for P3. Suppose there is no more interdependency, there is only local waiting. Then, here, there is no deadlock. Deadlock is discarded as per the algorithm. In an individual local site, there is only a local dependency. There is no external dependency, so no deadlock, okay? Now, P3 is waiting for P4. P4 is waiting for P5. P5 is waiting for P6. P6 is waiting for P7. P7 is waiting for two resources available at P8 and P9, then P10, right? So, then P10 is waiting for P11, P11 is waiting for P12, and this is how the dependency exists. Now, let’s see how the probe is sent. So, here, the probe—what was the initiating process? P1. So, (1, 3, 4)—where 1 is i, 3 is j, and 4 is k. P3 is the sending process at site 1, and P4 is the receiving process. Now, what is the probe for site 2 and site 3? For site 2, P4 is not going to be the initiating process. Here, P6 is the sending process (j), and P7 is the receiving process (k). So, (6, 7, k). Now, here, what is the probe? There are two probes from site 3 to site 4. The first here is as usual. 1 is the initiating process, here P8 is j, and P10 is k. Likewise, the second probe here is (1, 9, 10). And here, what is the probe? (1, 12, 1), right? Okay. Now, look at the final probe. Any problem in the path? It’s a chasing algorithm, chasing the edges. So, when chasing it, if any probe i = k, if i = k, yes, here P1 = P1. What is k? It is also P1. Here, P1, P1. So, there is a cycle, meaning deadlock exists. Deadlock exists, okay? So, this is how the Chasing Algorithm works, right?