6.885 Distributed Algorithms for Mobile Wireless Ad Hoc Networks (H)

L MW 11-12:30, Room 2-136
Professor Nancy Lynch, lynch@csail.mit.edu, Room 32-G668
Prereq.: 6.046, 6.033, 6.852 or equivalent of each
3-0-9

This subject qualifies as a Theoretical Computer Science Engineering Concentration subject.

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. Focusing on algorithms that can be described precisely, and that have relatively well-defined correctness, fault-tolerance, and performance requirements. Aiming to understand the existing theory of wireless network algorithms and contribute to its further development.

Thus, we would like to:

1. 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?

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

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

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

5. Identify useful abstraction layers for programming wireless networks.

The course will involve reading a series of recent research papers, proceeding roughly from lower to higher layers in the ``protocol stack'':

• MAC layer: Collision avoidance, backoff strategies; Collision detection.

• Local infrastructure: Local consensus, leader election; Local reliable broadcast, replicated state machines; Localization; Time synchronization.

• Broadcast

• Point-to-point routing

• Location-based communication services: Location services; Geographical routing.

• Global infrastructure: Power-aware topology control; Clustering; Maximal independent set, spanning trees.

• Middleware services: Mutual exclusion, resource allocation; Token circulation; Group membership, group communication; Synchronization, consensus.

• Virtual node layers.

• Applications: Data aggregation; Implementing shared memory; Tracking; Robot motion coordination