B649
Topics in Distributed Systems

Instructor

Hours

Office Hours: Tuesday & Thursday, 3:45 PM - 4:45 PM, or by appointment, or by chance. Lindley Hall 201D.

Course Description

Textbooks

• George Coulouris, Jean Dollimore, and Tim Kindberg. Distributed Systems: Concepts and Design, 2nd edition. Addison Wesley, 1995.

Optional secondary references are:

• Sape Mullender, editor. Distributed Systems, 2nd edition. Addison-Wesley, 1993.
• Kenneth P. Birman. Building Secure and Reliable Network Applications. Prentice Hall, 1996.

These books will be supplemented with articles as needed.

Tentative Syllabus

Chapters 3-5 discuss the basics of networks and interprocess communication. P536 and B538 together cover most of that material, so I will discuss it only briefly. If you are not already familiar with that material, don't despair: just start reading those chapters on your own. Of course, you should feel free to ask questions on those chapters or any other topic at any point during the course.

Project

A list of suggestions for possible projects will be distributed in early March. If you have ideas (even vague ideas) for a project earlier in the semester, please come discuss them with me.

A proposal describing your proposed project is due on Monday, March 10. Each proposal should specify the name(s) of the student(s) on the team. During the week of March 10, I will meet with each team, to discuss its proposal.

The project is due on Saturday, May 3.

Grading

Grading Statistics

Week of May 5

Solutions to Final Exam: LaTeX, compressed PostScript.

Week of April 28

Final Exam: A few Practice Problems for Final Exam are available. The final exam will be longer and cover more topics than these practice problems. Nevertheless, these problems can be a useful part of your preparations for the exam. Solutions to these problems will not be distributed. When you have tried your best, if you are unsure of whether some of your answers are correct, you are welcome to ask each other, or ask me.

Lecture is cancelled for Tue, April 29, since I will be out of town.

Week of April 21

Homework: Homework 7 is due on Thu, May 1.

Project: The last round of project meetings will be held May 4-8 (instead of the week of April 28), so I will have an opportunity to read the report describing your project before the last meeting. If this schedule change inconveniences anyone, please let me as soon as possible, and we will make alternative arrangements.

Final Exam: 5PM-7PM on Thursday, May 8, in the usual place. The final exam covers the entire course, though it does not contain questions specifically about name services, leader election, or the gossip architecture. During the exam, you may use only your notes, the required and optional textbooks, and handouts distributed during lecture or available via the course web page.

Grading: The tentative weights listed at the beginning of the semester have been finalized, with a small amount shifted from the project to the final exam (see above table).

Week of April 14

Week of April 7

Week of March 31

Reading: Recovery for atomic transactions is covered in Sections 15.1-15.2 of CDK and in the tech report by Babaoglu and Toueg (see link below).

Project: This is a reminder of what is expected for the project meetings this week. For non-implementation projects, you should be prepared to summarize 2 to 4 (depending on their length) papers that you have carefully read. Bring copies of those papers to the meeting! Also, bring copies (or at least names) of the papers you plan to read next (i.e., during the following 2 weeks). For implementation projects, you should be prepared to describe the design and functionality of your proposed system and the initial steps of the implementation. Also, be prepared to describe the next step in your implementation effort (i.e., what will be accomplished during the following two weeks).

Week of March 24

Erratum: There was a minor flaw in the description of the recovery protocol in lecture on Mar 27. I said that a participant records <VOTE, v> in its log (on stable storage) when it sends <VOTE, v> to the coordinator. I should have added that the coordinator records <VOTE, v> in its log at some appropriate point, e.g., immediately before or after sending the VOTE_REQ messages.

Questionaire: If you did not fill out the Mid-course Questionnaire in class on Mar 27, I would appreciate it if you would print it, fill it out, and put it in my mailbox.

Reading: Chapter 12, as an introduction to transactions. Sections 14.1-14.3 on atomic commitment, including Sections 15.1-15.2 on recovery. The presentation of atomic commitment in lecture is based on Understanding Non-Blocking Atomic Commitment, by Babaoglu and Toueg. That work is also described in Chapter 6 of Mullender, though in abbreviated form (specifically, Chapter 6 of Mullender lacks the discussion of recovery).

Week of March 17

Week of March 10

Week of March 3

Reading: Chapter 11 of CDK, covering group communication and gossip.

Project: Here is a more specific suggestion for a group-communication implementation project: implement and measure performance of a variant of the broadcast protocol used in Amoeba, in which (when r>0) instead of the sequencer receiving ack's and broadcasting accept for each message, other processes take turns doing this. This helps prevent the sequencer from being a bottleneck (cf. page 34 of the paper we discussed on Tuesday).

Project: Here is a more specific suggestion for a security-related implementation project: read and evaluate the papers on partially-authenticated protocols for distributed agreement by Malte Borcherding. Estimate the performance for varying degrees of authentication. Implement the protocols and measure the performance.

Project: Here is a handout with details about the course project.

Reading: Efficient Reliable Group Communication for Distributed Systems, by M. Frans Kaashoek and Andrew S. Tanenbaum. This paper describes the protocols used in the group communication system of Amoeba, a distributed OS (see Section 18.5 of CDK for an overview of Amoeba).

Week of February 24

Homework: Homework 5 is due on Friday, Mar 7. Note: Problem 4 was revised at 13:37 on Feb 27.

Handout: The handout distributed in lecture on Feb 25 (entitled bully-alg-PFD Tue Feb 25 14:07:28) contains errors. A revised version is now available (ASCII, PostScript). I apologize for the confusion (in the handout and the lecture).

Homework: Brief Solutions to Homework 4.

Homework: To save ink, I no longer repeat the homework policy at the top of each assignment, but it hasn't changed: You are free to discuss homework assignments with everyone, but you must write and submit your own work.

Week of February 17

Reading: "Elections in a Distributed Computing System", by Hector Garcia-Molina. This was distributed in class on Feb 18.

Week of February 10

Homework: Homework 4 is due on Friday, Feb 21.

Reading: Chapter 4 of Mullender contains (almost) all of the material that will be discussed this week, so if you decided to purchase Mullender, I suggest reading it. Chapter 10 of CDK discusses a small part of the material; a significant fraction of the rest is discussed in CDK's draft material on System Models.

Week of February 3

Homework: Solution to Homework 1. There were "typos" in the definitions of initialize and run_handler. They were fixed at 5:30PM on Feb 4. If you printed the solution before that, please re-print it.

Homework: Homework 3 is due on Thursday, Feb 13. Homework 3 was revised on Sunday, Feb 2, at 12:23PM. If you printed it before that, please re-print it.

Reading: Chapter 8 of CDK, or Chapter 14 of the book edited by Mullender. You might find Chapter 7 of CDK helpful as an introduction.

Reminders: Homework 1 is due on Monday, Feb 3. Homework 2 is due on Friday, Feb 7.

Week of January 27

Reading: Chapter 9; Section 6.3. I recommend that you read Section 6.3, although (or because!) I won't talk about it in class. The other sections in Chapter 6 are either fluffy or irrelevant to the other topics in this course.

Clarification for Homework 2: There is no distinction between client processes and server processes; in other words, each process can act as both a client and a server. Thus, for every process, initialize is called at start-up, and threads in the process can call sendreq at any time.

Homework: Homework 2 is due on Friday, Feb 7.

Homework: Homework 1 is due on Monday, Feb 3.

Week of January 20

Reading: Chapters 1 and 2. (Recall that Chapter 3 was assigned reading last week.)

A tentative syllabus, info on grading, and more info on projects have been added above.

Week of January 13

I will be out of town this week, so the first lecture will be on Jan 21.