Announcements

Remember to check this regularly!

• Last homework assignment is posted!
• Homework 3 is posted!
• Project 2 deadline extended to Monday (5/18)
• Project 0 and Project 1 grades are posted!
• Project 2 is posted!
• Project 1 is posted!
• Project 0 is posted!
• Take the tour – http://tour.golang.org

Course Description

Distributed systems are collections of networked computers that coordinate their actions through message exchanges. Most computing systems you interact with everyday are indeed distributed (e.g. email, web, Google, Skype, Facebook ...) for a variety of reasons such as fault tolerance, performance, and the geographical nature of the requirements.

In this course, we will discuss some of the basic principles behind distributed systems as well as common approaches and techniques used to build them. We illustrate these ideas through case studies of widely used or seminal systems.

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 This email address is being protected from spambots. You need JavaScript enabled to view it. . 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

• EECS-343 Operating Systems (or equivalent)
• EECS-340 Introduction to Networking.
• (Please contact me if you do not meet some of these requirements.)

Communication Channels

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

• We will use the course web site 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.
• We will use Piazza for class discussion. The system is highly catered to getting you help fast and efficiently from classmates, the TA, and myself. Rather than emailing questions to the teaching staff, I encourage you to post your questions on our Piazza for DS
• There is always email for questions that would be inappropriate to post on the newsgroup/discussion-board. When using email to contact the staff please start your subject line with "eecs345: helpful-comment" to ensure a prompt response.

Course Organization

The course is organized as a series of lecture and paper discussions, four projects and a take home exam.

• Lectures - A set of lectures on the core of the material. At the end of some key topics we will have one student lead presentation of a closely related, somewhat recent research.
• Readings - Textbook and paper reading in preparation for (not substitution of) the lecture.
• Homework assignments - A set of assignments meant as reader enforcers.
• Projects - Four programming projects to give you a better understanding of the subject matter and experience with the Go programming language.
• Atake-home final exam.

Grading

I use a criterion-referenced method to assign your grade; in other words, your grade will be based on how well you do relative to predetermined performance levels, instead of in comparison with the rest of the class. Thus, if a test has 100 possible points, anyone with a score of 90 or greater will get an A, those with scores of 80 or greater will get a B, those with scores of 70 or greater will get a C, and so on. Notice that this means that if everyone works hard and gets >90, everyone gets an A.

Total scores (between 0 and 100) will be determined, roughly, as follows:

• Homework assignments 20%
• Class participation/presentation 15%
• Projects 40%
• Exam 25%

Policies

Late policy:

Unless otherwise indicated, homework assignments and projects are due by midnight on their due date. If you hand in an assignment late, we will take off 10% for each day (or portion thereof) it is late. Assignments that are three or more days late receive no credit.

Cheating vs. Collaboration:

Collaboration is a really good thing and we encourage it. On the other hand, cheating is considered a very serious offense. When in doubt, remember that it's OK to meet with colleagues, study for exams together, and discuss assignments with them. However, what you turn in must be your own (or for group projects, your group's own) work. Copying code, solution sets, etc. from other people or any other sources is strictly prohibited.

Topics

• Introduction
• Networking and Internetworking
• Remote invocation and indirect communication
• Overlay networks and P2P
• Distributed file systems
• Name services
• Time and global state
• Coordination and agreement
• Consistency and replication
• Mobile distributed systems

For each of the topics, we will first review introductory material before presenting and discussing a related research paper to help you better understand the main issues.

The following is our intended calendar with topics, slides (as they become available) and reference material. Note "CDKB5 #" refers to chapters of the class' textbook (Coulouris et al., Distributed Systems: Concepts and Design, 2012).

Week	Date	Topic
1	3/30	Introduction [pdf] References: CDKB5 1,2 Google’s introduction to DS design Fallacies of Distributed Computing
	4/1	Go, Go [pdf] [tutorial.tgz] References: A Short Introduction to Go A Tour of Go J. Newmarch, Network programming with Go
