15-440 Assignments

There will be three programming projects and three written homework assignments.

Project 3: Hadoop MapReduce Programming

Updated 11/20: Running your experiments and generating your output on the cluster is now extra credit. As stated in the updated documentation below, we will be grading based on operation in the VM. This means your POPULAR.txt submission need only be run on the edges_small.txt file linked below for full credit.

Project 3 files can be found here:

• Project 3 Documentation
• Small version of Twitter friend relationships.
• Small version of Twitter status messages.
• Cluster Documentation for extra credit

PostID Lookup Webpage

You can use the following webpage to query postids and get the status quickly: http://sn001.datapository.net:8080/twitter

For example, if your inverted index says that #googleOS maps to

1464406884,2529671769

then you can enter that comma-separated list of postIDs in the search box, hit "retrieve post" and it will print out the posts associated with those postIDs in the box underneath. You can use this to test whether your inverted index returns postIDs that contain the appropriate hashtag.

Example bash script for turn in

As stated in the document, your Makefile must properly create the .jar files required to run your Hadoop programs. Your bash script should call the hadoop executable in your VM with the appropriate command line argument options so that we can easily run your programs. Here is an example shell script that takes in two arguments (the input and output directories) and runs the appropriate jar file: twindex.sh. Note the custom name of the Jar file as well as the package name.

Project 2: A Distributed File System

Part 4

• Part 4 Documentation
• Part 4 Code

Part 3

• Part 3 Documentation
• Part 3 Code
• Updated (optional) Part 3 Makefile

Copy the files extracted from the tarball into your existing part 1 and part 2 directory. The tarball only contains an updated Makefile and a tester for your lab 3 implementation.

Part 2

• Part 2 Documentation
• Part 2 Code

Copy the files extracted from the tarball into your existing part 1 directory. This will not overwrite any of your implementation files from part 1, but will update your Makefile.

Part 1

• Part 1 Documentation
• Part 1 Code
• Updated rpctest.cc
• VirtualBox Ubuntu Image with FUSE support (Warning: 1.4GB file)

Updated: Mon Oct 5 18:57:59 EDT 2009: We have provided an update to rpctest.cc. The new version should reduce the time concurrent_test takes when run with RPC_LOSSY=5. It should also help deal with some of the pthread_create failures in concurrent_test and early timeouts in simple_test. We will be using this for grading.

In Project 2, you will be doing your development in a Virtual Machine, and we will be supporting VirtualBox as the virtualization software. Please download VirtualBox for your system here: http://www.virtualbox.org. A brief introduction to VirtualBox for the purposes of this project can be found here: VirtualBox Intro for 15-440.

Project 1: A Simple Distributed Password Cracker

Using a trivially parallelizable, easy computation (brute-force cracking a password), this lab introduces students to the communication and coordination challenges involved in harnessing a cluster or wide-area distributed group of machines to accomplish a common goal.

• Using the provided protocol description, implement the coordinator process and slave processes that run on the worker machines. Your processes must be able to inter-operate with the course-supplied example binaries.
• Implement a reliable work assignment mechanism, operating on top of UDP, that successfully allocates jobs to slave machines, can deal with the loss or delay of UDP packets, and calculates timeouts to reschedule work that was allocated to failed machines.

Project 1 files can be found here:

• Project 1 Documentation (Updated Mon Sep 14 23:02:15 EDT 2009)
• Project 1 Tarball
• Updated Client Tester
• Updated Server Tester
• Updated Server Binary
• Updated server_protocol_tester
• Updated Protocol checker script (adds a sleep call)

Tarball last updated Thu Aug 27 22:19 EDT 2009. Does not contain updated files, please download the links above.

Updated: Wed Sep 16 01:42:19 EDT 2009 We have updated the binaries and the protocol_tester.sh file to be more robust to your client implementations, process scheduling, and port allocation on the shared andrew machines. Please use these versions or else you may experience and/or cause interference with others running on the same Andrew machine.

Updated: Mon Sep 14 23:02:15 EDT 2009 Documentation has been updated to reduce the computational resources required to complete the "Graph" part of the assignment. Please see Section 7 to see the updated requirements for the graph. These tests should only take a total of about 10 minutes to run. Also note the requirement that the server exit after finding the password to properly pass our updated testing scripts.

Updated Mon Sep 14 20:45:18 EDT 2009: We have provided two new ruby scripts for testing to be more robust to different program exit scenarios. Please use the updated ruby scripts. Keep in mind that your server needs to exit after finding the password for the updated scripts to work.

Older Updates:

Documentation has been updated to fix the ASCII ordering (A-Z,a-z,1234567890) to match what order our test code uses. (Updated Tue Sep 8 16:08:17 EDT 2009)

Stage 0 Due Date: Thursday, September 3, by beginning of lecture

Project 1 Due Date: Thursday, September 17, Updated: 11:59pm

Notes on the Programming Projects

A key objective of this course is to provide a significant experience with system programming, where you must write programs that are robust and that must integrate with a large, installed software base. Oftentimes, these programs are the ones that other people will build upon or use as tools. Systems programming is very different from the application program development you have done in earlier courses:

• It is typically done in a low-level language, such as C, to ensure close control over system resources.
• Especially with server code, it must be designed to run indefinitely. It must handle reliably handle every possible error condition, and it must manage resources such as memory with care.
• It must be secure. Connecting a system to a network makes it vulnerable to malicious attacks initiated anywhere in the world. Poorly designed or implemented network software provides a common entrypoint for attack. System software must be invulnerable to flaws such as string overflows or malformed incoming messages. (This point bears repeating: Any system software must stringently check input it receives from the network or from the user. Do not trust either one! They're often out to get you.)
• The interfaces to other parts of the system are generally specified by documented protocols.
• Distributed systems nearly always involve concurrency, both within individual machines (multiple processes or threads) as well as among the different network components.
• An important part of system programming is to develop comprehensive test methods for the programs. A significant effort should be invested in writing programs that will thoroughly test the system code, including the handling of different error conditions.

Finally, please note that by design, the projects do not always specify every corner case bit of behavior or every design decision you may have to make. A major challenge in implementing real systems is in making the leap from a specification that is often slightly incomplete to a real-world implementation. Don't get frustrated -- our grading will not dock you for making reasonable design decisions! We suggest three general guidelines to follow:

• Be conservative in what you do, be liberal in what you accept from others.. This is the design guideline underlying many Internet services, first uttered as a robustness principle by Jon Postel in the first TCP RFC, RFC 793.
• Browse the newsgroup and FAQ, ask the course staff!
• Make a reasonable design decision and document it. In a perfect world, all aspects of a design would be comletely specified, but most real-world, large, complex systems do not achieve this goal. You will often hear the course staff reply: You may pick either alternative as long as your server does not crash. This advice applies particularly to error handling, where there are a nearly infinite number of possible errors with partially-specified error responses. The goal of the course is to gain experience with creating large systems; we don't expect students to be psychic, merely to exercise good judgement about creating a robust and usable system.

We'll go into more detail about each of these points during the recitation sections. But keep in mind: The programming assignments are larger and more open-ended than in other courses. Doing a good job on the project requires more than just producing code that runs: it should have a good overall organization, be well implemented and documented, and be thoroughly tested.

Last updated: Wed Dec 09 22:06:06 -0500 2009 [validate xhtml]