CS262: Introduction to Distributed Computing        

Spring, 2008

MD G135               M, W 4:00 – 5:30

 

Instructors:

Jim Waldo (waldo@eecs.harvard.edu or jim.waldo@sun.com)

MD 339

M 2:30-3:30, W 2-3:30 or by appointment

 

Ian Rose (ianrose@eecs.harvard.edu)

By appointment, or just find him

 

Readings:

All readings for the course are available electronically from the course website. Links are available in the schedule below. The schedule indicates the time that the readings are to be done, not when they are assigned.

 

Grading:

Grades will be determined by a combination of one-hour exams (short and long essay), short (1-2 page) papers, programming assignments, class participation, and a final project. The weight of these will be

               Exams: 30%

               Final Project : 30%

               Short Papers : 15%

               Programming Assignments : 20%

               Class Participation: 5%

Short papers will be assigned about once a week. They will be concerned with the reading, and will be no more that two pages in length. Short papers will need to be submitted to the instructor prior to the class covering the corresponding reading.

 

Programming assignments will be assigned during the first half of the term. There will be a set of machines that can be used for those assignments; you will need to be signed up for the course to get access to those machines.

 

The final project will be student-defined, but will need to be cleared with the instructor. This project should be a substantial design and implementation of a distributed system that shows a solution to a well-defined problem. Proposals for a final project will be due shortly after spring break. Final projects will require a written paper and a (short) class presentation. Projects can be done by small groups (no more than three collaborators).

 

Make-up Exams

 

On May 12, from 2 to 5 p.m. in MD G135 (the regular meeting room) you can re-take either or both exams. The exams will cover the same material as those given during the term, but may ask different questions. The grade that will count towards your final grade will be the higher of the two scores, so there is no penalty in taking a second shot at the exam (other than the pain of taking a second exam).

 

Final Projects

 

Final projects will be graded based on three components—a proposal, a short class presentation, and a paper. The project may be done in a group; all members of the group will receive the same grade for all parts of the project. Final project papers must be submitted (electronically, in .pdf format if at all possible) to Jim Waldo no later than 11:59 p.m. Friday, May 16, 2008.

 

Lecture Slides

 

In general, you should not expect to be able to miss class and make it up by looking at the slides for the class. This is because there will often not be any such slides (I prefer to use the blackboard) or because when I do use slides, they often donÕt contain all of the information that was presented in class (and for which you will be held accountable).

 

That said, when there are slides, they will be posted (within a day or two) here.

 

Shopping Lecture

 

Vocabulary, failures models, and other problems

 

Replication

 

Global State and Logical Clocks

 

All About Broadcasts...

 

Paxos

 

Logic of Authentication

 

Schedule

 

Topics for each class, and the readings for that class, can be found here.

 

Some useful stuff

 

Tests

Here is a midterm I gave in this class last time around. Some of the questions concern material that we are not covering this time around, but some will seem familiar. Even better, here is the set of answers I would have given for that test.

 

Tests are open-book, open-note, open-nearly anything. The only aids you cannot use are those that are 1) alive or 2) electronic. ItÕs fine to bring in copies of the reading, and your notes, and print-outs of previous exams and their answers that you have found on the web. It is not fine to work in a team or use a network.

 

Assignments

 

Paper Assignments:

 

Note that all papers are to be no more than 2 pages in length, and must be sent electronically to the instructor (jim.waldo@sun.com or waldo@eecs.harvard.edu) by the due date and time.

 

Paper assignment 1: Explain the communication requirements of the state machine approach to replication, including why fulfilling those requirements is sufficient to insure that all replicas are identical. Papers are due by 12 noon (eastern) Sunday, 2/10/08.

 

For those wondering what IÕm looking for in these papers, here is an example of a very good paper.

 

Paper assignment 2: What is gap detection, and why canÕt it be done using logical clocks? Papers are due by 12 midnight (eastern) Sunday, 2/24/08 (in response to multiple protests, I have changed the due time to better reflect the standard student schedule).

 

Paper Assignment 3: What are vector clocks, what sort of gap detection can they do, and how can they do it? Papers are due by 11:59 p.m. Sunday, 3/2/08.

 

Paper Assignment 4: Describe how faulty processes can contaminate correct processes. Papers are due by 11:59 p.m. Sunday, 3/9/08. (This is a simple paper to make up for the length of the reading; one page will probably be sufficient.)

 

Paper Assignment 5: What is the notion of a majority as used in the Paxos algorithm? Explain how this notion is used in the algorithm, and why an implementation might choose to use a notion of a majority which is different from Ōmore than half of the participantsĶ. The paper is due at 11:59 p.m. Sunday, March 30 (welcome back).

 

Paper Assignment 6: Back when we were first introduced to Byzantine failure (in Replication Management using the State Machine Approach) the claim was made that in a system with Byzantine failure, it required 2t+1 machines to be t-fault tolerant. But Lamport says that it requires 3t+1 machines for t-fault tolerance. Explain the claim of each, and why we suddenly need t more machines. The paper is due Sunday, April 6 at 11:59 p.m. EDT.

 

Programming Assignments:

 

Programming Assignment 0: The class will be making use of the servers cs262-{0,1,2,3} for programming assignments. Determine your primary server using the following algorithm—your primary server is cs262-n, where n = your student ID number modulo 4. Your assignment is to log into your primary server, and send me (Jim Waldo) the output of the command

 

               java –version

 

This should be done by Friday, February 15, at 5 p.m. To do this will require that you send your EECS (not FAS) unix login name to ianrose@eecs.harvard.edu. If you donÕt have such a unix login, you should obtain one from the EECS IT department, located on the first floor of Maxwell-Dworkin by the snack machines.

 

Programming Assignment 1 Note: The last day for completing Programming assignment 1 is April 15, 2008.

 

Programming Assignment 2 Note: The last day for completing Programming Assignment 2 is April 20, 2008.

 

Programming Assignment 3 Note: The last day for completing Programming Assignment 3 is May 9, 2008.

 

Schedule for Final Project Presentations

Day 1 (4/28)

Time

Zak Stone

4:00

Bryan Kate

4:15

William Cheng and Thomas Carriero

4:30

Matt Tierney

4:45

Lamont James, Kristen

Lovin, Stefan Wernli

5:00

Nicholas Hoff

5:15

Michael Moore

5:30

Day 2 (4/30)

Time

Jean Yang, Stephen Chang, John Lai, Peter Zhivkov

4:00

Josh Kroll

4:15

C.K. Lin and C.Y. Su

4:30

Atanu Roy Chowdury and Jason Waterman

4:45

Patrick Ohiomoba

5:00

Chris Jeris

5:15