|
CS245 PROBLEM SET #6
Due by 5:30pm, Tuesday, August 24, 1999
|
Problem 1: Tree Locking Protocol (10 points)
Suppose that we want to extend the tree locking protocol to consider shared
and exclusive locks for reading and writing, respectively. The tree locking
rule #2 (in the book and the notes), which requires to lock the parent of a
node before getting a lock on that node, must be changed to consider different
types of locks. What is the proper rule #2 for shared and exclusive locks, so
that it prevents unserializable behavior and still keeps as much concurrency
as possible? (Hint: Think about what the bad scenarios could be and how to
prevent them while keeping the most concurrency.)
Problem 2: Validation Protocol (10 points)
Suppose that we run the following transactions using the validation protocol.
The following table lists the transactions involved, together with their read
and write sets:
| | Read Set | Write Set |
| T1 | {C, E} | {E, D} |
| T2 | {E} | {A, C} |
| T3 | {D, A} | {G} |
| T4 | {B, C} | {D, A} |
| T5 | {C} | {B} |
| T6 | {C} | {D} |
The following sequence of events takes place. (No other transaction run before
or concurrently with T1 ... T6.)
1. T1, T2, T3, T4 start (in this order)
2. T1 initiates validation
3. T2 initiates validation
4. T5 starts
5. T3 initiates validation
6. T4 initiates validation
7. T5 initiates validation
8. T1, T2, T3, T4 finish (if they were not aborted earlier)
9. T6 starts
10. T6 initiates validation
11. T5, T6 finish (if they were not aborted earlier)
What is the outcome (COMMITTED if successful at validation, or ABORTED if not)
of each transaction? Briefly show the reasoning steps.
Problem 3: View Serializability (10 points)
Consider the following execution schedule of transactions T1, T2, and T3:
S = w1(A) w2(A) w2(B) r3(A) r1(B) w3(B)
Is this schedule view-serializable? Show the polygraph for the schedule,
and explain your answer based on the graph.
Problem 4: Distributed Commit (20 points)
In this problem, we need a notation for describing sequences of messages that
can take place during a two-phase commit. Let (i, j, M) mean that
site i sends the message M to site j, where the
value of M and its meaning can be P (prepare), R
(ready), D (don't commit), C (commit), and A
(abort). We shall discuss a simple situation in which site 0 is the
coordinator, but not otherwise part of the transaction, and sites 1 and 2
are the components. For instance, one possible sequence of messages that could
take place during a successful commit of the transaction is as follows.
(0, 1, P), (0, 2, P), (2, 0, R), (1, 0, R), (0, 2, C), (0, 1, C)
- (a)
- How many possible sequences of messages such as the above are there, if
the transaction successfully commits?
- (b)
- Give an example of a sequence of messages that could occur if site 2
wants to commit, but site 1 does not.
- (c)
- How many possible sequences of messages are there, if site 2 wants to
commit, but site 1 does not? Assume no failures occur.
- (d)
- Give an example of a sequence of messages that could occur if site 2
wants to commit, but site 1 is down and does not respond to messages?
- (e)
- How many possible sequences of messages are there, if site 2 wants to
commit, but site 1 is down?