2	4/6	Networking and Internetworking I [pdf] References: CDKB5 3, 4 D. Clark, The design philosophy of the DARPA Internet Protocols, In Proc. of ACM SIGCOMM, August 1988 J.H. Saltzer, D.P. Reed, and David Clark, End-to-End Arguments in System Design, ACM TOCS, 2(4):277-288, Nov. 1984.
	4/8	Networking and Internetworking II [pdf] References: CDKB5 3, 4 H. Balakrishnan and N. Feamster, Interdomain Internet Routing, Lecture 4, 2005 C. Labovitz et al, Delayed Internet Routing Convergence, In Proc of SIGCOMM, 2001
3	4/13	Communication I [pdf] References: CDKB5 5, 6 A. Spector, Performing remote operations efficiently on a local computer network, CACM 25(4), 1982 A. Birrell and D. Nelson, Implementing Remote Procedure Calls, ACM Transactions on Computer Systems, 2, 1, pgs. 39-59, February 1984.
	4/15	Communication II [pdf] References: CDKB5 5, 6, 20.6.3 P. Eugster, P. Felber, R. Guerraoui and A-M. Kermarrec, The Many Faces of Publish/Subscribe, ACM Computing Surveys, 35(2), 2003. Y. Chu et al., A Case for End System Multicast, In Proc. of SIGCMETRICS, 2000
4	4/20	Overlay Networks [pdf] References: CDKB5 4.5, 10 P. Maymounkov and D. Mazieres, Kademlia: A Peer-to-peer Information System Based on the XOR Metric, IPTPS 2002. The original paper. S. Baset and H. Schulzrinne, An Analysis of the Skype Peer-to-Peer Internet Telephony Protocol, INFOCOM 2006.
	4/22	Distributed File Systems [pdf] References: CDKB5 12 R. Sandberg, D. Goldberg, S. Kleiman, D. Walsh and B. Lyon, Design and Implementation of the Sun Network File System, In Proc. of the Summer USENIX Tech Conference and Exhibition, 1986 J. Howeard, M. Kazar, S. Menees, D. Nichols, M. Satyanarayanan, R. Sidebotham and M. West, Scale and Performance in a Distibuted File System, ACM Transactions on Computer Systems, 6(1), 1988
5	4/27	Distributed File Systems [pdf] References: CDKB5 12 S. Ghemawat et al., The Google File System, In Proc. of SOSP 2003. K. McKusick and S. Quinlan, GFS: Evolution and Fast-forward; a discussion between ACM Queue 2009. A. Muthitacharoen et al., A Low-bandwidth Network File System, In Proc. of SOSP 2001.
	4/29	Name Services [pdf] References: CDKB5 13 B. Lampson, Designing a Global Name Service, In Proc. of PODC, 1986 P. Mockapetris and K. Dunlap, Development of the Domain Name System, In Proc. of SIGCOMM 1988
6	5/4	Off
	5/6	Content distribution networks [pdf] References: CDKB5 10, 20.6 M. Freedman et al., Democratizing Content Publication with Coral, In Proc. of NSDI, 2004 C. Huang et al., Measuring and Evaluating Large-Scale CDNs, In Proc. of IMC, 2008 M. Zhao et al., Peer-Assisted Content Distribution in Akamai NetSession, In Proc. of IMC, 2013
7	5/11	Time and Synchronization [pdf] References: CDKB5 14.1, 14.4 F. Cristian, Probabilistic clock synchronization, Distributed Computing 3:146-158, 1989. D. Mills, Internet Time Synchronization: the Network Time Protocol, Transactions on Communications, 1991 L. Lamport, Time clocks and the ordering of events in a distributed system, Communications of ACM, 1978 M. Raynal and M. Singhal, Logical time: Capturing causality in distributed systems, IEEE Computer, 29(2), February 1996
	5/13	Global State [pdf] References: CDKB5 14.5,14.6 M. Chandy and L. Lamport, Distributed Snapshots: Determining Global States of Distributed Systems, ACM TOCS, Feb. 1985
