CS505 : Distributed Systems

Course Information

MW 4:30p-5:45p
LWSN B134

Instructor:
Charles Killian
email: ckillian@cs.purdue.edu
phone: 765-494-6014
office: LWSN 1187
office hours: by appointment

Teaching Assistant:
Karthik Nagaraj [email : knagara at purdue]

Textbook:
We will not be following a textbook in this course, but instead focusing on research papers. Useful reference books may be listed here later.

Announcements

• 2010-03-29: HW3 due today, HW4 posted. Remaining readings were already posted, and the last class day will be April 26th, which will likely run long for holding project presentations. Don't forget your status reports.
• 2010-02-26: HW2 Rubric updated to reflect e-mail announcement on reducing the testing time.
• 2010-02-18: Final project timeline (from class) posted.
• 2010-02-18: Papers for next 2 segments posted.
• 2010-02-08: HW2 posted below. Due 2/26.
• 2010-02-08: Class cancelled today (2/8). Paper responses accepted through Wednesday (in addition to other paper assigned Wednesday).
• 2010-02-02: See announcements from class in lecture slide 1.
• 2010-01-27: The rubric for programming assignment 1 can be found in the assignment page. PA1 should be submitted using BlackBoard, using the assignments section. Due to a planned BlackBoard outage this weekend, the deadline for PA1 will be extended to Monday (2/1).
• 2010-01-25: As discussed in class, Mid-term and final weights decreased. Weights added instead to programming assignments and readings
• 2010-01-20: Slides posted about Mace and MaceMC (see Intro page).
• 2010-01-15: Programming Assignment 1 updated thanks to TA suggestions.
• 2010-01-11: The webpage is created. New content added as available.

Course Description

Developing applications which will run over a set of physically distributed processors is inherently hard, as one has to deal with latency and failures of both processors and communication, as well as with security concerns which arise as soon as a shared media for inter-process communication.

Most industrial-scale applications developed nowadays involve some form of remote interaction. Understanding and mastering the challenges of distributed settings becomes thus of primary importance. This becomes even more valid considering the continuously increasing number of computers connected through the Internet as well as the advent of mobile wireless and sensor networks which continue further the reach of our society's global communication infrastructure.

This course is intended to cover foundations for building reliable distributed systems, including failure and system models, and basic communication and agreement problems; crash failures, recovery, partition, Byzantine failures; asynchronous systems, failure detectors, communication channels, wireless and sensor networks; software clocks, causality, cuts. Examples of problems include consistency, reliable broadcast, consensus, leader election, replication., authentication.

Grades

Tentative and subject to change.

• 17% - Reading assignments and class participation
• 33% - Programming assignments
• 10% - Midterm
• 20% - Final prjoect
• 20% - Final exam

Topics/Schedule

Updated in an ongoing basis

Reading assignments will be listed in individual section pages. For each class period, there will be one or more papers assigned. One of the papers will be marked as the reading assignment due before class. The standard reading assignment response is (1) state the main contribution of the paper, and (2) list 4 points about the paper, 2 in favor of the paper and 2 opposing the paper. The reading response is DUE by class time on the day assigned. Please do not read your fellow students entries prior to submitting your own response.

THEN, within 24 hours AFTER class time, you should respond to two other student's entries. Try to pick entries which have fewer than 2 responses to them.

You may skip responding to 5 papers during the course of the semester without penalty. Skipping either the review or the review responses counts a 1 skip (skipping both on the same paper still counts as 1 skip).

While responding to papers, you may consider these questions:

• Describe the soundness of the methodology. For example: do the experiments support the conclusions? Are the assumptions practical? Are there other experiments which would have been better? Were there other methodological errors?
• What are the strongest/most interesting ideas in the paper?
• What are the biggest weaknesses of the paper?
• What question would you ask the author if seen presented at a conference?

Though the response should primarily be about the paper assigned, feel free to include details from other papers assigned for comparison or general discussion.

• (Weeks 1-2) I. Introduction (1/18: No class MLKJ Day) [1/10 - 1/23]
• (Weeks 3-4) II. Overlay Networks. DHTs. and Multicast [1/24 - 2/6]
• (Weeks 5-6) III. Bulk Data Transfer and CDNs [2/7 - 2/20]
• (Weeks 7-8) IV. Time, Agreement, and Causality (3/3) In-Class Midterm Exam [2/21 - 3/6]
• (Weeks 9-11) V. Consensus (Week 10: Spring Break) [3/7 - 3/27]
• (Weeks 12-13) VI. Storage and Consistency [3/28 - 4/10]
• (Weeks 14-15) VII. Datacenter Middleware [4/11 - 4/24]
• (Week 16) Project Presentations [4/25 - 5/1]

Programming assignments

There will be approximately 7 programming assigments, all using the Mace toolkit. One will correspond with each unit of the class. They will be posted below as they become available. Programming assignments should be done individually. No collaboration. Blackboard may be used as a forum for asking and answering peer questions, as well as the professor and TA.

Some notes on the use of logging within mace are available here [./logging-notes.txt]

Programming Assignment 1: Epidemic/Gossip Multicast

Programming assignment 1 is a getting-to-know-Mace project. This project will be to implement portions of the gossip protocol described in Demers et al. Complete details will be posted here. PA1 will be graded out of a score of 20. The rubric will be posted when available, and will be out of a score of 20. PA1 is due on Monday, February 1st. This assignment should be done individually, though helping fellow students with programming or Mace, (provided there is no sharing of code or text), is acceptable. Assignment questions should be posted to Blackboard for the benefit of all.

