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.
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
50 points total
Important
You may complete the first two problems from this section with a partner, but the final two problems must be completed on your own.
In this assignment, you will write Java programs to run MapReduce jobs using Apache Hadoop.
Because it can be challenging to install and run Apache Hadoop locally, you will instead be running and testing your programs on Gradescope after eliminating any syntax errors in your code. You will NOT be running them on your own machine.
The Autograder will run Hadoop in local mode, which simulates a distributed cluster. However, the programs that you construct could also be run on a real cluster without modification – and they could handle much more data than we will be using in our testing!
Our problem domain is a social network database that contains information about users and their connections to other users in the network.
The data is stored in one or more plain-text files, where each line of a given file represents a single user and looks something like this:
48,Brown,Matthew,1989-11-05,mbrown@gmail.com,189,305,17,31;56,23,32,188,549
From left to right, each line contains the following fields:
The fields are comma-separated, with the exception of a semicolon that appears before the friend list. However, if a user has no friends, the line will not contain a semicolon.
Here’s a subset of lines from the largest input file (users200k.txt
),
showing a number of different (though not all!) variations:
65,Lewis,James,1965-12-26,jlewis1965@hotmail.com,257,7,227;911255,176121,554966,671982,775492,834730,948609 80,Lawson,Emerald,1997-10-01,270,144,368,201,484,8;40146,44545,285685,734547,861038 201,White,Alexander,1958-08-19,awhite1958@yahoo.com;979442,33777,416988,823482,920887,929242
You should begin by downloading the following zip file:
ps4_mapreduce.zip
Unzip/extract the contents of the file.
Depending on your system, after extracting the contents you will either have:
a folder named ps4_mapreduce
that contains all of the files that
you need for the map-reduce problems
an outer folder called ps4_mapreduce
that contains an inner
folder named ps4_mapreduce
that contains all of the Java
files that you need.
Take the ps4_mapreduce
folder that actually contains the necessary
files and drag it into your ps4
folder so that you can easily find
and open it from within VS Code.
Launch VS Code on your laptop.
In VS Code, select the File->Open Folder or File->Open menu
option, and use the resulting dialog box to find and open the
problem6
folder that you created above – the one that contains the
provided files. (Note: You must open the folder; it is not
sufficient to simply open one of the Java files in the folder.)
The name of the folder should appear in the Explorer pane on the left-hand side of the VS Code window, along with a list of all of its contents.
Review the provided files. We have given you:
WordCount.java
- a sample MapReduce program that you are welcome
to use as a template for your programs
starter code for each of the problems (Problem3.java
,
Problem4.java
, etc.)
data
- a folder containing sample input data files for the
problems you will solve. They include users20.txt
, which we
use by default when testing your programs on Gradescope (see
below).
IMPORTANT: You should NOT try to run any of these programs on your own machine! Rather, you should follow the procedures outlined below.
As mentioned above, we will be running and testing your programs on Gradescope instead of on your own machine.
However, you should still use the compiler in VS Code to eliminate any syntax errors in your programs before you try to test them on Gradescope.
Finding and eliminating syntax errors
Click on the name of program in the Explorer pane to open it in the Editor window.
Open a Terminal window in VS Code, and click on the Problems tab at the top of the Terminal window.
Locate any error messages for the program you’re working on. They begin with a red circle with an X in it. Clicking on the error message will show you the corresponding line from your code.
Note: You may see some warning messages, which begin with a
yellow triangle symbol that contains an exclamation mark (!
).
These can be safely ignored.
Make whatever changes are needed to eliminate all of the error messages.
Remember: do NOT try to run your code on your own machine!
Testing and debugging
Once you have eliminated the syntax errors, save the program in VS Code.
Upload the program to Gradescope. Each problem has its own Gradescope page, and you have two options that you can use for testing:
Upload just the program itself (i.e., the Java file). Doing so will run the program on a small input file and compare the results to the expected results.
Upload the program and one or more input files like the ones
we give you in the data
folder. Doing so will run the
program on those input files and show you the results, but it
will not assess their accuracy. By enabling you to create and
use your own input files, this testing option will allow you
to ensure that your code handles edge cases that may not be
present in the default input file.
Review the results displayed in Gradescope.
Fix any logic errors and resubmit until you obtain the correct results.
Important: To assist you in debugging, you can add
temporary println
statements to your code. If you do so,
Gradescope will include the output of those statements as part of
the results that it displays.
Employ good programming style. Use appropriate indentation, select descriptive variable names, localize variables, insert blank lines between logical parts of your program, and add comments as necessary to explain what your code does.
Your nested classes for mappers and reducers should extend the
built-in Mapper
and Reducer
classes, as discussed in lecture
and shown in WordCount.java
. Your mapper classes will override
the inherited map()
method, and your reducer classes will override
the inherited reduce()
method. You should not override or make
use of the other inherited methods of the Mapper
and Reducer
classes.
You are welcome to include additional helper methods in your classes as needed, although doing so is not required. You may also include additional helper classes for a given problem, but they should go in the same file as the rest of the code for that problem, and they should also be nested static classes.
You will need to determine how to correctly parse each line in the input file. In particular, you will need to account for the optional fields in a given line. We encourage you to use the following methods as needed:
the String
method called split()
that we discussed in lecture.
(Note: We have imported the java.util
package at the top of
each file so that you can use the Arrays.toString()
method
as needed. You may find it useful during debugging, since it
can take the array produced by split()
and turn it into a
string that you can print using a temporary println
statement.)
other String
methods like indexOf()
and substring()
; however, you should not use anything that isn’t
available in Java 8
the following static methods for converting from a Java
String
object that is the string representation of a number
to the corresponding numeric value:
Integer.parseInt()
Long.parseLong()
Double.parseDouble()
You may assume that the birthdate and email fields are
well-formed; that is, the birthdate will always be of the form
YYYY-MM-DD, where YYYY is the four-digit birth year, MM is the
two-digit month, and DD is the two-digit day. The email, if present,
will contain an occurence of the @
character to separate the user
name from the domain.
You should limit yourself to the packages that we’ve imported at the top of each starter file. You must not use classes from any other Java package.
You should only use features of Java that were available in Java 8.
You should not use any global variables (i.e., static class variables) in your programs. Class constants (i.e., static final variables) are fine if needed.
Feel free to use these resources as needed:
13 points; pair-optional
This is one of only two problems in this assignment that you may complete with a partner. See the rules for working with a partner on pair-optional problems for details about how this type of collaboration must be structured.
Write a MapReduce program to find the number of users for each email-address domain. The output of the program should be (key, value) pairs in which the key is an email-address domain and the value is the number of users that have addresses from that domain. For example:
icloud.com 500 gmail.com 250 ...
(although you will get different numbers than the ones shown above!)
Notes:
In Problem3.java
, we have given you a template for your code.
You only need to implement the bodies of the map
and reduce
methods.
To allow for large numbers (i.e., long integers) in the final
results, we’ve specified that the values output by the reducer
should be of type LongWritable
. Make sure that your code
uses a variable of type long
when determining the counts.
Use the birth-month counter program from lecture as a model for what you should do.
Don’t forget that not all user records include an email address. However, you may assume that at least one of the input records includes an email address.
You may assume that all email addresses include an @
symbol.
If a given user doesn’t have an email address, the map
method can
simply return without writing anything.
Make sure to follow the guidelines given above for how to compile and test your program.
13 points; pair-optional
This is one of only two problems in this assignment that you may complete with a partner. See the rules for working with a partner on pair-optional problems for details about how this type of collaboration must be structured.
Write a MapReduce program to find the email domain with the oldest users – i.e., the domain whose users have the largest average age. The final output should be a single (key, value) pair in which the key is the email domain with the youngest users, and the value is the average age of that domain’s users, specified as a floating-point number. If there are multiple email domains whose members are tied for the smallest average age, your program may report any one of them.
Notes:
You will need a chain of two MapReduce jobs for this problem. We discussed how to do this in lecture.
The second job will process the results of the first job. Because
those results are stored in a text file, the key-value pairs
passed into the second map
function will have the following
format:
The key will be a file-offset value that you should ignore –
just as any other map
function that processes data stored in
a text file typically ignores its keys.
The value will be a Text
value consisting of one line from
the results file produced by the first job. In other words, it
will contain one of the key-value pairs written by the first
job’s reduce
function, with a single tab character ("\t"
)
between the key and the value.
In the second job, the map
function should ensure that all of the
(key, value) pairs that it outputs have the same constant key.
You may either use a string or an integer for this purpose. Using
a constant key will ensure that all of these pairs go to a
single reducer task, which will then be able to determine which
email domain’s users have the smallest average age.
When determining a user’s age, you should simply subtract the
person’s year of birth from 2025, regardless of when their
birthday is. For example, if someone has a dob string of
"2000-10-21"
, they should be considered to have an age of 25
(because 2025 -
2000 = 25), even though they haven’t celebrated
their birthday yet this year.
When computing the average age for an email domain, make sure to take into account how the division operator works in Java. In order to perform floating-point division, at least one of the two operands must be a floating-point number. One way to ensure this is to use a type cast.
You can convert the string representation of an integer into a
value of type int
by using the built-in Integer.parseInt()
method. Similarly, you can convert the string representation of a
floating-point number into a value of type double
by using the
built-in Double.parseDouble()
method.
We have given you templates for the two sets of mapper and reducer classes, but they are more limited than what we provided for the previous problem. In particular:
The extends
clauses for the mapper and reducer classes
look like this:
extends <Object, Object, Object, Object>
As needed, you should replace a given occurrence of Object
with the class name for the appropriate Hadoop data type. See
the lecture notes for a reminder of the purpose of each of the
four types.
We haven’t given you headers for the map
and reduce
methods. Make sure that you use the appropriate
types for the parameters of these methods, and that you
include the same throws
clauses that we used for those
methods in the previous problem.
In the main
method, you should modify as needed the lines
that specify the classes for the output keys and output values
of the mappers and reducers. You should not change the
other lines in this method.
12 points; individual-only; you MUST complete this problem on your own
Recall that a user’s record may optionally include one or more group IDs – ID numbers of groups to which the user belongs. For example, consider the following record:
63,Gutierrez,Mary,1961-07-12,mary.gutierrez1@hotmail.com,10,19;55
It indicates that Mary Gutierrez belongs to two groups: group 10 and group 19. Note that 55 is not a group ID; see the description of the format of the data at the start of Part II.
Write a MapReduce program to determine, for each group ID number, a count of the number of members in that group who are 50 or younger (i.e., born in 1975 or later). The output of the program should be (key, value) pairs in which the key is a group ID number and the value is the number of users who belong to that group and were born in 1975 or later. If a group doesn’t have any group members 50 or younger, its ID number should still appear in the results file with a value of 0.
Notes:
You will only need a single map-reduce job.
Once again, we have given you a template for your code, and you
will need to select and fill in the appropriate class names in the
extends
clauses for the two inner classes, and then define
appropriate map
and reduce
methods.
Here again, you should modify as needed the lines in the main
method that specify the classes for the output keys and output
values. You should not change the other lines in this method.
Don’t forget that not all user records include a list of group
IDs. However, you may assume that at least one of the input
records includes such a list. If a given record doesn’t have any
group IDs, map
can simply return without writing anything.
You can convert the string representation of an integer into a value
of type int
by using the built-in Integer.parseInt()
method.
Make sure that your solution is able to accommodate large final counts.
12 points; individual-only; you MUST complete this problem on your own
In the previous problem, you found per-group counts of members 50 or younger. In this problem, you will find the group with the largest number of such members. The final output of the program should be a single (key, value) pair in which the key is the ID of the group with the most members 50 or younger, and the value is the number of members of that group. If there are multiple groups that are tied for the most members 50 or younger, your program may report any one of them.
Notes:
As in Problem 4, you will need a chain of two MapReduce jobs for this problem.
Don’t forget that not all user records include a list of groups. However, you may assume that there is at least one record that includes a group, and thus there will always be a final result.
Make sure that your solution is able to accommodate large final counts.
You can convert the string representation of a long integer into a
value of type long
by using the built-in Long.parseLong()
method.
As we did in Problem 4, we have given you templates for
the two sets of mapper and reducer classes, and you will need to
select and fill in the appropriate class names in their extends
clauses, and then define the appropriate map
and reduce
methods.
Here again, you should modify as needed the lines in the main
method that specify the classes for the output keys and output
values of the mappers and reducers. You should not change the
other lines in this method.
You should submit only the following four files:
Problem3.java
Problem4.java
Problem5.java
Problem6.java
Each problem should be submitted to its own Gradescope page.
Here are the steps:
Login to Gradescope and click on the box for CS 460.
Click on the appropriate problem in the list of assignments. You should see a pop-up window with a box labeled DRAG & DROP. (If you don’t see it, click the Submit or Resubmit button at the bottom of the page.)
Add your files to the box labeled DRAG & DROP. You can either drag and drop the files from their folder into the box, or you can click on the box itself and browse for the files.
Click the Upload button.
You should see a box saying that your submission was successful.
Click the (x)
button to close that box.
The Autograder will perform some tests. Once it is done, check the results to ensure that the tests were passed. If one or more of the tests did not pass, the name of that test will be in red, and there should be a message describing the failure. Based on those messages, make any necessary changes. Feel free to ask a staff member for help.
Notes:
Passing the preliminary tests does not guarantee that you will ultimately get full credit for the problem. Additional tests will be run later, and you should perform your own testing following the procedures outlined above to ensure that your code works correctly in all cases.
In particular, don’t forget that you can upload your own
input file(s) when you submit your program. We recommend
that you try input files that include instances of special
cases (e.g., users without email addresses or groups). To do
so, you can use one or more of the text files that we have
provided in the data
subfolder. Either use one of those
files in its entirety, or create a new file containing a
subset of lines from those files (edited as needed) so that
you can focus on particular types of cases.
If needed, use the Resubmit button at the bottom of the page to resubmit your work. Important: Every time that you make a submission, you should submit all of the files for that Gradescope assignment, even if some of them have not changed since your last submission.
Near the top of the page, click on the box labeled Code. Then click on the name of each file to view its contents. Check to make sure that the files contain the code that you want us to grade.
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
Last updated on April 24, 2025.