**Sept. 13**My office number has changed to 342 A.**Sept. 8**The first problem set is now available. It can be downloaded from the password protected course schedule and resources page.**Sept. 8**If you are attending the course but are not registered, please send me an e-mail so I can add you to the course announcement e-mail list.**Sept. 2:**The password protected course schedule and resources page is now live and can be accessed here. This is where I will post all lecture notes, problem sets and reading assignments. I will give out the username and password in class. You can also e-mail me if you need it.

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.

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).

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.

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:

- How useful are the current applications of distributed computing theory beyond the traditional settings?
- What are the most promising future directions for this field?

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.

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:

**Check plus:**At most a small number of small mistakes.**Check:**Some small mistakes, at most one large mistake.**Check minus:**Multiple large mistakes and/or many small mistakes.**Zero:**Didn't hand in the problem set, or handed in incomplete solutions.

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:

**Check plus:**Complete answers to all four parts for all papers assigned (including specific results, in mathematical notation, for the third and fourth part, when relevant).**Check:**Missing some specifics.**Check minus:**Many details missing.**Zero:**Didn't hand in.

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:

**Check plus:**A clear and correct presentation of all required parts.**Check:**Some material missing, incorrect, or hard to follow.**Check minus:**Major material missing, incorrect, or hard to follow.**Zero:**Does not show up with presentation prepared.

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:

- Problem sets - 40%
- Presentations - 40%
- Final project - 20%

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.

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.

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.

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.**.

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

- What is the problem (or problems) addressed in this paper?
- Why is this problem (or problems) useful to the real world?
- What results are achieved? (Be specific.)
- 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).

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:

- A detailed elaboration on the answers to the questions from the standard problem set.
- A detailed walk through of one or more highlighted results from the paper. I will tell you which results I think you could highlight, and which are less important or too complicated to bother with.
- Depending on the timing of your presentation, feel free to focus your time unevenly (e.g., spend more time going into the details of the highlighted result for one paper, and then give only high-level intuition for the second).
- You don't have to list every result from both papers if there are a lot.
- In general,
**I am looking for two things in your presentations:**First, you are able to convey what the results mean, and are not just listing them; and second, you are able to give a solid intuition about how they achieved the highlighted result(s).

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.

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.