Announcements

Remember to check this regularly!

• Tuesday Jan. 21th - We will meet at our regular time in L170
• Note the link to the first "Question"
• Friday Jan. 17th - Class meets in our regular classroom and time slot (11-12:20PM)
• Monday Jan. 6th - Class cancelled!
• 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 (http://aqualab.cs.northwestern.edu/classes/eecs-345-w14) 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 the Google Group EECS 345 at Northwestern for class discussion. This particular channel is intended to foster communication among you, the students. You'll find that someone else in the class will have thought of the same problem that you have and will perhaps have some valuable insight that will prove helpful. The staff will be monitoring the discussion threads and will step in with guidance when appropriate. If you don't have a subscription already, you can request one:
  Email:
• 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, two five-week projects and a take home exam.

• Lectures - A set of lectures on the core of the material. Most lectures will be organized in two parts. During the first part (approx. 35'), students will present and discuss as a group the assigned research paper for the day. After a short break, we will cover the lecture topic and necessary background material for the next paper reading and discussion.
• Readings - Textbook and paper reading in preparation for (not substitution of) the lecture.
• Projects - You will build at least one system that addresses issues, solves problems and exploits techniques from classroom discussions and readings.
• Exam - A take-home, final given in the last week of class.

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:

• Questions on reading assignments 20%
• Class participation/presentation 20%
• Project 40%
• Exam 20%

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
• Privacy, security and censorship

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.

Week	Date	Topic
1	1/6/1/8	Introduction [PDF] Reference: Chap. 1, 2 J. Gray, Distributed computing economics, Microsoft TR, 2003 J. Ousterhout, The Role of Distributed State, 1991
	1/13	Go, Go A Short Introduction to Go A Tour of Go J. Newmarch, Network programming with Go Kademlia DHT [PDF] P. Maymounkov and D. Mazieres, Kademlia: A Peer-to-peer Information System Based on the XOR Metric, IPTPS 2002. The original paper. The XLattice Project, Kademlia: A Design Specification, Last published Feb. 2010.
2	1/13	Networking and Internetworking I [PDF] Reference: Chap. 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, In Proc. of ICDCS, August 1981 Paper: K. Winstein and H. Balakrishnan, TCP ex Machina: Computer-Generated Congestion Control, In Proc. of SIGCOMM, 2013 (Question) Presenter: Angela Jiang [slides]
	1/15	Networking and Internetworking II [PDF] Reference: Chap. 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 Paper: J. John, E. Katz-Basset, A. Krishnamurthy, T. Anderson and A. Venkataramani, Consensus Routing: The Internet as a Distributed System, In Proc. of NSDI, 2008 (Question) Presenter: Ruba Merza [slides]
3	1/20	Remote Invocation [PDF] Reference: Chap. 5.2-5.4 A. Birrell and D. Nelson, Implementing Remote Procedure Calls, ACM Transactions on Computer Systems, 2, 1, pgs. 39-59, February 1984. Paper: Y. J. Song et al, RPC Chains: Efficient Client-Server Communication in Geodistributed Systems, Proc. of NSDI 2009 (Question) Presenter: Risbabh Gemawat [slides]
	1/22	Overlay Networks and P2P [PDF] Reference: Chap. 4.5, 10 Paper: G. Kreitz and F. Niemela, Spotify -- Large Scale, Low Latency, P2P Music-on-Demand Streaming, In Proc. of IEEE P2P, 2010 (Question) Presenter: Wenzhou Wang [slides]
4	1/27 2/3	Indirect Communication [PDF] Reference: Chap. 6 P. Eugster, P. Felber, R. Guerraoui and A-M. Kermarrec, The Many Faces of Publish/Subscribe, ACM Computing Surveys, 35(2), 2003. Paper: M. Castro, P, Druschel, P. Kermarrec and A. Rowstron, SCRIBE: A large-scale and decentralized application-level multicast infrastructure, IEEE Journal on Selected Areas in Communication (JSAC), 20:8, 2002 (Question) Presenter: Eric Lin [slides]
	2/3	Distributed File Systems [PDF] Reference: Chap. 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 Paper: A. Adya et al., FARSITE: Federated, Available and Reliable Storage for an Incompletely Trusted Environment, In Proc. of OSDI 2002 (Question) Presenter: Chris Yungmann [slides]
5	2/5	Name Services [PDF] Reference: Chap. 13 P. Mockapetris and K. Dunlap, Development of the Domain Name System, In Proc. of SIGCOMM 1988 J. Jung, E. Sit, H. Balakrishnan, and R. Morris, DNS performance and the effectiveness of caching, In Proc. of ACM SIGCOMM Internet Measurement Workshop 2001 H. Balakrishnan, K. Lakshminarayanan, S. Ratnasamy, S. Shenker, I. Stoica and M. Walfish, A layered naming architecture for the Internet, In Proc. of SIGCOMM, 2004. Paper: V. Ramasubramanian, E. Sirer, The Design and Implementation of a Next Generation Name Service for the Internet, In Proc. of SIGCOMM, 2004 (Question) Presenter: Kalamakar Kambhatla [slides]
	2/10	Content Distribution Networks [PDF] Reference: M. Freedman et al., Democratizing Content Publication with Coral, In Proc. of NSDI, 2004 J. Otto et al., On Blind Mice and the Elephant -- Understanding the Network Impact of a Large Distributed System, In Proc. of ACM SIGCOMM, August 2011 C. Huang et al., Measuring and Evaluating Large-Scale CDNs, In Proc. of IMC, 2008 Paper: M. Zhao et al., Peer-Assisted Content Distribution in Akamai NetSession, In Proc. of IMC, 2013 (Question) Presenter: Dipendra Jha [slides]
6	2/11	Midterm Presentation (Second Project)
7	2/12	Time [PDF] Reference: Chap. 14 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 Paper: DeCandia et al., Dynamo: Amazon’s Highly Available Key-value Store, In Proc. of SOSP 2007 (Question) Presenter (Date): Jianan Wang (2/17)[slides]
	2/17	Global State [PDF] Reference: Chap. 14 M. Chandy and L. Lamport, Distributed Snapshots: Determining Global States of Distributed Systems, ACM TOCS, Feb. 1985 Paper: M. Yabandeh, N. Knezevic, D. Kostic and V. Kuncak, CrystalBall: Predicting and preventing inconsistencies in deployed distributed systems, In Proc. of NSDI, 2009 (Question) Presenter (Date): Muhammed Mas-Ud Hussain (2/19) [slides]
8	2/19	Coordination Reference: Chap. 15 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 Briman et al., Lightweight Causal and Atomic Group Multicast, ACM TOCS 9(3), 1991 Paper: P. Hunt et al., Zookeeper: Wait-Free Coordination in Internet-scale Systems, USENIX ATC, 2010 (Question) Presenter (Date): Ben Rafshoon (2/24) [slides]
	2/24	Consensus and Related Problems [PDF] Reference: Chap. 15 Fisher, Lynch, Patterson, Impossibility of Distributed Consensus With One Faulty Process, JSAC, 1985 L. Lamport, Paxos made simple, ACM SIGACT News, 2001 B. Lampson, How to Build a Highly Available System Using Concensus, TR I. Moraru et al., There is More Consensus in Egalitarian Parliaments, In Proc. of SOSP 2013 M. Aguilera, Stumbling over consensus research: Misunderstandings and issues, Lecture Notes in Computer Science 5959, 59-72 Paper: T. Chandra et al., Paxos made live – an engineering perspective, In Proc. of PODC, 2007 (Question) Presenter (Date): Dipendra Jha (3/3) [slides]
9	3/3	Consistency, replication and fault tolerance [PDF] Reference: Chap. 18 F. Schneider, Implementing Fault-tolerant Services Using the State Machine Approach: A Tutorial, ACM Computing Surveys, 22(4), 1999 Lamport, Shostak, and Pease, The Byzantine Generals Problem, ACM TOPLAS, 1982 R. Ladin et al., Providing Availability Using Lazy Replication, ACM TOCS, 10(4), 1992 M. Castro, B. Liskov, Practical Byzantine Fault Tolerance, In Proc. of OSDI, Feb. 1999 Paper: L. Gendenning, et al. Scalable Consistency in Scatter, In Proc. of SOSP, 2011 (Question) Presenter (Date): Cassandra Rommel (3/5)[slides]
	3/5	Mobile Distributed Systems [PDF] Reference: Chap. 19 M. Weiser, The Computer of the 21st Century, Scientific American, Sep. 1991 Paper: B. Ford et al., Persistent personal names for globally connected mobile devices, OSDI 2006 (Question) Presenter: Kamalakar Kambhatla (3/10) [slides]
10	3/10	Privacy and Security Isdal et al, Privacy-preserving P2P Data-Sharing with One-Swarm, ACM SIGCOMM, 2010 Presenter (Date): Matthew Evans (3/10) [slides] D Andersen, H Balakrishnan, N Feamster, T Koponen, D Moon, S Shenker, Accountable Internet Protocol (AIP), ACM Sigcomm, 2008 (Question) Presenter (Date): Zhengyang Qu (3/12) [slides]
	3/12	Censorship and Censor Resistance S. Burnett et al., Chipping Away at Censorship Firewalls with User-Generated Content, USENIX Security, 2010 (Question) Presenter (Date): Andrew Jiang (3/12) [slides] Project presentations
Finals Week	3/18	Take-home final and reports

Assignments

There are no homework assignments, only one (in two parts) team project and one take-home final exam.

That is not to say the course is easy! Students will work on teams of 2-3 on two projects over the quarter. In addition, every student will be responsible for presenting one paper from those assigned for discussion (either individually, for grad students, or in teams of two for undergraduate students. Last, ever student should submit their answer to one question I will post for each of the papers discussed.

Projects

For the project component of this course you will work in teams of 2-3 students (3 is the preferred number, 1 is not allowed), to implement a basic DHT (Distributed Hash Table) during the first half of the quarter, and build upon it/extend it during the second half.

The project 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.

Part 1

The first project - lasting five weeks - will focus on building the Kademlia DHT -- a very popular DHT first published in 2002. You will start from a minimal base, following the specification linked below. You must adhere to the following schedule:

• Week 1: Familiarize yourselves with Go. We suggest writing a few toy programs before starting on the project proper.
• Week 3: Meet with a member of the course staff to demonstrate your progress. By this point, you should have the structure of your DHT working - new peers should be able to join your network and exchange messages with each other. The only serious work left should be implementing the rest of the protocol.
• Week 5: By 05:59 on Saturday, February 8, email a tarball containing your completed kademlia implementation to the the TA. Read onfor a definition of "complete".

Few distributed systems operate in homogeneous environments. Your project will be evaluated based on its ability to interoperate with other kademlia implementations: if everyone implements the requirements correctly, we will be able to run a single DHT that includes clients from every group. You will receive a reference implementation at least one week before the project is due to help you ensure your code will work.

To ensure compatibility, you must strictly adhere to both the the Xlattice project's kademlia spec (linked below) and the README in the project tarball. In addition, the handout provided should help get you started.

• Kademlia Project Handoir [ handout.pdf]
• The XLattice Project, Kademlia: A Design Specification, Last published Feb. 2010.
• the provided skeleton [ skeleton.tar.gz]

Part 2

During the last five weeks of the quarter, you will build on your Kademlia implementation to addresses issues, solve problems and exploit techniques from classroom discussions and readings. For example, you could enhance your DHT's ability to recover from peer churn, or you could build a consistent storage system on top of it. You should meet with the staff anytime before the fifht week (midterm) to decide on the topic of your second project.

Some additional reading before starting with your project.

• P. Maymounkov and D. Mazieres, Kademlia: A Peer-to-peer Information System Based on the XOR Metric, IPTPS 2002. The original paper.
• Tour of the Go language - Please work through the tour (also available as part of the SDK); you might find it worthwhile to write a simple HTTP client or other toy program before starting your work for the class.
• Network Programming with Go, Jan Newmarch, April 2012.

Reading Papers

We will be reading two or more paper per week; you should have read the assigned paper before coming to lecture. During the first half of most class meetings one or more students will one or more papers and the class will discuss them in a round-table manner. To ensure lively discussions, you will be responsible for reading and answering a question I will post the day before.

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" from now on).
• 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.