Distributed Algorithms for Wireless Networks

Abstract – 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.

Biography – 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.