Colloquium d’Informatique de Sorbonne Université
Nancy Lynch, MIT

Thursday, September 12, 2019 18:00
Amphi 44 Sorbonne University - Faculté des Sciences

A Theoretical View of Distributed Systems

Nancy Lynch is the NEC Professor of Software Science and Engineering in MIT's EECS department, and until recently, an Associate Department Head. She heads the Theory of Distributed Systems research group in the MIT Computer Science and Artificial Intelligence Laboratory. She received her PhD from MIT and her BS from Brooklyn College, both in Mathematics. Lynch has (co-)written many research articles about distributed algorithms and impossibility results, and about formal modeling and verification of distributed systems. Her best-known contribution is the “FLP” impossibility result for reaching consensus in asynchronous distributed systems in the presence of failures, with Fischer and Paterson, followed by a paper with Dwork and Stockmeyer on algorithms for reaching consensus under restricted failure assumptions. Other contributions include the I/O automata system modeling frameworks, with Tuttle, Kaynar, Segala, and Vaandrager. Lynch is the author of the textbook “Distributed Algorithms” and co-author of “The Theory of Timed I/O Automata” and “Atomic Transactions”. She is an ACM Fellow, a member of the National Academy of Engineering and the National Academy of Sciences, and a Fellow of the American Academy of Arts and Sciences. She has been awarded the Dijkstra Prize (twice), the van Wijngaarden Award, the Knuth Prize, the Piore Award, and the Athena Lecturer Award. She has supervised approximately 100 PhD students, Masters students, and postdocs. Lynch is interested in all aspects of distributed computing theory, including modeling, algorithm design, analysis, lower bounds, and applications. She is especially interested in algorithms for “difficult” platforms, which are subject to noise, failures, and changes. Recently, her work has focused on wireless network algorithms, biological distributed algorithms, and the connections between them.

Abstract

For several decades, my collaborators, students, and I have worked on theory for distributed systems, in order to understand their capabilities and limitations in a rigorous, mathematical way. This work has produced many different kinds of results, including :

Abstract models for problems that are solved by distributed systems, and for the algorithms used to solve them ;
Rigorous proofs of algorithm correctness and performance properties (also some error discoveries) ;
Impossibility results and lower bounds, expressing inherent limitations of distributed systems ;
Some new algorithms ;
and General mathematical foundations for modeling and analyzing distributed systems.

These various results have spanned many different kinds of systems, ranging from distributed data-management systems, to communication systems, to biological systems such as insect colonies and brains. In this talk, I will overview some highlights of our work over many years on theory for distributed systems. I will break this down in terms of three intertwined “research threads”: algorithms for traditional distributed systems, impossibility results, and mathematical foundations. At the end, I will say something about our recent work on algorithms for new kinds of distributed systems.

Master Class

One particularly popular moment associated to the colloquium is the “Master Class” where students have the opportunity to give a short (but well-prepared) presentation of his/her work. Each presentation (10 minutes) is followed by an open discussion with the guest speaker (15 minutes) who gives a detailed feedback. The complete program is provided here.