Microsoft Research Blog

The Microsoft Research blog provides in-depth views and perspectives from our researchers, scientists and engineers, plus information about noteworthy events and conferences, scholarships, and fellowships designed for academic and scientific communities.

Microsoft Research’s Dwork Wins 2007 Dijkstra Prize

August 9, 2007 | By Microsoft blog editor

By Rob Knies, Managing Editor, Microsoft Research

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

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

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, 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, 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, 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, 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 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, 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, 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.”

Up Next

Artificial intelligence, Computer vision, Human-computer interaction, Medical, health and genomics, Programming languages and software engineering

Microsoft Research Dissertation Grants: Broadening the PhD pipeline to increase innovation

Research shows that diverse teams are more productive teams. Diversity, particularly in the area of computing research, means including unique perspectives that otherwise might not have a voice, fueling innovation. These are some of the key reasons that Microsoft is committed to diversity. One aspect of demonstrating that commitment is that, for the second year […]

Meredith Ringel Morris

Principal Researcher and Research Manager

Algorithms, Artificial intelligence, Computer vision, Data management, analysis and visualization, Hardware and devices, Human-computer interaction, Mathematics, Programming languages and software engineering, Security, privacy, and cryptography, Social sciences, Systems and networking, Technology for emerging markets

Microsoft Research PhD fellowships provide financial support to promising researchers

By Jim Pinkelman, Senior Director, Microsoft Research Since 2008, Microsoft Research has been awarding two-year PhD fellowships to computer science and related researchers at leading universities in the United States and Canada. These awards are designed to help promising young researchers focus on their studies, not their finances! This year’s program provides fellowships to 10, […]

Microsoft blog editor

Programming languages and software engineering

Microsoft Research and the industrial research cycle

A personal view By Thomas Ball, Research Manager, Research in Software Engineering (RiSE) group, Microsoft Research The industrial research cycle Here is what I have told new hires of Microsoft Research (MSR) since I became a manager some 14 years ago: MSR gives you the freedom to explore and expand the bounds of scientific knowledge, […]

Microsoft blog editor