Consider the following hierarchical deadlock-detection algorithm, in which the global wait-for graph is distributed over a number of different controllers, which are organized in a tree. Each non-leaf controller maintains a wait-for graph that contains relevant information from the graphs of the controllers in the subtree below it. In particular, let SA, SB, and SC be controllers such that SC is the lowest common ancestor of SA and SB (SC must be unique, since we are dealing with a tree). Suppose that node Ti appears in the local wait-for graph of controllers SA and SB. Then Ti must also appear in the local wait-for graph of
• Controller SC
• Every controller in the path from SC to SA
• Every controller in the path from SC to SB
In addition, if Ti and Tj appear in the wait-for graph of controller SD and there exists a path from Ti to Tj in the wait-for graph of one of the children of SD, then an edge Ti → Tj must be in the wait-for graph of SD.
Show that, if a cycle exists in any of the wait-for graphs, then the system is deadlocked.