Nancy Lynch - Distributed Computing Theory for Wireless Networks and Mobile Systems
Monday, April 08, 2013 2:30 PM - 3:30 PM EDT
Massachusetts Institute of Technology
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.