3414

Briefly answer the following questions:

1. Compare the relative merits of centralized and hierarchical deadlock detection in a distributed DBMS.

2. What is a phantom deadlock? Give an example.

3. Give an example of a distributed DBMS with three sites such that no two local waits-for graphs reveal a deadlock, yet there is a global deadlock.

4. Consider the following modification to a local waits-for graph: Add a new node Text, and for every transaction Ti that is waiting for a lock at another site, add the edge Ti → Text. Also add an edge Text → Ti if a transaction executing at another site is waiting for Ti to release a lock at this site.

(a) If there is a cycle in the modified local waits-for graph that does not involve Text, what can you conclude? If every cycle involves Text, what can you conclude?

(b) Suppose that every site is assigned a unique integer site-id. Whenever the local waits-for graph suggests that there might be a global deadlock, send the local waitsfor graph to the site with the next higher site-id. At that site, combine the received graph with the local waits-for graph. If this combined graph does not indicate a deadlock, ship it on to the next site, and so on, until either a deadlock is detected or we are back at the site that originated this round of deadlock detection. Is this scheme guaranteed to find a global deadlock if one exists?