4.

Q: Suppose locking is not 2PL (that is, you may now release the locks before 
taking new ones). Show how Chandy-Misra-Haas algorithm may discover a phantom
deadlock.

A: Suppose 3 servers and 4 transactions.


T0 on S1 has locked u,
T1 on S1 has locked x,
T2 on S2 has locked y, and
T3 on S3 has locked z.

T0 is waiting for x (locally),
T1 is waiting for y,
T2 is waiting for z, and
T3 is waiting for u.

T1 suspects a cycle in the global WFG, because there is a local transaction T0 
th at is dependant on T1 and T1 is dependant on a transaction on other site, 
i.e. T2 on S2. T1 therefore sends a probe to T2 containing the arcs T0->T1 
and  T1->T2.

T2 receives the probe and adds T2->T3 to the graph. T2 sends the probe to T3.

T3 receives the probe and adds T3->T0 and sends the probe to T0. At this point 
T2 releases the lock on y it is holding (allowed since 2PL is not used). T0
recieves the probe and detects that it is dependant on itself, therefore a
deadlock exists, and all transactions in the graph are part of the deadlock.

Now, some transaction(s) is rolled back even though the deadlock detected is in
fact a phantom deadlock.