For almost 30 years Professor Nancy Lynch has made major and lasting contributions to the theory of distributed computing. She has developed new distributed algorithms, created precise models for analyzing distributed processes, and discovered the limitations on what distributed algorithms can accomplish. Her celebrated result in 1982 with M.J. Fischer and M.S. Paterson on the impossibility of distributed agreement in the presence of stopping faults is fundamental in all of computer science. Her development, with M.R. Tuttle, F. Vaandrager, R. Segala, and D. Kaynar, of the I/O Automata mathematical system modeling frameworks brought needed rigor to the field. Her influence extends to practitioners who have benefited from her courses and papers aimed at non-theory audiences, and her insights on distributed computation have influenced other fields of computing, including cryptography, distributed transactions, and hardware synchronization. Her textbook "Distributed Algorithms" is notable both for its very deep and broad coverage and has become a key reference in the field. She is one of the founders of the annual ACM Symposium on Principles of Distributed Computing (PODC) which celebrated its 25th year in 2006. Her influence on the field is also measured by her mentoring of numerous postdocs and over twenty Ph.D. students.
Knuth Prize Committee:
Mike Paterson (Chair)
Tom Leighton
Gary Miller
Anne Condon
Mihalis Yannakakis
Richard Ladner