Distributed Algorithms for Wireless Networks
NEC Professor of Software Science & Engineering
Massachusetts Institute of Technology
Monday, March 26, 2012|
4:00pm - 5:00pm
1690 Beyster Bldg.
About the Event
In this talk, I will provide an overview and many examples of recent work on distributed algorithms for wireless networks and mobile systems. These algorithms differ from traditional distributed algorithms in that they must work in much more difficult settings---settings that include complications like node mobility and message collisions. This is an active area for current research.
I will start with a discussion of algorithms for dynamic networks with reliable communication channels, illustrating the general ideas with examples involving function computation, local and global message broadcast, robot coordination, maintaining atomic memory, and Virtual Node abstraction. I will then describe algorithms for models with unreliable channels, in particular, channels that exhibit message collisions and resulting losses. The examples I will consider here will involve leader election, local and global message broadcast, and MAC-layer abstraction. I will finish with a discussion of some issues
involving uncertain message delivery range. Many problems remain open for further study.
Nancy Lynch is the NEC Professor of Software Science and Engineering
in the EECS Department at MIT. She heads the Theory of Distributed
Systems research group in MIT's Computer Science and AI Lab. Prior to
joining MIT, she served on the faculties at Tufts, the University of
Southern California, Florida International, and Georgia Tech. She
received her B.S. degree from Brooklyn College and her PhD from MIT,
both in mathematics.
Lynch 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. Other well-known research contributions include the I/O
automata modeling framework, with Tuttle, Kaynar, Segala, and
Vaandrager. Her recent work is focused on algorithms for wireless networks.
Lynch is the author of the textbook ``Distributed Algorithms'' and
co-author of ``The Theory of Timed I/O Automata''. She is an ACM
Fellow and a member of the National Academy of Engineering. She has
been awarded the Dijkstra Prize (twice), the van Wijngaarden prize,
the Knuth Prize, and the Piore Prize. She has supervised
approximately 25 PhD students and 50 Masters students.
Contact: Cindy Estell
Open to: Public