Given the following scheme for distributed deadlock detection:

Processes are assigned unique priorities. When a process waits for an object being locked by another process, deadlock detection is initiated and a probe is sent out to the process where the object is locked. When a probe arrives at an unblocked process or a blocked process with priority higher than the probe initiator, the probe is discarded; otherwise the probe is forwarded along the wait-for edge. A deadlock is declared when a probe returns to the site where it is originated.

Given a scenario with 4 processes P0, P1, P2, and P3, and 4 resource types R0, R1, R2, and R3, where each process resides in a separate site and each resource type has a single instance. Currently, each Ri is assigned to Pi, for 0 ≤ i ≤ 3. Processes are prioritized, with P0 being the highest and P3 the lowest.

Suppose at this time, each Pi is requesting for resource R(i+1) mod 4, for 0 ≤ i ≤ 3. (A deadlock cycle should have formed as a result.) These requests will trigger deadlock detection according to the above scheme. Follow the analysis steps below to determine the total number of messages transmitted in detecting this deadlock.

Construct the resource allocation graph of this system.
Convert the resource allocation graph into a corresponding wait-for-graph. Observe the formation of a cycle, which represents the existence of a deadlock.
Find the number of messages transmitted from each probe initiated, and compute the total.
Generalize the above scenario to n processes in n sites, with each process holding a separate resource and requesting for an assigned resource in the same pattern as described above, and determine the total number of messages transmitted for the detection of the existing deadlock.
above represents the worst case performance for the given deadlock detection scheme in terms of the total number of messages transmitted for detecting a deadlock formed under the following conditions: every site is running one process, resource requests by individual processes are limited to one resource at a time, and there is currently a deadlock cycle that involves all n processes. Find the performance of the scheme for a best case scenario with n processes.