Part I due by 11:59 p.m. on Tuesday, November 4, 2025.
Part II due by 11:59 p.m. on Monday, November 24, 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.
40 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.
16 points total; 8 points each part
Consider the following sequences of operations by concurrent transactions:
sequence 1:
r3(A); w3(A); r1(C); r1(A); r2(B); w2(C); r3(C); w3(B)
sequence 2:
r1(A); w1(B); r3(C); r3(B); w3(B); r2(C); w2(C); w1(A)
For each of these sequences, determine whether deadlock will occur under rigorous two-phase locking. You should assume that:
In your copy of ps4_partI, fill in the table and edit the diagram
to show the outcome of each sequence of actions.
If deadlock occurs for a given sequence, fill in the table with the partial schedule (including lock and unlock operations, and any commits) up to the point of deadlock. In addition, edit the diagram to show with the waits-for graph at the point of deadlock.
If deadlock does not occur, show the full schedule, including lock and unlock operations and commits, along with the partial waits-for graph that you created while building the full schedule.
If a transaction needs to wait for a lock:
You should show the lock request, followed by a note that indicates the need to wait and which tranaction is it waiting for (e.g., “waits for T1”).
While the transaction is waiting, you should skip any of its actions in the schedule because a waiting transaction cannot make any forward progress until the lock that it’s waiting for is granted!
If the lock request is subsequently granted, you should show the lock request again at the point at which it is granted. Then you can continue with the rest of that transaction’s actions from the schedule. Note that waits may cause the actual sequence of operations to be different than the original sequence.
If two transactions wait for a lock held by the same other transaction, and that other transaction releases the lock, 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.
24 points total; 8 points each part
Consider the following sequence of operations involving four transactions and two data items, A and B:
s1; s2; s3; s4; r2(A); w3(B); r2(B); r3(A); w1(B); r4(B); r1(A); w1(A); 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.
Login to Gradescope by clicking the link in the left-hand navigation bar. Once you are in logged in, click on the box for CS 460.
Submit your ps4_partI.pdf file using these steps:
If you still need to create the PDF file, open your file on Google Drive, choose File->Download->PDF document, and save the PDF file on your machine.
Click on the name PS 4: Part I in the list of assignments. You should see a pop-up window labeled Submit Assignment. (If you don’t see it, click the Submit or Resubmit button at the bottom of the page.)
Choose the Submit PDF option, and then click the Select PDF
button and find the ps4_partI.pdf that you created in step 1.
Then click the Upload PDF button.
You should see an outline of the problems along with thumbnails of the pages from your uploaded PDF. For each problem in the outline:
As you do so, click on the magnifying glass icon for each page and doublecheck that the pages that you see contain the work that you want us to grade.
Once you have assigned pages to all of the problems in the question outline, click the Submit button in the lower-right corner of the window.
You should see a box saying that your submission was successful.
Click the (x) button to close that box.
You can use the Resubmit button at the bottom of the page to resubmit your work as many times as needed before the final deadline.
Important
It is your responsibility to ensure that the correct version of a file is on Gradescope before the final deadline. We will not accept any file after the submission window for a given assignment has closed, so please check your submission carefully using the steps outlined above.
If you are unable to access Gradescope and there is enough
time to do so, wait an hour or two and then try again. If you
are unable to submit and it is close to the deadline, email
your homework before the deadline to
cs460-staff@cs.bu.edu
60 points total
Last updated on October 29, 2025.