Events Calendar

THIS LECTURE HAS BEEN CANCELED - it will be rescheduled for another time. Prestige Lecture Series: Nancy Lynch - Distributed Computing Theory for Wireless Networks and Mobile Systems

Nancy Lynch
NEC Professor of Software Science and Engineering
Software Science and Engineering
MIT

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"

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 research group's recent work on a theory for dynamic systems, especially wireless networks and mobile systems.  I will start by describing our work on networks with reliable communication channels, including algorithms for maintaining atomic memory in dynamic networks, Virtual Node abstraction layers, algorithms for coordinating robot swarms, and algorithms for computing functions in dynamic networks.  I will then describe our work for models with unreliable channels, in particular, channels that exhibit message collisions and resulting losses.  I will finish with a discussion of some issues involving unpredictable message delivery range.

Bio:
Nancy Lynch is the NEC Professor of Software Science and Engineering in the Department of Electrical Engineering and Computer Science at MIT.  She heads the Theory of Distributed Systems research group in MIT's Computer Science and Artificial Intelligence Laboratory.  She is also currently a Fellow at the Radcliffe Institute for Advanced Study.

Lynch received her B.S. degree in mathematics from Brooklyn College in 1968, and her PhD in mathematics from MIT in 1972.  She has written numerous research articles about distributed algorithms and impossibility results, and about formal modeling and verification of distributed systems. Her best-known research contribution is the "FLP" impossibility result for distributed consensus in the presence of process failures, developed with Fischer and Paterson in 1982.

Lynch's other well-known research contributions include the I/O automata mathematical system modeling frameworks, with Tuttle, Vaandrager, Segala, and Kaynar.  Her recent work is focused on algorithms for mobile ad hoc networks.

Lynch has written books  on "Atomic Transactions" (with Merritt, Weihl, and Fekete), on "Distributed Algorithms", and on "The Theory of Timed I/O Automata" (with Kaynar, Segala, and Vaandrager).  She is an ACM Fellow, and a member of both the National Academy of Engineering and the American Academy of Arts and Sciences.  She was co-winner of the first (2006) van Wijngaarden prize, and was awarded the 2007 Knuth Prize, the 2010 IEEE Emanuel Piore award, and the 2012 Athena award.  Lynch has supervised over 25 PhD students and over 50 Masters students, as well as numerous postdoctoral research associates.