8	5/18	Coordination I [pdf] References: CDKB5 15.1-15.4 T. Chandra and S. Toueg, Unreliable Failure Detectors for Reliable Distributed Systems, JACM, 43(2), March 1996 B. Sanders, The Information Structure of Distributed Mutual Exclusion Algorithms, ACM Transactions on Computer Systems, 5(3), 1987 H. Garcia-Molina, Elections in Distributed Computer Systems, IEEE Transacions on Computers, C-31(1), 1982
	5/20	Coordination II [pdf] References: CDKB5 15.1-15.4 Kaashoek et al.,An efficient reliable broadcast protocol, ACM SIGOPS 23(4), 1989. Birman et al., Reliable communication in the presence of failures,, ACM TOCS 5(1), 1991 Birman et al., Lightweight Causal and Atomic Group Multicast, ACM TOCS 9(3), 1991
9	5/25	Memorial Day
	5/27	Consensus [pdf] References: CDKB5 15.5 Lamport, Shostak, and Pease, The Byzantine Generals Problem, ACM TOPLAS, 1982 Fisher, Lynch, Patterson, Impossibility of Distributed Consensus With One Faulty Process, JSAC, 1985 L. Lamport, Paxos made simple, ACM SIGACT News, 2001 T. Chandra et al., Paxos made live – an engineering perspective, In Proc. of PODC, 2007 M. Burrows, The Chubby lock service for loosely-coupled distributed systems, In Proc. of OSDI 2006.
10	6/1	Replication and Fault Tolerance [pdf] References: CDKB5 18 F. Schneider, Implementing Fault-tolerant Services Using the State Machine Approach: A Tutorial, ACM Computing Surveys, 22(4), 1999 R. Ladin et al., Providing Availability Using Lazy Replication, ACM TOCS, 10(4), 1992 D. Terry et al., Session guarantees for weakly consistent replicated data, Proc. of PDIS, 1994
	6/3	Mobile and Ubiquitous [pdf] References: CDKB5 19 M. Weiser, The Computer of the 21st Century, Scientific American, Sep. 1991 M. Satyanarayanan, Fundamental Challenges in Mobile Computing, In Proc. of PDOC, 1996 M. Satyanarayanan, Pervasive Computing: Vision and Challenges, IEEE Personal Communication, 2001
*	6/8	Final

Assignments

There are some basic homework assignments, mostly meant as reading eforcers, and warmup project and three team projects that build on each other.

In addition, groups of 4-5 students (assigned by the instructors) will work to do a presentation and prepare educational material around on one of the 7-8 papers assigned by the instructors. The material, to be shared with the rest of the class, will include a summary, presentation slides, and a homework assignment and/or demo.

Take a look at the homework assignments.

Projects

The firt project for this course is a short, one-week long project meant to serve as a gentle introduction to Go and a quick way to check if you are ready to take on the rest. The following three projects are to be done in teams of 2-3 students (3 is the preferred number, 1 is not allowed), to implement a basic DHT (Distributed Hash Table) and build upon it in some interesting way.

All projects will be done in Go, a language that was originally created within Google, but is now a fully open-source project. Go is garbage-collected and has built-in coroutines and channels, making it highly suited to building distributed systems. Its standard library is already pretty comprehensive. For example, take a look at the net and rpc packages.

Take a look at the project descriptions.

Reading Papers

We will be reading two or more paper per week; you should have read the assigned paper before coming to lecture.

When reading papers it is 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 documents useful:

• How to Read a Paper by S. Keshav, ACM SIGCOMM CCR, 37(3), 2007.
• Efficient reading of papers in Science and Technology by Michael J. Hanson, 1990, revised 2000 Dylan McNamee.

Materials

Required

• George Coulouris, Jean Dollimore, Tim Kindberg and Gordon Bair, Distributed Systems: Concepts and Design.Pearson, 5th Ed., 2012 ("CDKB5").
• A set of research papers I will make available (see the schedule page for a full list).

Very Useful

• S. Keshav, How to Read a Paper, ACM SIGCOMM CCR, 37(3), 2007.
• Michael J. Hanson, Efficient reading of papers in Science and Technology, 1990 (revised 2000 Dylan McNamee).
• 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.