This year, computer science professor Eli Gafni and one of his former Ph.D. students, Elizabeth Borowsky, have been awarded the 2017 Edsger W. Dijkstra Prize in Distributed Computing for their 1993 publication, “Generalized FLP impossibility result for t-resilient asynchronous computations”.
The award, named after Edsger Wybe Dijkstra, one of the early pioneers of distributed computing and one of the most influential computer scientists in history, is given out annually to outstanding papers whose impact on the theory of distributed computing have been evident for at least a decade. Recipients receive a plaque and a $2,000 prize, as well as a feature of their paper at the ACM Symposium on Principles of Distributed Computing (PODC) and the EATCS Symposium on Distributed Computing.
“I feel very honored to have our work recognized,” Gafni said in reaction to the award. “This is work we did a long time ago, so it’s nice to see that our work has stood the test of time, and still remains a fundamental contribution to the field,” Borowsky added.
Distributed computing is a field of computer science which focuses on the coordination of different machines within a network in order to solve problems or execute tasks. Borowsky and Gafni’s 1993 publication provides several important results about consensus, a fundamental problem in the field of distributed computing that asks whether multiple processors can coordinate reliably to accomplish a task in the presence of failures.
“As the internet scales and as everything becomes more connected, distributed computing has basically become the underpinning of how the different pieces of a network coordinate to provide the service that we now all expect to be at our fingertips,” Borowsky explained. “In the situation of consensus, you want all of these different machines – different pieces of the network – to coordinate with each other to agree upon and produce a single data value. The problem is, you can never know whether or not a computer in the system is just being slow, or if it’s failed entirely.”
When they started their research, it was known that even if one computer might be slow, consensus is impossible. Borowsky and Gafni expanded on this idea by investigating limited consensus, where computers “vote” on two independent data values instead of one. In this situation, computers are also allowed to abstain, and the goal is to reach a unanimous vote – consensus – for at least one data value. Their result implied that if two processors have the possibility of being slow, even limited consensus is impossible.
With hundreds of citations, Borowsky and Gafni’s paper had, and continues to have, an enormous impact on the field of distributed computing, and provides a complete answer to a problem which had puzzled researchers within the field for years.
Gafni’s research interests span over distributed algorithms, mathematical programming with applications to distributed routing and control of data networks, and computer science theory, but since the completion of his Ph.D. at MIT in 1982, his primary research focus has been within the realm of distributed computing. While he completed both his B.S. and M.S. in Electrical Engineering at the Technion – Israel Institute of Technology and the University of Illinois at Urbana Champaign respectively, he eventually became fascinated by the algorithms studied in computer science, which led him to pursue his Ph.D. in EECS at MIT. Shortly after completing his Ph.D., Gafni joined the UCLA computer science department to continue his algorithmic work.
Borowsky completed her B.S. in Mathematics at Williams College in 1990. After taking a required computer science course during her undergraduate career, she realized the areas of math she was interested in were closely related to computer science, and went on to receive her M.S. and Ph.D. in Computer Science at UCLA. During her time at UCLA, Borowsky took Gafni’s distributed algorithms course, where she discovered her passion for distributed computing. She wrote her final paper for the class on the specific case of the consensus problem, which would later go on to serve an integral part in her and Gafni’s award-winning paper. From there, Gafni invited Borowsky to join him in continuing the research on the consensus problem, which the pair eventually solved in 1993. From 1999-2006, Borowsky was an assistant professor of computer science at Boston College.
While Borowsky no longer works in research or academia, she still works within a similar problem space as VP of Engineering at Akamai Technologies, a content delivery network and cloud services provider focused on making the internet fast, reliable, and secure for its customers. Now, Borowsky applies her extensive knowledge of distributed systems to solve problems related to load balancing, networks and topology, and optimization. In the long run, Borowsky hopes her contributions will help in providing the best experiences for the company’s end users, and also hopes to spread awareness of computer science to historically underrepresented groups in the field by helping her company host programs like Girls Who Code.
In terms of long-term goals for Gafni, he hopes that by the time he retires, distributed computing will have a complete body of work that can be taught in future undergraduate courses. “There are still many unanswered questions within the field of distributed computing,” Gafni explained. “There’s no grand unifying theory for distributed computing, but I hope I can give more exposure to the field, and get more people to understand these key questions that need to be answered.”
Gafni will be giving a tutorial on the aspects of distributed computing at the ACM Symposium on Principles of Distributed Computing (PODC) in July in order to spread awareness of the unsolved problems in distributed computing, in hopes of involving more academics in his area of research.
Borowsky and Gafni’s paper is accessible via the ACM Digital Library.