APPLICATIONS

The ACM Special Interest Group on Algorithms and Computation Theory (SIGACT) will present its 2007 Knuth Prize to Professor Nancy Lynch of the Massachusetts Institute of Technology (MIT) for her influential contributions to the theory of distributed systems, which solve problems using multiple processes or computers connected through a shared memory or network. Professor Lynch is the first woman to receive this award since its inception in 1996. She was cited for her seminal impact on the reliability of distributed computing systems, which are used to power traditional wired networks, modern mobile communications systems, and systems with embedded computers, including factory machinery, vehicles, robots, and other real-world devices. In a career spanning more than 30 years, Professor Lynch developed new distributed algorithms, created precise models for analyzing distributed processes, and discovered limitations on what distributed algorithms can accomplish. In 1982, her research with M.J. Fischer and M.S. Paterson produced a fundamental result, commonly known as the FLP (Fischer, Lynch, Paterson) impossibility result, concerning the impossibility of distributed agreement in the presence of process failures. This breakthrough has had a monumental impact in distributed computing, both theory and practice. Professor Lynch's influence extends to practitioners who have benefited from her courses and papers aimed at non-theory audiences. Her insights on distributed computing have influenced other fields of computing including database transaction procession, hybrid systems, security, and hardware synchronization. Her textbook Distributed Algorithms introduces readers to the fundamental issues underlying the design of distributed systems, including communication, coordination, synchronization and uncertainty. In 2001, Professor Lynch was awarded the Dijkstra Prize (then known as the Principles of Distributed Computing Influential Paper Award) for her research on the FLP impossibility result. Other well-known research contributions include the I/O automata mathematical system modeling frameworks, which she conducted with M.R. Tuttle, F. Vaandrager, R. Segala, and D. Kaynar. An ACM Fellow, she is a member of the National Academy of Engineering and a co-winner of the first van Wijngaarden Prize in 2006, from Centrum voor Wiskunde en Informatica (CWI), the national institute for research in mathematics and computer science in The Netherlands. Professor Lynch is the NEC Professor of Software Science and Engineering at MIT's Department of Electrical Engineering and Computer Science. She heads the Theory of Distributed Systems Research Group in MIT's Computer Science and Artificial Intelligence Laboratory (CSAIL). Prior to joining MIT in 1981, she served on the faculty at Tufts University, the University of Southern California, Florida International University, and the Georgia Institute of Technology. A graduate of Brooklyn College with a B.S. in Mathematics, Professor Lynch received her Ph.D. in Mathematics from MIT. The Knuth Prize is named in honor of Donald Knuth, Professor Emeritus at Stanford University, who is best known for his ongoing multivolume series, The Art of Computer Programming, which played a critical role in establishing and defining Computer Science as a rigorous intellectual discipline. The Knuth Prize was first awarded to Andrew C. - C. Yao, who went on to win ACM's 2000 A.M. Turing Award, considered the "Nobel Prize of computing." The Knuth Prize is given every year and a half by ACM SIGACT and the IEEE Technical Committee on the Mathematical Foundations of Computer Science, and includes a $5,000 award. It will be presented at the ACM Symposium on Theory of Computing (STOC) conference, June 11-13, in San Diego, CA.