Distributed Algorithms, 6.852

Fall 1999

Lecture: TR 9:30-11  (34-304)

Recent Announcements:

Important: Solution to each HW problem must be handed in on seprate sheet(s). Solutions are due before class on alternating Thursdays. (See Syllabus for the dates.)
FYI: You may want to use spec92.sty and 6.852.sty style files for typesetting your homework solutions in LaTeX. "spec92.sty" is Leslie Lamport's package that defines a spec environment for printing an ASCII specification. The environment is like verbatim, except that \ works as usual, and various abbreviations are defined--for example, [ ] for \Box and => for \Rightarrow. See comments in the file for info on how to use it. "6.852.sty" has some extensions to the spec environment.

Past announcements are moved to  the bottom of this page.


Lecturer:  Prof. Nancy Lynch  lynch@theory.lcs.mit.edu NE43-366. Office Hours: After class and by appointment
TA:  Roger Khazan  roger@theory.lcs.mit.edu  NE43-368. Office Hours: T12-2, W3-5
Secretary:  Joanne Talbot  joanne@theory.lcs.mit.edu NE43-366. Phone: 617 253-6054



Distributed Algorithms, by Prof. Nancy Lynch. (third printing)

Consult  Corrections to the Second Printing of "Distributed Algorithms" if you have the second printing of the book.

Please direct any typos you find or other comments about the book to Prof. Nancy Lynch.

Also, a good general reference for the area of ``Reliable Distributed Computing'' is the book Building Secure and Reliable Network Applications, by Kenneth P. Birman. Manning Publications, 1996.


1. Course Description  Postscript
2. Tentative Course Schedule  Postscript
3. Homework Assignment 1, Part a  Postscript
4. Supplemental Bibliography  Postscript
5. Homework Assignment 1, Part b  Postscript   Report from graders
6. Homework Assignment 2, Part a  Postscript
7. Homework Assignment 2, Part b  Postscript   Report from graders
8. Information about Term Project  Postscript  
9. Homework Assignment 3, Part a  Postscript  
10. Sample Solutions for HW1    in the course cabinet
11. Homework Assignment 3, Part b  Postscript   Report from graders
12. Revised Course Schedule  Postscript  
13. Sample Solutions for HW2  in the course cabinet
14. Homework Assignment 4, Part a Postscript
15. Homework Assignment 4, Part b Postscript Report from graders
16. Sample Solutions for HW3 in the course cabinet
17. Homework Assignment 5, Part a Postscript
18. Homework Assignment 5, Part b Postscript
19. Sample Solutions for HW4 in the course cabinet
20. Homework Assignment 6, Part a Postscript (P1 - Cancelled. P3 - Modified). Due: Dec 2
21. Homework Assignment 6, Part b Postscript (22.11 - Hint: there is an algorithm). Due: Dec 2
22. Sample Solutions for HW5 in the course cabine


Each student must participate in grading problem sets, probably just one, but maybe two depending on the size of the class. If you have not signed up to grade for a certain week, please do so by contacting Roger (roger@theory.lcs.mit.edu). Please check in the sign-up sheet below what weeks are available. We need eight graders for each week.

10/05/99: If all grading slots have been assigned and you did not get one, don't worry, some of the slots are likely to become available as the drop-date approaches.
 HW Grading Period   Graders 
1 Thr. 9/23   - Mon.   9/27   X   X   X   X   X   X   X   X 
2 Thr. 10/7   - Mon. 10/11   X  X  X  X  X  X  X  X
3 Thr. 10/21 - Mon. 10/25  X  X  X  X  X  X  X  X
4 Thr. 11/4   - Mon. 11/8  X  X  X   X   X  X
5 Thr. 11/18 - Mon. 11/22  X  X   X   X  X  X  X  X 
6 Thr. 12/2   - Mon. 12/6  X  X  X  X        

Old Announcements

Important: Handout 8 contains inormation about the term project. Proposal is due Oct 28. 
Important: Students, please subscribe to the course mailing list by sending email to roger@theory.lcs.mit.edu. Please include your name and email address.
Important: Students must participate in grading homework. Please see  information  at the bottom of this page.
Distributed Algorithms

by Prof. Nancy Lynch

(third printing)

Reading for Tuesday, November 9:
  1. "Unreliable failure detectors for reliable distributed systems" by Chandra and Toueg. 
  2. "Fault-Tolerant Broadcasts and Related Problems" by  Vassos Hadzilacos and Sam Toueg.  Chapter 5 of Distributed Systems. ACM Press and Addison-Wesley. Second Edition. 1993. Pages 97-145. Edited by Sape Mullender.  (Available in the course cabinet.) 

Maintained by Roger Khazan.