COSC 547 - Distributed Computing Outside the Box (Fall 2011)

Georgetown University

Prof. Calvin Newport

Tuesdays and Thursdays, 3:30 pm - 4:45 pm

Intercultural Center, Room 104

Announcements

Course Overview

Description

Distributed computing theory concerns algorithms and impossibility results for coordinating distributed agents. Over the past several decades, this theory has been applied with great success to wired networks and multi-processor systems. Google's massive data centers and the multiple cores on your home desktop both draw from foundational results in this field.

Recently, however, an increasing number of researchers are applying distributed computing theory to more unconventional settings -- from structuring wireless mesh networks, to disseminating data among vehicles, to coordinating robot swarms, to understanding how fireflies desynchronize their flashing.

This course focuses on these unconventional applications of distributed computing theory.

Organization

The course is taught in two pieces. The first piece is a brief primer on distributed computation theory. You will learn the basics of proving upper and lower bounds on both deterministic and randomized distributed algorithms.

During the second piece of the course, which will constitute the bulk of the semester, we will dive into the research literature, exploring the different ways researchers having been applying distributed computing theory in unconventional settings. In particular, we will look at recent applications of this theory to wireless networks, vehicular networks, robot swarms, and nature. For every topic, we will complement the theory papers with one or more practical, systems-oriented papers on the same topic. Our ultimate goal is to debate the question: Is this application of distributed computing theory useful to the real world?

In each class we will cover one or two papers. Some will be presented by students and some will be presented by me (the ratio depending on enrollment).

Prerequisites

Students should have taken an undergraduate algorithms course and be comfortable with basic discrete math. No prior exposure to distributed computing is required: we will cover what you need to know during the first part of the course.

Goals

The application of distributed computing theory to novel settings is an exciting development in this field. The jury is still out, however, about the real world usefulness of these applications. The main goal of this course, therefore, is to better our understanding of the following two questions:

Along the way to answering these questions, you will pick up a familiarity with standard distributed computing theory techniques. By the course's conclusion, you should also be comfortable reading a theory paper in this field and understanding what the results are, why they are important, and the basic approaches deployed to obtain them.

Grading

Throughout the semester you will be assigned short weekly problem sets. During the first part of the course -- the distributed algorithm primer -- these assignments will allow you to practice the techniques we learn. During the second part of the course, your main responsibility is reading, so the problem sets will be short and serve mainly to make sure you did the reading.

In addition to the problem sets, you will graded on your paper presentations and a final project.

The problem set problems will be graded on a check plus, check, check minus, and zero scale. The following are the rough guidelines I will use in assigning these scores during part 1 of the course:

During the second piece of the course (i.e., everything after part 1), we will be reading papers. You will be asked to answer a standard set of questions for most papers (see the course mechanics section for more details on these standard questions and when they are due). The grades for these problem sets will be assigned acording to the following rough guidelines:

During the second piece of the course, (i.e., everything after part 1) you will also be asked to present papers. The grades will be assigned according to the following rough guidelines:

We will discuss the grading criteria for the final project later in the course.

In determining your final grade, I will use the following breakdown:

What Will be Required to Earn an A

To earn an A in this course will require that you score a check plus on most of the problem sets and presentations, and an A or A- on the final project. Because this is a reading course, and not a traditional exam-based course, I fully expect that every student is capable of earning an A. This will require, however, that you put aside sufficient time to dive into the readings, contemplate the problem sets, and craft your presentations. Bare minimum effort will be evaluated as such.

Course Mechanics

Contact & Office Hours

You can contact me and submit assignments at cnewport [at] cs.georgetown.edu. I generally only check my e-mail on a small number of occasions each day, and almost never past normal working hours. With this in mind, my e-mail policy is that I will respond to any student message, at the latest, by 5 pm the day after I receive it.

My office hours are 2 - 3 pm on Tuesdays. My office is 342 A in Saint Mary's Hall.

Schedule & Resources

Due to the fact that we will be reading copyrighted material in this class, the course schedule and resources page is password protected. You can access it here. This is where I will post all lecture notes, problem sets and reading assignments. The papers available on this page are for your personal academic use only. Do not make them public or otherwise distribute. I will give out the username and password in class. You can also e-mail me for it.

Readings

There will be no assigned readings during the first piece of the course -- the lectures will be self-contained. The papers we are covering during the remainder of the course can be downloaded from the password protected schedule page..

Problem Sets

During Part 1 of the course, I will post a problem set every Thursday by 5:30 pm that covers the material taught in the previous two lectures. Each problem set is then due by the start of class the following Thursday. Problem sets should be submitted directly to me by e-mail.

During the second piece of the course (i.e., everything after Part 1), we will be reading papers and discussing them in class. For this second piece, you must answer the standard questions listed below for every paper we read, with the exception of those in lectures labelled A Systems Intermission. Even presenters must submit these answers (though, presumably, if you are presenting a paper, answering these questions should be easy.) Answers to these problems must be submitted to me by e-mail before the start of the class where we cover the paper.

  1. What is the problem (or problems) addressed in this paper?
  2. Why is this problem (or problems) useful to the real world?
  3. What results are achieved? (Be specific.)
  4. How do these results compare to the most relevant existing results? (If there are lots of related results given, you can pick out a handful you think are most relevant. Sometimes there will be no relevant related work; e.g., when a problem is new.)

Problem sets submitted late will have their grade reduced by one level for each 24 hours it is delayed.

During Part 1 of the course (the distributed algorithm's primer) you can collaborate on the problem sets. Each student, however, must write up their own responses (no copying) and list any collaborators. During the subsequent parts of the course, the problem set problems are non-technical in nature and intended mainly to verify that you read the papers. Accordingly, during these parts no problem set collaboration is permitted.

The most efficient way to seek assistance on a problem set is to attend my Tuesday office hours. You can also e-mail me with questions or requests for clarification -- but do not wait until the day before (see my e-mail policy above).

Paper Presentations

When we enter the second piece of the course (i.e., everything after part 1), we will switch to reading papers and discussing them in class. During each lecture, one person will be responsible for presenting the days' papers. The schedule of presentations can be found on the course schedule.

When giving a presentation, you can either use slides or the blackboard. If you use slides, I suggest e-mailing them in advance to me or a web based e-mail account to ensure they can be loaded on the classroom computer.

For the lectures that are not a systems intermission, the presentations should consist of the following:

For lectures that are a systems intermission, it is your responsibility to explain the main points from the papers, and then present your thoughts on what these results tell us about the relevance of the theory papers we just read. Time should be left for classroom discussion.

Final Project

We will discuss the details of the final project as the semester progress. At a high-level, however, you will be asked to identify a novel setting where distributed computing theory might be useful (the more unusual, the better), design and prove correct a basic algorithm for this setting, and then conduct some type of evaluation using real world data. The project will not be onerous, and should be entertaining to work on.