Center for Science of Information presents as part of the Prestige Lecture Series on Science of Information

Nancy Lynch, NEC Professor of Software Science and Engineering in the Department of Electrical Engineering and Computer Science at MIT

\\"Distributed Computing Theory for Wireless Networks and Mobile Systems\\"

Recorded Monday April 8th, 2013 via Google Hangouts on Air.

ABSTRACT:
Nearly all modern computer systems are distributed. Most are based on platforms that change dynamically, and many rely on wireless communication. These systems must deal with complications such as node mobility and message collisions. Consequently, such systems are hard to understand and hard to build.

As yet, there is no comprehensive theory to help us out. Such a theory should identify key problems and sub-problems, and should include algorithms, lower bounds, and ways of composing algorithms to build more complex algorithms. The theory should span from the basic communication model to high-level data-oriented and control-oriented applications.

In this talk, I will provide a high-level overview of my group's recent progress on a theory for dynamic systems, especially wireless networks and mobile systems. I will start by describing our work on algorithms for dynamic networks with reliable communication channels, including algorithms for managing data, coordinating robots, and computing functions. I will finish by describing our work on algorithms for wireless networks with unreliable communication channels---channels that exhibit message collisions and losses.

Although this work provides many pieces for the needed theory, there is still a great deal of work to be done.