Administrative Information

Professor

T.A.

Course Description

Distributed systems consists of a collection of independent computers that appears to its users as a single coherent system. While their early development followed the emergence of high-speed local area computer networks at the beginning of 1970s, the recent availability of powerful and cheap microprocessors and pervasive connectivity has brought the topic to everyone's attention.
In this course we will discuss some of the basic principles behind distributed systems and review some of the main paradigms used to organized them.

Throughout the quarter, you will also design, build and evaluate an interesting distributed system that addresses issues, solves problems and exploits techniques from classroom discussions and readings. Based on this project, you will write a high-quality paper with which you will go through a peer-review process similar to what you would experience if submitting it to one of the major systems conferences.

The course follows a mixed lecture-style/seminar model for class instruction, with the students and the instructor sharing some of the teaching load. Every new topic is started with an introduction of the basic problems/ideas/solutions, followed by student presentations of seminal work and current research in the topic. Although there are no homework assignments, you will be responsible for reading the material before coming to class (to ensure lively discussion) and for submitting a one-page summary of the papers covered. In addition, there will be only one exam - a take-home final given in the last week of class.

Location and Time

Tuesdays and Thursdays - 2:00-3:20OM, place TBD.

In compliance with Section 504 of the 1973 Rehabilitation Act and the Americans with Disabilities Act, Northwestern University is committed to providing equal access to all programming. Students with disabilities seeking accommodations are encouraged to contact the office of Services for Students with Disabilities (SSD) at +1 847 467-5530 or ssd@northwestern.edu. SSD is located in the basement of Scott Hall. Additionally, I am available to discuss disability-related needs during office hours or by appointment.

Course Prerequisites

• CS-343 Operating Systems.
• CS-340 Introduction to Networking.

Communication Channels

There will be a number of communication channels set up for this class:

• We will use the course web site (http://www.cs.northwestern.edu/~fabianb/classes/cs-345-w05) to post announcements related to the course. You should check this regularly for schedule changes, clarifications and corrections to assignments, and other course-related announcements.
• There will be a newsgroup (cs.345 at news.cs.northwestern.edu) to foster communication outside the classroom.
• There will be an email alias ( cs-345-ta@cs) for the staff that you should use for questions that would be inappropriate to post on the newsgroup/discussion-board.

Announcements

Remember to check this regularly!

• Slides from the first class have been posted.

Materials

Required

• Andrew S. Tanenbaum and Maarten van Steen. Distributed Systems: Principles and Paradigms. Prentice Hall, 2002 ("DSP2" from now on).
• Research papers - You can see the list in the class schedule.

Course Organization

• In-class presentations - Instructor and students' presentations based on textbook and research papers.
• Project - A major project that addresses issues, solve problems and exploit techniques from classroom discussions and readings.
• Exam - A take-home, final given in the last week of class.

Paper Presentation

We will start each new section with an introduction of the basic problems/ideas/solutions (first lecture), followed by students presentations of seminal work and current research in the topic. To ensure lively discussions, you will be responsible for reading and preparing a short (typed) summary of one or two papers before each class. The summaries will be due by 11:59PM of the previous day so that the staff has time to read them and bring your comments into next class' discussion.

Each lecture will consist of a formal presentation, and is expected to go into considerable depth by focusing on some aspect of the material and treating it thoroughly. We'll be using slides that will be made available on the course site. A presentation will normally last between 30 and 40 minutes (presenters are required to meet with either me or the TA before class in order to discuss the slides). The lecture period will be followed by a broader discussion that myself or the TA will lead. During the discussion following each presentation, we'll try to understand the broader context and importance of each result. All students in the class are expected to participate.

Reading Papers

When reading papers it is normally useful to write down a summary of about a page. Your summary should include at least:

1. Paper title and its author(s).
2. Brief one-line summary.
3. A paragraph of the most important ideas: perhaps a combination of their motivations, observations, interesting parts of the design, or clever parts of their implementation.
4. A paragraph of the largest flaws; maybe an experiment was poorly designed or the main idea had a narrow scope or applicability. Being able to assess weaknesses as well as strengths is an important skill for this course and beyond.
5. A last paragraph where you state the relevance of the ideas today, potential future research suggested by the article, etc.

You may find the following brochure useful: Efficient reading of papers in Science and Technology by Michael J. Hanson, 1990, revised 2000 Dylan McNamee.

Projects

Projects are a critical component of this course. Your goal is to design, build and evaluate interesting systems that address issues, solve problems and exploit techniques from classroom discussions and readings.

We will save the last part of our Thursdays' lectures to talk about your projects (brainstorming, reporting progress, discussing problems you have found, etc.).

You will write a high-quality paper on your project. The paper has to conform to the format and submission rules used by the Workshop on Hot Topics in Operating Systems. For tips on preparing the paper, refer to Levin & Redell, An evaluation of the ninth SOSP submissions -or- How (and how not) to write a good systems paper.
The paper will be done in four steps:

• First you must choose an area based on your interest and background reading, such as naming or multicast. Email your choice to us (cs-345-ta) by Jan. 11, 2005..
• Follow this with a literature survey, and write a short survey paper (2-3 pages) describing the literature in the field. This survey is due Jan. 25, 2005.
• You must then choose the topic of your paper, and discuss this with me before Feb. 1, 2005. Ideas will be suggested by the staff, but you are encourage to come up with your own.
• In the third stage, write a full paper on your topic. This is paper due Feb. 25, 2005.
• Reviews will be due back on Mar. 5, 2005 (Friday before presentations start)
• Final paper is due Mar. 14, 2005

Papers will be review by 2-3 people, including one or two of your classmates (assigned by the instructor) and someone from the staff.

General Advice

• John Wilkes, CSP project startup documents, (HPL-CSP-90-42), 11 Oct. 1990 - A great guideline for project proposals.
• Roy Levin and David D. Redell, An evaluation of the ninth SOSP submissions -or- How (and how not) to write a good systems paper, ACM SIGOPS Operating Systems Review 17(3):35-40 (Jul., 1983)
• George D. Gopen and Judith A. Swan,The Science of Scientific Writing,American Scientist (Nov-Dec 1990), 78: 550-558.

Exams

There will be a take-home, final given in the last week of class.

Grading

• Paper summaries: 15%
• Class participation: 15% (I'll keep track of this)
• Project: 40%, made up of ...
  
  
• Survey paper: 5%
• Project presentation: 10%
• Final paper: 25%
• Final, take-home, exam: 30%

Class Outline

• Introduction: Defining distributed systems and their goals, hardware and software concepts, the client-server model and architecture, modern architectures for distributed systems.
• Wide-area dsitributed systems and PlanetLab: Issues with wide-area distributed systems and brief introduction to PlanetLab.
• Communication: Basics of communication, remote procedure calls, remote object invocation, message-oriented and stream-oriented communication.
• Processes: Clients, servers, code migration and software agents.
• Naming: Naming and locating entities, removing unreferenced entities.
• Synchronization: Synchronization in distributed systems, logical time, global state, elections and mutual exclusion.
• Consistency and replication: Data replication, scalability, and consistency
• Fault tolerance: Making distributed systems fault tolerant, reliable and resilient multicasting.
• Security: Secure communication and authorization in distributed systems.
• Review of major distributed systems paradigms: Distributed object systems (Corba, Globe, ...), Distributed file systems (Plan 9, XFS, SFS, ...), Distributed document-based systems, and Distributed coordination-based systems.