Special Topics Graduate Course:
Distributed Algorithms for Mobile Wireless Ad Hoc Networks
6.885, Spring 2006

Professor:
Nancy Lynch

Time and Location:
Mon/Wed 11:00 to 12:30
Room 2-136

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

Professor Jennifer Welch's Course Web Site.   >>

Tentative Reading List.   >>

Handouts.   >>

Course Notes.   >>

Scribe and Lecture Sign-up.   >>

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.