6.885  Distributed Algorithms for Mobile Wireless Ad Hoc Networks

Algorithms (6.046 or equivalent)
Computer Systems (6.033 or equivalent)
Desirable: Distributed Algorithms (6.852 or equivalent)

Description:

This course will cover distributed algorithms for mobile (and some non-mobile) wireless ad hoc networks, including those with interesting interactions with the real world. We will focus on algorithms that can be described precisely, and that have relatively well-defined correctness, fault-tolerance, and performance requirements. Our aim is to understand the existing theory of wireless network algorithms and contribute to its further development.

Thus, we would like to:

• Understand the nature of wireless ad hoc network settings. What are typical correctness, reliability, and performance properties that can be assumed? What are the ``right'' complexity measures to use for evaluating algorithms?

• Identify important, well-defined problems and subproblems that must be solved by distributed algorithms in wireless ad hoc networks. These will include problems of low-level and higher-level communication, time synchronization, localization, network configuration, resource allocation, tracking, and data management.

• Learn about the most important existing algorithms for many of these problems, and identify places where additional algorithmic work is needed.

• Identify some inherent limitations (lower bound and other impossibility results) on the solvability of problems in wireless networks.

• Identify useful abstraction layers for programming wireless networks.

The course is aimed at theory-of-computing graduate students who are interested in mobile ad hoc networks, and at graduate students working in systems and application areas who are interested in algorithms, analysis, and other theory. The material will be divided roughly into five parts:

• Part I: Basics: Physical and MAC layers. Time synchronization. Localization.

• Part II: Communication: Global broadcast. Point-to-point routing with and without location information. Location services.

• Part III: Building and maintaining network structures: Topology control. Clustering. Maximal independent sets, coloring, etc.

• Part IV: Middleware: Local infrastructure (local consensus, local reliable broadcast, etc.). Token circulation. Compulsory protocols. Virtual node layers.

• Part V: Applications: Data aggregation. Population protocols. Computing properties in mobile net- works. Implementing atomic memory. Robot and vehicle motion coordination.

Course requirements:
We will be reading and discussing a lot of papers. Students in the class will be required to read one or two papers before each class, to participate in the class discussions, and to answer basic questions about the readings (in “mini-problem-sets”). Each student will also help in presenting one of the course topics in class, and will carry out a term project focusing on one of the topics.