Consider the following deadlock-detection algorithm. When transaction T_i, at site S₁, requests a resource from T_j, at site S₃, a request message with timestamp n is sent. The edge (T_i, T_j, n) is inserted in the local wait-for of S₁. The edge (T_i, T_j, n) is inserted in the local wait-for graph of S₃ only if T_j has received the request message and cannot immediately grant the requested resource. A request fromT_i to Tj in the same site is handled in the usual manner; no timestamps are associated with the edge (T_i, T_j). A central coordinator invokes the detection algorithm by sending an initiating message to each site in the system. On receiving this message, a site sends its local wait-for graph to the coordinator. Note that such a graph contains all the local information that the site has about the state of the real graph. The wait-for graph reflects an instantaneous state of the site, but it is not synchronized with respect to any other site.

When the controller has received a reply from each site, it constructs a graph as follows:

• The graph contains a vertex for every transaction in the system.

• The graph has an edge (T_i, T_j) if and only if

There is an edge (T_i, T_j) in one of the wait-for graphs.

An edge (T_i, T_j, n) (for some n) appears in more than one wait-for graph.

Show that, if there is a cycle in the constructed graph, then the system is in a deadlock state, and that, if there is no cycle in the constructed graph, then the system was not in a deadlock state when the execution of the algorithm began.