CS 670: Special Topics in Architecture/Systems {Distributed Systems}


Instructor: Lecture Coordinates:

Shrideep Pallickara

Office: Room 346, CS Building

Office Hours: 3:15-5:00 pm Thursday

E-mail: shrideep {aT}
          (with the obvious change)

Tel:     970.492.4209



2:00-3:15 pm (TTh)

Computer Science Bldg Room 425




Critical Review of Papers

We will be doing a critical review of 7 papers as part of this course. Based on your course load, you can choose the 7 papers for which you do your critical review. This critical review will be 1-2 pages long. Specifically, this review should answer the following questions.

  • The objective is NOT to defend the paper
       Poke and probe this paper to see if things fall apart

  • DO NOT just take thesis sentences from the paper. Construct your own arguments.

  • What is this paper about?

  • What problem does it solve, and why  is this  important?

  • What are the possible inefficiencies in this approach
       How can we address these inefficiencies, and are there any trade-offs involved?
       Construct situations that cause things to break

  • What are the possible extensions to this work?

  • It is OK to come in from left-field and propose significant changes.

Critical Review Submissions:

The critical review must include your name and should be submitted via e-mail as a PDF document.

The file naming convention is: CR<review-number>_<FirstnameLastname>_<AbbrevOfPaperTitle>.pdf

       e.g. CR1_JohnSmith_GFS.pdf or CR2_JohnSmith_Dynamo.pdf


Assignment Instructions:

Please submit only the source files for your assignment, along with a README.txt file that describes library dependencies. The zipped file should be submitted via e-mail by the deadline for the assignment.


It is expected that you develop all your software from scratch. Modifications or extensions of any third-party code (unless expressly specified for the assignment) is disallowed. You are allowed to discuss assignments with your peers at a conceptual level; however, you may not discuss implementation specific issues.

The file naming convention is: HW<assignment-number>_<FirstnameLastname>.zip



Late Submission Policy:

Barring extenuating circumstances NO extensions will be given for either the assignments or critical reviews.



Assignment 1: Developing a Chat Server (which will be part of a interconnected network)

In this assignment the focus is to build a chat server that can support multiple forums. Users can (de)register to multiple forums. The chat server should support clients developed by your classmates. It should be possible to create a network of the chat servers that each of you have developed, and use these chat servers to relay messages across the federated chat server network. The wire formats for these messages are described in detail here.

Due on Sep 22nd: This assignment will be tested in class. All of you will be required to startup your chat-servers and your client. Chat server will be inter-connected based on the topology specified in class: each Chat Server will be connected to at least 4 other Chat Servers. Next, clients will generate messages to chat forums with a specific time-to-live (TTL). Messages should be duplicate-detected based on the traces, and discarded when the TTL reduces to 0. The routing (and discarding of messages) combined with the traces in the messages will determine scoring.


Critical Review 1:
Due on Sep 22nd: Paper to be reviewed is the "The Google File System"
Critical Review 2:
Due on Sep 24th @11:59 am: Paper to be reviewed is "Dynamo: Amazon's Highly Available Key-value Store."
Critical Review 3:
Due on Sep 29th @11:59 am: Paper to be reviewed is "Big Table"

Critical Review 4:
Due on Oct 8th @11:59 am: Critical review contrasting "
Mapreduce: Simplified Data Processing on Large Clusters" and "Dryad: Distributed Data-Parallel Programs from Sequential Building Blocks".
Critical Review 5:
Due on Oct 15th @11:59 am: Paper to be reviewed is "Xen and the Art of Virtualization".


Assignment 2: Building a distributed, replicated and fault-tolerant file system
Due on October 20th @ 2:00 pm: As part of this assignment we will be building a distributed file system (very similar to the Google File System) from commodity desktops. A given file will be split into chunks that will be distributed across a set of commodity desktops. During the creation of a file, it should be possible to specify a specific redundancy level. The file system needs to respond to node failures by making sure that a certain number of replicas for a chunk continues to be available. The design needs to incorporate support for random writes/deletes to these files in addition to appends. Include data on whether any of your chunks have gaps in them, and are thus not byte-wise identical with other chunk replicas. Details about this assignment are available here.


Other instructions:

1. Each assignment will need to work with at least 10 chunk servers. The number of machines N for the test will be specified during the scoring.

2. You can use a third-party library for the cryptographic checksum for chunk slices.

3. All other software will be developed by you from scratch.

4. Scoring for the assignment will be done based on a one-on-one interview/demonstration of all the features outlined in the assignment. You will be asked to a code walk-through of specific sections of your code.



Critical Review 6:
Due on Oct 22nd  @11:59 am: Paper to be reviewed is BOINC: A System for Public-Resource Computing and Storage and BOINC: Designing a Runtime System for Volunteer Computing

Critical Review 7:
Due on Oct 29th  @11:59 am: Paper to be reviewed is The Chubby lock service for loosely-coupled distributed systems

Critical Review 8:
Due on Nov 3rd  @11:59 am: Paper to be reviewed is The Eucalyptus Open-source Cloud-computing System

Critical Review 9:
Due on Nov 10th  @11:59 am: Paper to be reviewed is An Inside Look at Botnets and
Understanding the Network-Level Behavior of Spammers


Assignment 3: Splicing a physical machine into virtual machines, and building a private cloud to launch a cryptographic attack to retrieve the secret AES key

Due on Nov 12th @2:00 pm: As part of this assignment we will be splicing a physical machine's capabilities (CPU, main memory, hard disk and networking) to create multiple virtual machines. One (or more) of the virtual machines that are created will be part of a private cloud that would be used to run distributed programs. You will be asked to reason about apportioning the available execution pipelines on a CPU. Is there a difference in the performance of virtual machines that have a hardware-assist from the CPU?


As part of this assignment you will be launching a cryptographic attack to retrieve a secret key. Each of you will be given a plain-text, encrypted-text and a cryptographic key search space. You will use this information to launch the attack and retrieve the key. The solution to the assignment is submitting the complete AES cryptographic key. You will run your program on a machine with only one OS, and one with 5 concurrent OS running under Xen. Your report should reason about the differences you see in performance. Also, estimate the number of machines that you will need to launch an unassisted cryptographic attack; for the purposes of your calculation assume that your machine will have 1024 cores, with 4 execution pipelines per core. Details about this assignment are available here.


Critical Review 10:
Due on Nov 17, 2009 @11:59am: Paper to be reviewed is
Optimizing Network Virtualization in Xen.

Critical Review 11:
Due on Nov 19, 2009 @11:59am: Paper to be reviewed is Terra: A Virtual Machine-Based Platform for Trusted Computing.

Critical Review 12:
Due on Dec 1, 2009 @11:59am: Paper to be reviewed is Building a Database on S3.

Critical Review 13:
Due on Dec 3, 2009 @11:59am: Paper to be reviewed is Deploying a High Throughput Computing Cluster.

Critical Review 14:
Due on Dec 8, 2009 @11:59am: Paper to be reviewed is Data Management in the Cloud: Limitations and Opportunities.

Critical Review 15:
Due on Dec 10, 2009 @11:59am: Paper to be reviewed is SQL in the Clouds.

Final Project: Implementing Google's Page Rank Algorithm
Due on Dec 11th @2:00pm
Details about this assignment are available here.






Department of Computer Science, Colorado State University,

Fort Collins, CO 80523 USA

2009 Colorado State University