Microsoft Research’s Dwork Wins 2007 Dijkstra Prize

Published August 9, 2007

Share this page

By Rob Knies, Managing Editor, Microsoft Research

Cynthia Dwork (opens in new tab), a principal researcher for Microsoft Research Silicon Valley, has been honored as co-winner of the 2007 Edsger W. Dijkstra Prize in Distributed Computing (opens in new tab).

The award, one of the most prestigious in the distributed-systems discipline, was announced July 24 by the award committee of the Association of Computing Machinery’s Symposium on Principles of Distributed Computing (PODC).

Cynthia Dwork

The 2007 Dijkstra Prize was bestowed upon Dwork, Nancy Lynch, and Larry Stockmeyer, the latter posthumously, for their paper Consensus in the Presence of Partial Synchrony (opens in new tab), which appeared in the Journal of the ACM in April 1988.

The prize is given each year to an outstanding paper on the principles of distributed computing, the significance and impact of which on the theory and/or practice of distributed computing has been evident for at least a decade. Papers appearing in any conference proceedings or journal are eligible as long as they have had a significant impact on research areas of interest within the PODC community and as long as the year of publication is at least 10 years before the year in which the award is given.

“In a fast-moving field such as ours, significant work often slides into the subconscious of current practitioners, becoming ‘just the way things are done,’ “ noted Roy Levin, Microsoft distinguished engineer and director of Microsoft Research Silicon Valley. “The Dijkstra Prize highlights work that is woven into the fabric of present-day computing and, in so doing, helps to fight this collective amnesia. I’m delighted to see this paper recognized as one in that special class.”

In the official award citation, the time-proven contribution of the paper by Dwork, Lynch, and Stockmeyer is recounted at length:

“This paper introduces a number of practically motivated partial synchrony models that lie between the completely synchronous and the completely asynchronous models and in which consensus is solvable. It gave practitioners the right tool for building fault-tolerant systems and contributed to the understanding that safety can be maintained at all times, despite the impossibility of consensus, and progress is facilitated during periods of stability. These are the pillars on which every fault-tolerant system has been built for two decades. This includes academic projects such as Petal, Frangipani, and Boxwood, as well as real-life data centers, such as the Google file system.

“In distributed systems, balancing the pragmatics of building software that works against the need for rigor is particularly difficult because of impossibility results such as the FLP theorem. The publication by Dwork, Lynch, and Stockmeyer was, in many respects, the first to suggest a path through this thicket and has been enormously influential. It presents consensus algorithms for a number of partial synchrony models with different timing requirements and failure assumptions: crash, authenticated Byzantine, and Byzantine failures. It also proves tight lower bounds on the resilience of such algorithms.

“The eventual synchrony approach introduced in this paper is used to model algorithms that provide safety at all times, even in completely asynchronous runs, and guarantee liveness once the system stabilizes. This has since been established as the leading approach for circumventing the FLP impossibility result and solving asynchronous consensus, atomic broadcast, and state-machine replication.

“In particular, the distributed-systems engineering community has been increasingly drawn toward systems architectures that reflect the basic split between safety and liveness cited above. Dwork, Lynch, and Stockmeyer thus planted the seed for a profound rethinking of the ways that we should build, and reason about, this class of systems. Following this direction are many foundational solutions.”

The e-mail went to cite as one of those solutions the “seminal Paxos algorithm” contributed by Leslie Lamport (opens in new tab), also a principal researcher for Microsoft Research Silicon Valley. That citation provides a direct link to the history of the Dijkstra Prize. In 2000, Lamport won the inaugural version of the award, then called the PODC Influential-Paper Award, for his Time, Clocks, and the Ordering of Events in a Distributed System (opens in new tab), which appeared in Communications of the ACM in July 1978.

In 2005, the Dijkstra Prize was shared by Marshall Pease, Robert Shostak, and Lamport for their Reaching Agreement in the Presence of Faults (opens in new tab), which appeared in the Journal of the Association of Computing Machinery in April 1980.

Dijkstra, who died in 2002 at age 72, was a Dutch computer scientist who won the A.M. Turing Award (opens in new tab) in 1972. A pioneer in the field of distributed computing, Dijkstra undertook foundational work on concurrency primitives, concurrency problems, reasoning about concurrent systems, and self-stabilization. His efforts provide one of the most important supports upon which the field is built.

As the PODC Web page about the prize states, “No other individual has had a larger influence on research in principles of distributed computing.”

Dijkstra himself won the PODC Influential-Paper Award in 2002, for Self-stabilizing Systems in Spite of Distributed Control (opens in new tab), which appeared in Communications of the ACM in 1974. After his death, the prize was renamed in his honor.

Dahlia Malkhi, a senior researcher at Microsoft Research Silicon Valley, appeared on the award committee for this year’s Dijkstra Prize. She served as the award-committee chair for the 2006 Dijkstra Prize.

Lynch had been honored in 2001 with the second presentation of the then-PODC Influential-Paper Award, along with Michael J. Fischer and Michael S. Paterson, for Impossibility of Distributed Consensus with One Faulty Process (opens in new tab), published in the Journal of the ACM in April 1985.

Stockmeyer died in July 2004. In announcing this year’s prize, the award committee said that “Larry’s impact on the field through this paper and many others will always be remembered.”