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.
Vocabulary, failures models, and other problems
Global State and Logical Clocks
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 |
|
|
|