Programming Assignment 2: Chord-like Ring

Programming assignment 2 is to implement portions of the chord protocol described in Stoica et al. Complete details are posted here. PA2 will be graded out of a score of 30. The rubric will be posted when available, and will be out of a score of 30. PA2 is due on Friday, February 26th. This assignment should be done individually, though helping fellow students with programming or Mace, (provided there is no sharing of code or text), is acceptable. Assignment questions should be posted to Blackboard for the benefit of all.

Programming Assignment 3: Byzantine Agreement

Programming assignment 3 is to debug portions of a BFT protocol implementation described in Lamport's Byzantine Generals paper and detailed in the blog post linked from the assignment. Complete details are posted here. PA3 will be graded out of a score of 20. PA3 is due in ONE WEEK, on Monday, March 29th. This assignment should be done individually, though helping fellow students with programming or Mace, (provided there is no sharing of code or text), is acceptable. Assignment questions should be posted to Blackboard for the benefit of all.

Programming Assignment 4: 3 Phase Commit

Programming assignment 4 is to implement portions of a 3PC protocol. Complete details are posted here. PA4 will be graded out of a score of 20. PA4 is due in two weeks, on Monday, April 12th. This assignment should be done individually, though helping fellow students with programming or Mace, (provided there is no sharing of code or text), is acceptable. Assignment questions should be posted to Blackboard for the benefit of all.

Final project

Many intersting and exciting topics cannot be covered in this semester course, and those we cover will not be covered in as much depth as possible. The course project is your opportunity to explore a topic in greater depth, gaining first-hand experience with implementing and evaluating a distributed system.

For the final project you may choose to collaborate with others, but each of you should submit a separate project. (i.e. 2 people working together should submit 2 projects - on two separate systems.) Each person should be the primary collaborator on one project.

It is expected that you will use Mace to implement your final project. If there is a particularly compelling reason why you should not use Mace for your project, you should consult with the professor.

For this final project, you will be submitting an implementation of your distributed system, and a 5-10 page paper. The paper should discuss your implementation and its limitations, any extensions or improvements you have made to the system, and describe the details of the implementation which were not fully described in the publication of the system. The paper should also include an evaluation which shows a validation of the implementation with respect to the results put forth in the publication.

Generally, the system you will implement should have been published in a top-tier systems conference. Follow this link for a list of suggested projects (in progress).

Project Timeline:

• (3/1): Pick a few papers, and discuss the project with the professor. The goal is to talk about scope, ideas, etc.
• (3/5): Submit a project proposal to the BlackBoard discussion forum. Indicate the paper you are working on, teammates you plan to work with, and what you hope to be able to implement and test in the time remaining.
• (at least every 2 weeks -- 3/19, 4/2, 4/16): Reply to your project thread in BlackBoard with a status report. This will also be a good place to have discussions about approaches, etc., which could include non-team members.
• (4/26): Project presentations and paper deadline. [Extensions may be requested up to 4/30 on the paper, but not the presentation.]

Course Mailing-lists

In this course we will be using a ITAP maintained announcement list. This list will be used both for announcements only. Discussions related to the course, and questions about assignments, may be posted to the relevant topics in BlackBoard.

Pre-requisites

1. This course should both equip you with the basic concepts and principles underlying the field of distributed systems and give you first hand experience with the challenges of building distributed systems. In this course, we will be using the Mace platform to simplify this building and understanding. It is NOT expected that you will know how to use Mace before beginning this course, but necessary to being able to pick up Mace is the ability to program in C/C++. Therefore, if you are unfamiliar with C/C++, please take the appropriate undergraduate programming courses before you register for this course. This is a strong requirement and no exceptions will be made at all.
2. CS 354 (Under graduate operating systems) or  CS 422 (undergraduate networks) or equivalent courses. If in doubt, please see me before you register. These courses are not required but no exposure to any of these courses would make it really hard for you to follow the course.
3. Speaking in English. Written and spoken English is essential since most exams will be in English (US or UK should be fine, i.e., you can spell color as color or colour and not be afraid of getting penalized).

Course Policies

(subject to change)

This is a new course with new assignments. While the professor intends that the assignments will be given adequate time for completion, sometimes exceptions will be made or extensions given if it appears the assignment was more complex that originally intended. However, do not expect to receive extensions, as they will be granted at professor's discretion. If you find that your assignment is taking longer than expected, contact the professor early to discuss options. Failure to plan ahead is not an excuse.

Additionally, students may use a total of 7 days (metered in half-days) during the course of the semester to turn in late programming assignments without penalty. Beyond that time, there will be a 10% penalty per half-day late. NO SUBMISSION MAY BE SUBMITTED MORE THAN 6 DAYS LATE, EVEN USING "FREE" TIME.

Reading assignments submitted late will not be counted. However, you may skip responding to 5 of the papers, though you will still be responsible for understanding the content.

Emergencies: In the event of a major campus emergency, course requirements, deadlines and grading percentages are subject to changes that may be necessitated by a revised semester calendar or other circumstances. Here are ways to get information about changes in this course. The course web page, the class mailing list, or by contacting the professors directly.

General policies: This course further adheres to the policies posted at http://spaf.cerias.purdue.edu/cpolicy.html. Please familiarize yourself with them.

Special note on academic dishonesty: In particular, note the section on academic honesty. Violations of this policy are treated as very significant, and will be dealt with both through punitive grading and notification to the Dean of Students.