Consider the following hieran hical 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 form SC to SA
Every controller in the path from SC to SA
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.
A proof of this can be found in the article Distributed deadlock detection algorithm which appeared in ACM Transactions on Database Systems,Volume 7,Issue 2 (June 1982),ages: 187- 208.