COSC-547 Distributed Computing Outside the Box
Fall for 2013-2014
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 special topics course focuses on these unconventional applications of distributed computing theory.
The course has two parts. The first part 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 part 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.
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).
Grading will be a mix of three factors: paper presentations, short weekly problem sets on the reading assignments, and an end of term project.
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.
Other academic years
There is information about this course number in other academic years: