Part I due by 11:59 p.m. on Tuesday, April 8, 2025.
Part II due by 11:59 p.m. on Tuesday, April 22, 2025.
In your work on this assignment, make sure to abide by the collaboration policies of the course. All of the problems in this assignment are individual-only problems that you must complete on your own.
If you have questions, please come to office hours, post them on
Piazza, or email cs460-staff@cs.bu.edu.
Make sure to submit your work on Gradescope, following the procedures found at the end of Part I and Part II.
50 points total
Create a subfolder called ps4 within your
cs460 folder, and put all of the files for this assignment in that
folder.
This part of the assignment will all be completed in a single PDF file. To create it, you should do the following:
Access the template that we have created by clicking on this link and signing into your Google account as needed.
When asked, click on the Make a copy button, which will save a copy of the template file to your Google Drive.
Select File->Rename, and change the name of the file to
ps4_partI.
Add your work for all of the problems from Part I to this file.
Once you have completed Part I, choose File->Download->PDF
document, and save the PDF file on your machine. The resulting
PDF file (ps4_partI.pdf) is the one that you will submit. See
the submission guidelines at the end of Part I.
30 points total; 10 points each part
Consider the following sequence of operations involving four transactions and two data items, A and B:
s1; s2; s3; s4; w1(A); r4(A); w3(B); w2(B); w3(A); r2(A); w4(B); r1(B); c1; c2; c3; c4
where si indicates the start of transaction Ti, which is when its
timestamp is assigned, and ci indicates the commit of
transaction Ti.
Assume that the transactions are assigned the following timestamps, based on the order in which they start:
and that RTS(A), WTS(A), RTS(B) and WTS(B) are all initially 0.
Given these assumptions, complete the following exercises:
In the first table for this problem in ps4_partI, we’ve filled
in the row for the first operation in the above sequence of
operations. Complete the table to show how the system would
respond to the remaining read and write requests when it is using
regular timestamp-based concurrency control without commit
bits.
Guidelines:
In the second column of the table, indicate the response of the system by selecting the correct option from the following list:
Note: If a transaction is rolled back, you should not restart it, and you should use the “doesn’t occur” option for any of its remaining read or write requests – ones that occur after the point at which it is rolled back.
In the third column of the table, you should do one or more of the following:
If the action is ignored or denied, include a brief explanation. For example, if a transaction T7 tried to read item C and its read were too late, you would include something like this:
TS(T7) < WTS(C)
Summarize any changes to the state maintained for items A and B, as we’ve done in the first row. Note that there may be changes in the state of one or both items even when an action is denied.
If an action is allowed and it doesn’t lead to any changes in the state maintained for the items, simply put “no changes”.
Because commits don’t have an effect when we’re not using
commit bits, you should not include the commit actions
(c1, c2, etc.) in this table.
Complete the second table that we’ve provided to show the system’s response to the above sequence of operations if the DBMS is using regular timestamp-based concurrency control with commit bits.
Guidelines:
In the second column of the table, there are now six options to choose from:
Note: If a transaction is made to wait, it cannot make any forward progress until the wait comes to an end. Therefore, you should temporarily skip any operations by that transaction in the schedule and use the option “skip for now; waiting” in the second column.
In the third column of the table, make sure to also include changes to an item’s commit bit when appropriate. For example, “c(A) = false” or “c(B) = true”.
In the table that we’ve provided for this problem, there is a thick line after the initial set of read and write requests. Below that thick line, there are extra rows that you should use as needed for:
any commit actions that are able to occur, since they may cause a change in state. However, if a transaction has been rolled back, you should not include its commit action in the table. Make sure that you don’t commit a transaction until all of its operations have been completed.
operations by transactions that have been made to wait. When a transaction’s wait comes to an end, you should include another row in the table to show what happens when the transaction retries the read or write request that caused the wait. In addition, you should include another row for any action that was skipped while the transaction was waiting. See below for additional details on how to handle waiting transactions.
You may not need all of the extra rows.
If more than one transaction is waiting for the same transaction, when the wait comes to an end, you should assume that the waiting transaction with the smaller transaction number (call it T) is allowed to try again first. In addition, if you needed to skip actions by T while it was waiting, you should make as much progress as possible with those skipped actions before you allow the next waiting transaction to try again.
Complete the third table that we’ve provided to show the system’s response to the above sequence of operations if the DBMS is using multiversion timestamp-based concurrency control without commit bits.
Guidelines:
In the second column of the table, you should use one of the following options:
When a transaction is allowed to read an item, make sure to indicate which version it is allowed to read (e.g., “allowed to read A(t)”, where t is the write timestamp of the version).
In the third column, make sure to specify which version’s state is being updated (e.g., “create A(t) with RTS = 0, WTS = t” or “RTS(A(t)) = ...”, where t is the write timestamp of the version). In addition, you should include the relevant version of an item in any explanation of why an action wasn’t allowed.
Because commits don’t have an effect when we’re not using
commit bits, you should not include the commit actions
(c1, c2, etc.) in this table.
20 points total
Assume that a database is replicated using synchronous replication across 11 different sites. In other words, there are 11 copies of each item.
Consider the following voting schemes:
Fill in the tables that we’ve provided to answer the following questions:
Would these voting schemes work if the system uses fully distributed locking? Follow the guidelines below.
Would these voting schemes work if the system uses primary-copy locking? Follow the guidelines below.
Guidelines:
If a given scheme would work, put “yes” in the second column of the table and use the third column to specify the inequality or inequalities that allow you to draw that conclusion.
For example, in lecture we considered a voting scheme in which there were 9 copies instead of 11, and a transaction needed to read 5 copies and write 5 copies. One of the relevant inequalities for determining that this scheme works is 5 > 9 - 5. Depending on the type of locking, you might also need to include the inequality 5 > 9/2. (Make sure to adjust your inequalities to specifics of each scheme – including the fact that there are 11 copies of each item, not 9!)
If a given scheme would not work, put “no” in the second column of the table. In the third column, you should not specify the relevant inequalities. Rather, you should specify all possible problematic scenarios that could arise under that scheme by including all of the items below that apply, based on the voting scheme and the type of locking:
A transaction may not always read the most up-to-date value of a given item.
Two transactions can get a global exclusive lock for the same item at the same time.
If one transaction has a global exclusive lock for an item, another transaction can get a global shared lock for that item, and vice versa.
Coming soon!
50 points total
Last updated on April 2, 2025.