How does timestamping cause a global deadlock?

Question

I read about the advantages / disadvantages of using timestamps to control concurrency in a distributed database. The material I read mentions that while timestamps overcome traditional deadlock problems that can affect locking, there is still a “global deadlock” problem to which it is vulnerable.

The material describes the global deadlock as a situation where there is no cycle in the waiting graphs of local graphs, but there is a cycle in the global graph.

I wonder how can this happen? Can someone describe a situation where a timestamp system can cause this problem?

Answer 1

Here is an example, perhaps the simplest. We have cars A and B Machine A has locks T1 and T2 with a ratio T1 < T2 . Machine B has T3 and T4 with T3 > T4 .

Now local charts are just what T2 has to wait while T1 and T3 have to wait for T4. So there are no local loops. But now suppose we have T4 < T1 , so T1 must wait for T4. And at the same time, T2 < T3 , so T3 must wait for T2. In this case, there is a global loop.

So how does this cycle go? The key point here is that you will never have complete information in a distributed system. Therefore, we can later find out that there are intermotor dependencies. And then we have a problem.

Answer 2

Timestamping is used to determine the resolution of conflicts between local processes on a machine. This provides a means to eliminate deadlocks at this level. For distributed processes, there is the possibility of two processes on different machines that are waiting for each other. This is actually a regular dead end, but through cars. This is called a "global" dead end. Imho timestamping can be used there as well, but is apparantly impractical.

Some information about this can be found at http://www.cse.scu.edu/~jholliday/dd_9_16.htm