EECS-345 Distributed Systems, Winter 2013

Announcements

Remember to check this regularly!

Administrative Information

Professor

Fabián E. Bustamante
Technological Institute, L465
+1 847 491-2745
This email address is being protected from spambots. You need JavaScript enabled to view it.

TAs

Zach Bischof
Ford Design Building, 2-217
+1 847 467-3250
This email address is being protected from spambots. You need JavaScript enabled to view it.

Location and Time

Lectures: Mondays and Wednesdays 11:00-12:20PM
Tech. L221 NOTE THE CHANGE OF ROOM!

Professor Office Hours: by appointment

TA Office Hours: TBA

Final Exam: TBA

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 and review some of the main paradigms used to organized them.

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

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-w13) 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.
  • 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:

  • Summaries of reading assignments 20%
  • Class participation 20%
  • Project 40%
  • Exam 20%

Topics

  • Introduction
  • Networking and Internetworking
  • Communication and overlay
  • Naming
  • Time and global state
  • Coordination and agreement
  • Concurrency control
  • Consistency and replication
  • Fault tolerance
  • Protection, 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.

Remember to blog on your reading.

Week Date Topic
1 1/7 Introduction/system models/Go

Defining distributed systems and their goals, hardware and software concepts, the client-server model and architecture, modern architectures for distributed systems. An overview of major systems models; we will use a couple of current papers to make our discussion more concrete.

[Slides pdf]

(This is good background material and, if you are a grad student in systems, you should probably read it)

A short introduction to Go [Slides pdf]

1/9 Paper discussion

(this is required reading and blogging)

2 1/14 Networking and Internetworking

(A quick review of networking topics)

[Slides pdf]

1/16 Paper discussion
3 1/21 Off - MLK
1/23 Communication and overlays

A review of common communication models including RPC, publish-subscribe and multicast.

[Slides pdf]

4 1/28 Paper discussion
1/30 Naming

A look at the naming problem and different naming models and systems.

[Slides pdf]

5 2/4 Paper discussion
2/6 Time and global state

Synchronization in distributed systems, logical time, global state.

[Slides pdf]

6 2/11 Paper discussion
2/13 Concurrency control

Mutual exclusion, election, communication.

[Slides pdf]

7 2/18 Paper discussion
2/20 Coordination and agreement

Consensus and related problems.

[Slides pdf]

8 2/25 Paper discussion
2/27 Consistency and replication

Replication, consistency models.

[Slides pdf]

9 3/4 Paper discussion
3/6 Fault tolerance

Fault tolerance and highly available systems.

[Slides pdf]

10 3/11 Paper discussion
3/13 Privacy, security and censorship – paper discussion
F 3/18 Exams begin

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 the 20 assigned for discussion (either individually, for grad students, or in teams of two for undergraduate students. Last, ever student should submit one paper summary to the blog from the same list of discussion papers; you can pick from background readings if we run out of discussion papers.

Projects

For the project component of this course you will work in teams of 2-3 students (3 is the preferred number), 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 six weeks - will focus on building the Kademlia DHT -- a very popular DHT first published in 2002, starting from a minimal base, following the specification linked below. You will need to keep up with the following schedule:

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.

Part 2

During the last four 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 fifth week (midterm) to decide on the topic of your second project.

Before starting your project, you'll need to do some reading.

Reading Papers and Blogging

We will be reading two or more paper per week; you should have read the assigned paper before coming to lecture. On Wednesdays, the papers will be first presented to the group by one or more students and then discussed in a round-table manner. To ensure lively discussions, you will be responsible for reading and preparing a short summary of the assigned papers before each class.

This year we will use a blog to collectively learn from everybody's insight. Everybody (other than the presenters) should read the assigned papers and blog a unique comment about the reading no later than midnight on the day before the class (to give time for everyone to read the entries before class). Note that the earlier you post, the easier it is to be unique. Entries can be parts of your summaries, e.g. main idea, the broader context for the work, a question about some aspect of the paper, an answer to someone else's question, a methodological flaw, missing related work, etc.

The blog for the site is hosted on Blogger. We will automatically add all members of the 345 Google group with @u.northwestern.edu as authors. If you do not get added, please email the TA with your Google or @u email addresses to be added as authors. Make sure to check ahead of time that you have access to the course blog.

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 documents useful:

Materials

Required

Very Useful