CS 5204 - Fall, 2009
Problem Set 6
20 points
 Assigned: September 29, 2009
Due: October 6, 2008 (noon)  

1. (6 points) See Figure 1 in the paper Software Transactional Memory for Dynamic-Sized Data Structures. The  main while loop in the insert method has the code "catch (Denied d) {}".
(a) Explain the purpose of a Denied exception.
(b) Give an example of why a Denied exception might have been thrown in the insert method.
(c) Explain the relationship between a Denied exception and conflict detection in DSTM?

2. (5 points) See Figure 1 in the paper Language Support for Lightweight Transactions. The first operation in the while loop is STMStart(). The paper also says "It is an error to invoke STMStart if the current thread is already running a transaction." (6th page, left column at top). This appears to be a contradiction because the while loop may execute the STMStart operation more than once. Explain.

Shown below are the logs from a distributed database system. The first entry in Log1  ( R4(V1) ) denotes that a Read operation was performed on behalf of transaction 4 of the data item V stored on data manager 1. The second entry in Log1 ( W3(V1) ) denotes that a Write operation was performed on behalf of transaction 3 of the data item V stored on data manager 1.
   
    Log1:  R4(V1), W3(V1), R2(X1), W1(V1)

    Log2:  R3(W2), W3(V2), R1(W2), W1(Z2), W1(V2), W2(Z2)

    Log3: R3(Z3), W3(V3), R1(V3), R4(Z3), W1(V3), W2(Z3)

3. (3 points) Show all pairs of conflicting transactions in these logs.

4. (3 points) To what, if any, serial execution are these logs equivalent?

5. (3 points) State three insightful questions about the concepts of serializeability and transactions based on the readings assigned for the course.