
Solutions for Section 19.1
Solutions for Section 19.2
Solutions for Section 19.3
Solutions for Section 19.4
Solutions for Section 19.5
Solutions for Section 19.6
Solutions for Section 19.7
If locking is strict, then the two unlocks must occur, in either order, after the second write action. Thus, there are 6 orders for strict, 2phase locking.
If locking is not strict, the unlock of B must occur after w_{1}(B), but then the unlock of A can occur in any of the three positions after w_{1}(A). Thus, there are 9 orders if strictness is not required, and 3 of these must be nonstrict.
Each transaction reads only one element, so the question is, does it read from the other? If so, then in order for the schedule to be recoverable, it must commit after the other as well. That is, the two constraints on the schedule can be expressed:
The partial orders that violate (1) look like:
o>o>o>o  ^ v  o>o>o>o
With a little effort, we can find that there are 12 orders for the eight nodes involved.
The orders that violate (2) are similar; they have the constraints:
o>o>o>o  ^ v  o>o>o>o
There are 10 of these. Since there are {8 choose 4} = 70 orders in all, 48 of them are recoverable.
_____________________   A  v B T_0 > T_{1} T_{2} > T_{3} > T_{f}   A ^ ^  __________________   A  ______________________________
Above is the polygraph. We have labeled with A the arcs due to the reading of A, and likewise for B. The two unlabeled arcs are secondphase requirements that the other writers of B  T_{1} and T_{2}  not interfere with the reading of B. by the final ``transaction'' T_{f}.
Clearly, T_{3} must come last in an viewserializable schedule, but there is no required ordering of T_{1} and T_{2}. Notice that conflictserializability would require T_{1} to precede T_{2}, because their writes of B cannot swap places.
Start with the three writes. We can only place r_{1}(A) prior to w_{1}(B). Next, we can place r_{2}(A) in any of the three positions prior to w_{2}(B). At the last step, there are now five places where we can put r_{3}(A) prior to w_{3}(B). Thus, there are 15 conflictequivalent schedules.
For viewserializable orders, there are the above 15, and another 15 in which w_{1}(B) is placed after w_{2}(B). Intuitively, we can do so because neither T_{1} nor T_{2} have their value of B read, so the order in which they write doesn't matter.
T_{3} > T_{2}
At the next step, T_{2} must wait for T_{1}, which has a lock on C. The waitsfor graph is:
T_{3} > T_{2} > T_{1}
Next, w_{4}(A) causes T_{4} to wait for T_{1}. There is still no cycle, and the waitsfor graph is:
T_{3} > T_{2} > T_{1} < T_{4}
Finally, T_{1} tries to write D. It cannot get the exclusive lock on D that it needs, because T_{3} holds a shared lock on D. If we allowed T_{1} to wait, the graph would be:
T_{3} > T_{2} > T_{1} < T_{4} ^  ___________________
Thus, T_{1} must abort and relinquish its locks. At that time, T_{2} and T_{4} can each get the locks they need. When T_{2} finishes, T_{3} can proceed.
Initially, T_{1} locks A and T_{2} locks B and then requests a lock on A. T_{2} therefore waits for T_{1}. Meanwhile, T_{3} starts and requests a lock on B. Thus, T_{3} waits for T_{2}, and the waitsfor graph is:
T_{3} > T_{2} > T_{1}
When T_{1} requests a lock on A, it would cause a cycle, so T_{1} is rolled back. Now, T_{2} completes and releases its locks. The lock on A is given to T_{1} and the lock on B is given to T_{3}. Next, T_{3} requests a lock on A, but has to wait for T_{1}. Also, T_{4} starts up and requests a lock on B, thus being forced to wait for T_{3}. The waitsfor graph is now:
T_{4} > T_{3} > T_{1}
The above graph is just like the first, except T_{4} and T_{3} have replaced T_{3} and T_{2}, respectively. As long as there is a supply of transactions like T_{2}, T_{3}, and T_{4}, they can prevent T_{1} from finishing ever.
Notice that the transactions in the example above request locks on A and B in different orders. Perhaps forcing transactions to request locks in a fixed order will solve the problem. Indeed, if we follow the policy that when a lock becomes available, it is given to a waiting transaction on a firstcomefirstserved basis, then any transaction that is waiting for a lock will eventually become the transaction that has been waiting for the lock the longest. At that point, the next time the lock becomes available, it will be granted to that transaction, which thus makes some progress. The above observation is the germ of an inductive proof that requesting locks in order plus firstcomefirstserved will allow every transaction eventually to complete.
However, if the scheduler is able to give locks to any transaction it wishes, then it is easy to make a transaction starve. Suppose T_{1} wants a lock on A when some other transaction has that lock. As long as there is always another transaction besides T_{1} waiting for a lock on A, and the scheduler always chooses to give the lock to some transaction other than T_{1} when the lock becomes available, T_{1} never makes any progress.
Last, let us consider deadlock prevention by timeout. If the duration before a timeout can vary even slightly, then the example given initially for deadlock prevention by avoiding cycles will work. That is, even though T_{2} has been waiting slightly longer for a lock than T_{1}, if we allow that T_{1} might timeout first, then the sequence of events described above could also occur with timeoutbased deadlock prevention.
If timeouts occur for any transaction at exactly t seconds from when it first started to wait, then we need a simple modification of the above example. Assume that T_{1} is faster at requesting its second lock than any of the other transactions. Then, after T_{1} gets a lock on A and T_{2} gets a lock on B, T_{1} next requests its lock on B and starts to wait. Slightly later, T_{2} requests a lock on A. T_{3} requests its lock on B just before T_{1} times out, so when that timeout occurs, T_{2} completes, gives its Alock to T_{1} and its Block to T_{3}. When T_{2} next requests a lock on B and starts to wait, this cycle can repeat with T_{3} and a new T_{4} in place of T_{2} and T_{3}.
Now, consider the value of creating a copy of R at site i. On the positive side, the queries generated at site i that used to have to be answered remotely, at a cost of 10cq_{i}, can now be answered for cq_{i}, a positive benefit of 9cq_{i}.
However, the additional copy of R has to be updated. The cost is du_{i} for the updates generated at site i and U  10du_{i} for the updates generated at all other sites. Recall that U represents the cost of a remote update for all generated updates, so if we subtract 10du_{i} we get just the cost of the updates that do not originate at i.
In order for the benefit of creating a copy at i to outweigh the additional update cost, we must have
Thus, the optimal selection of sites at which to maintain copies of R is all sites for which the above inequality holds. Roughly, we favor those sites at which there is a lot of activity, but the larger U is (i.e., the greater the update rate), the less likely we are to want to create many copies.
There is one special case: what if the inequality fails for all i; that is, it is not cost effective to create any copies. As long as all the q_{i}'s are zero, that's OK. The proverbial ``writeonly database'' needs no copies! However, in realistic cases with a heavy update rate, we shall be forced to create one copy. The correct choice is whichever i has the largest value of cq_{i} + du_{i}.
In the second phase, the coordinator can send commit messages to the other two sites in either order. There are thus 6 * 2 = 12 possible message sequences.
just as for the shared + increment system discussed in the section. We also cannot allow a shared and exclusive lock at the same time, which tells us:
Likewise, we cannot have an exclusive and increment lock at the same time, so:
Finally, we cannot have a shared and increment lock at the same time, so:
For example, we could require that any type of lock requires a majority. We cannot allow both s and i to be n/2 or less, because of the last inequality. But we could let one of s and i be 1, while the other, and x, are both n.
To see that this compensation works, we can consider all the possible cases above, and check that the file system, after compensation, is the same as would be the case had f never been written. If f was overwritten before compensation, then we surely leave the file system in the same state as if f were never written. If f is not overwritten, then we have correctly left the file with that name being either f', if it existed, or left the file system with no file of that name.
There are two interesting issues. First, in order for there to be a compensating transaction, it seems we must both remember the time at which the installation occurred (so we can tell whether the file f has been overwritten when the uninstallation occurs), and we must also remember the file f', at least until such time as the file is overwritten, and the new value is itself guaranteed never to be uninstalled (i.e., the saga that wrote it has finished). These features are not commonly available.
Second, note that file systems do not support serializability. Thus, it is entirely possible that the uninstalled file f has been read, and its contents have influenced other files or the behavior of the system.