Stanford University
Computer Science 244b: Spring 2016

Distributed Systems

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

Announcements

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.

Details

Lectures:
Tuesday and Thursday 3:00pm-4:20pm. Gates B3
Instructor:
David Cheriton
Office hours: None - send an email or talk me after class to schedule an appointment
Contacting staff:
Please use Piazza for all communications as it easier to track questions and requests. Create private notes if necessary.
https://piazza.com/stanford/spring2016/cs244b
Teaching assistants:
Ali Sharafat (sharafat at stanford)
Office hours: Wednesdays 10:00am-noon at Y2E2 253

Benjamin Braun (bjmnbraun at gmail)
Office hours: Gates 440. Mondays 3:00-5:00, Tuesdays 1:00-3:00 (before class). SCPD feel free to call into office hours via google hangout (my email.)

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 CS144 or CS244A and ideally, CS249A.
Units:
3
Schedule:
  • All due dates are at 11:59 pm unless otherwise noted.
  • TBA
  • Newsgroup:
    We are using Piazza. Make sure get enrolled in this class on it; it will be the primary way of making announcements, advertising review sessions, and answering questions. Just follow the link, create an account, and add CS244B. If you need to contact the staff directly, our addresses are above.
    piazza.com/stanford/spring2016/cs244b

    Materials

    Lectures

    The lectures are based on notes by the instructor, typically one chapter per 2 lectures. Access to this material is restricted to Stanford students.

    The chapters below indicated as 2014 have not been updated to this year yet but should be quite close to what we will use in this offering.

  • Overview [ps, pdf]
  • Distributed Shared Memory [ps, pdf]
  • Structuring of Distributed Systems [ps, pdf]
  • Clocks: Real, Virtual and Logical [ps, pdf]
    CATOCS slides[ppt]
  • Directories and Naming [ps, pdf]
  • Accounts and Authentication [ps, pdf]
  • Transactions, Agreement and Reconiliation [ps, pdf]
  • Distributed Storage Systems (2014) [ps, pdf]
  • Future Directions and Issues (2014) [ps, pdf]
  • 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, unless otherwise stated in class.

    The chapters also list research papers as references, meaning they are optional reading and not required in any way to do 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 CA.

  • B. Stone-Gross et al., Your Botnet is My Botnet: Analysis of a Botnet Takeover UCSB Technical Report Note: not covered on final
  • P. Helland, Life beyond Distributed Transactions: an Apostate’s Opinion
    G. DeCandia et al. Dynamo: Amazons Highly Available Key-value Store SOSP 2007
  • Smart Cheaters Do Prosper: Defeating Trust and Reputation Systems AAMAS 2009
    Public Key Certificates Considered Harmful
    This morning's MD5 attack - resolved Article related to Public Key Certificates Considered Harmful from student, Max Martynov, and his comments
  • D.Cheriton and D. Skeen, Understanding the Limitations of Causally and Totally-Ordered Communication, SOSP'93, Dec. 1993.
    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.
  • 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.
  • 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, 5th edition.

    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. Details to follow.

    Assignment Details

    Assignment 1: Mazewar

    Assignment 2: Replicated Filesystem

    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 myth cluster in the Gates building, we strongly recommend that you develop and test your code on one of these machines.

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

    Exams

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

    The midterm is scheduled for Thursday, May 5. Location: TBD

    Off-campus students are encouraged to come onto campus for the exams if at all feasible. If necessary, remote SCPD students may take the exams at their company sites with a proctor; Stanford SCPD is responsible for distributing exams to proctors as well as returning the completed exams.

    These sample exams should aid you in your studying: Prior Exams

    Policies

    Late assignment policy

    You are allowed 3 late day credits for the quarter which you may use as needed to accommodate your schedule. If an assignment has multiple parts, each part may use late day. 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, 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 SCPD students as well; exceptions are not granted due to students' work obligations.

    Honor code

    Please note that we take the honor code very serious in this class, monitor for honor code violations, investigate suspected honor code violations, and prosecute if necessary. This policy is consistent with Stanford's policy and motivated in part by the desire to be fair to most students who do conform to the honor code.

    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. The instructor and CAs try to help students who get behind or encounter unexpected difficulties. There is more flexibility here than in dealing with violations of the honor code.

    Incomplete policy

    No incompletes are given in this course, so make sure you determine before the drop deadline whether you can complete it satisfactorily. You have other plans for the summer quarter and beyond, and so do we.