Stanford
Stanford University
Computer Science 244b: Spring 2008

Distributed Systems

Announcements | Overview | Details | Materials | Assignments | Exams | Policies

Details

Lectures:
Tuesday and Thursday, 4:15PM-5:30PM, Skilling 191, also on Stanford Online on channel E1
Instructor:
David Cheriton
Office hours: Tues/Thurs 1:30 to 2:30 pm (or send an email to schedule an appointment)
Teaching assistant:
Bob Lantz
Prerequisites:
Knowledge of C, and C++, and basic programming methodology as developed in cs106b or cs106x, and networking and sockets knowledge at the level of cs244A and ideally, CS249.
Units:
3
Newsgroup:
We will (unfortunately) be using coursework for discussions and possibly other communication. Please login to Coursework.stanford.edu and make sure "Sp08-CS-244B-01" is one of your tabs in that system. We will be update the course schedule there. We will be answering questions through the discussion group in coursework (The link on the left hand side in coursework).

Announcements

May 16: Project 2 (replFs) question session: Friday May 16th, 3:15pm-4:05pm, Gates B03 (slides)
May 9: Project 2 (replFs) intro session: Friday May 9th, 3:15pm-4:05pm, Gates B03 (slides)
April 4: Project 1 info session: Friday April 4th, 3:15pm-4:05pm, Gates B03

Overview

Many systems and applications beyond a relatively modest scale end up being distributed for a variety of reasons, including fault-tolerance, performance, security and the geographical nature of the requirements. Although the common case of a distributed system is separate computers interconnected by the Internet or some networking technology, many of the challenges and solutions come into play as soon as the application consists of two or more processes that do not share a common address space.

This course explores the issues to address in designing and implementing distributed systems with a particular emphasis on how to deal with the shared state between separate processes within such a system. Topics include: distributed shared memory, object-oriented structuring of distributed systems, real/logical/virtual time, directories and naming, distributed file systems, authentication and security, distributed process scheduling, presentation protocols and communication support for distributed systems. The material complements network-layer courses by building on the transport layer to provide higher-level applications and services.

Materials

Lectures

Most lectures are based on notes by the instructor, typically one chapter per 2 lectures. The chapter for the next week will be posted on-line in postscript and pdf by Sunday night of the week of the lectures, if not before.

There is expected to be several guest lectures that depart from this pattern and will be noted as they arise.

Research Papers

As augmentation to this material, there may be one or two research papers that are listed as readings at the end of each chapter and/or listed together with the chapter material that you are also responsible for.

The chapters also list research papers as references, meaning they are optional reading and not required in any way to so well in the course. Students should be able to access these papers online using Stanford's site license for the ACM digital library from any computer with a Stanford IP address. If you have difficulties accessing the papers online, please contact the TA.

Textbooks?

There is no text that really corresponds to the material and focus of this course. However, if you really want a textbook treatment, you can refer to: Distributed Systems: Concepts and Design by George Coulouris, Jean Dollimore, and Tim Kindberg, Addison Wesley, August 2000 (3rd edition).

Lectures

  1. Overview [ps, pdf]
    M. Balazinska et al. Fault-tolerance in the Borealis Distributed Stream Processing System SIGMOD 2005 June 14-16, Baltimore Maryland.
    Sun Microsystems, Sun Game Server API Programming Guide http://www.projectdarkstar.com
  2. Distributed Shared Memory [ps, pdf]
    Amza et al., TreadMarks: Shared Memory Computing on Networks of Workstations IEEE Computer, 1996.
  3. Structuring of Distributed Systems [ps, pdf]
    RPC Comparison
  4. Clocks: Real, Virtual and Logical [ps, pdf]
    D. Mills, Internet Time Synchronization: the Network Time Protocol, IEEE Transactions on Communication.
    D. Jefferson et al, Distributed Simulation and the Time Warp Operating System, SOSP'87.
    D.Cheriton and D. Skeen, Understanding the Limitations of Causally and Totally-Ordered Communication, SOSP'93, Dec. 1993.
    CATOCS talk
  5. Directories and Naming [ps, pdf]
    S. Baset and H. Schulzrinne An Analysis of the Skype Peer-to-Peer Internet Telephony Protocol
    B. Lampson, Designing a Global Name Service, 5th PODC, August, 1986.
    Demers et al., Epidemic Algorithms for Replicated Database Maintenance, PODC'87.
  6. Chapter 6 Transactions and Agreement [ps, pdf]
  7. Chapter 7 Accounts and Authentication [ps, pdf]
    Public Key Certificates Considered Harmful
  8. Chapter 8 Future Directions [ps, pdf]

Project/Problem Sessions

Assignments There is expected to be 2-3 programming assignments with the 3rd possibly morphing into a homework assignment because of time constraints. The first programming assignment is planned to be posted by the first lecture. The intent is to get going right away with a tutorial sessions scheduled for April 7th at 10 am (televised). Details to follow.

Assignment #1 - Mazewar
Assignment #2 - Distributed Replicated Files

Collaboration

Of course you are permitted and encouraged to discuss design strategies with one another, but there should be no sharing of code or header files, and all assistance (other than from the TA or instructor) must be cited. See this link for more detailed explanation of what is permitted and what is not.

Working on assignments

You may work on the assignments on any Unix machine with a modern C/C++ compiler and debugger. But since we will evaluate your assignment on one of the Linux machines in the Terman Engineering Computer Cluster we strongly recommend that you develop and test your code on one of these machines.

You may find the Unix command ssh -X pod.stanford.edu to be useful at your Linux or OS X prompt.

Exams

Midterm: May 6th - in class (exam, answers, histogram)
Final exam: currently scheduled for Wednesday, June 11th, from 12:15-3:15 p.m. in Gates B01

Exams are closed book, closed notes. The final is normally 45 percent of the grade, midterm 15 percent and assignments the remaining 40 percent.

Off-campus students are encouraged to come onto campus for the exams if at all feasible. If necessary, remote SITN/SCPD students may take the exams at their company sites; please have your local tutor send us email to make arrangements.

Old Midterms

Old Finals

Policies

Late assignment policy

You are allowed 3 late day credits for the quarter which you may use as needed to accomodate your schedule. Otherwise, late assignments may be penalized 10% for each 24-hour period or fraction thereof (including weekends) that they are late. Beyond 3 days, they are graded/credited only at the sole discretion of the TA. Please try to make prior arrangements with the TA or instructor if you anticipate any problem with this policy.

Since lectures are made available via Stanford Online on the same day they are taped, SITN/SCPD students are expected to follow the same schedule as the rest of the class. This means that the above late assignment policy applies to SITN/SCPD students as well; exceptions are not granted due to students' work obligations.

Honor code

It should go without saying, but because computer science project courses have a long and ugly history of honor code violations, we will say it anyway:

The Stanford honor code applies to all work done in this course. All work you submit must be your own. Suspected violations of the honor code will be investigated and referred to the Office of Judicial Affairs.

Honor code violations are a serious matter, and being found guilty of one can ruin your academic career. Review the honor code. If you ever find yourself uncertain about how it applies to your situation, ask. Asking what you might think is a silly question is better than risking your career.

Incomplete policy

No incompletes area given in this course, so make sure you determine before the drop deadline whether you can complete it satisfactorily.