Barbara Liskov Wins ACM A. M. Turing Award

Originally Printed in the Summer/Fall 2009 Newsletter

Professor Barbara Liskov of MIT has won the 2008 Association for Computing Machinery (ACM) A.M. Turing Award.  The Turing Award is the highest honor awarded in Computer Science and Engineering and carries a $250,000 prize. The ACM citation for the award states “Barbara Liskov has led important developments in computing by creating and implementing programming languages, operating systems, and innovative systems designs that have advanced the state of the art of data abstraction, modularity, fault tolerance, persistence, and distributed com-puting systems.” Barbara formally received the award in June at the ACM Award’s Banquet and she will deliver her Turing Award lecture at the Symposium on Operat-ing Systems Principles (SOSP) in October.

Q: One of your most significant early contributions was a new paradigm in programming, data abstraction, developed as a way to better organize and build software systems. Tell us a bit about your insights and your approach to making them concrete by designing CLU. 

One of my first research projects after getting my Ph.D. was to design and implement a small multi-user operating system called Venus. At the end of that project, I began to think about programming methodology and I realized that the way we had organized the program modules in Venus was different from the normal approach of just using procedures.  Instead we had what I call “multi-operation modules”.  These were black boxes that provided code with an interface consisting of several operations.  The entire module was implemented as a unit, and this enabled a greater amount of information hiding than was possible with procedures, since the data structures that were shared among the operations could be hidden inside the module.

The work on multi-operation modules was done while I was still working at the MITRE Corporation.  I left MITRE to join MIT in September 1972.  At MIT, I continued to think about programming methodology and, during my first year there, I got the idea of linking multi-operation modules to data types.  The idea was that the module defined a new data type whose objects could be used by calling the opera-tions.  This work was done jointly with Steve Zilles and led to a paper “Programming with Abstract Data Types” that was published in the fall of 1973.

Then I decided to further investigate the idea of abstract data types by designing a programming language that included them.  I had two reasons for doing this: First, programmers think in terms of programming languages, so de-signing a programming language seemed like a good way to communicate the new ideas.  And second, a programming language has to be well-defined and therefore designing one would force us to be very precise. CLU was designed and implemented during the period of 1973-1978.  This work was done jointly with a number of students and colleagues, including Russ Atkinson, Craig Schaffert, and Alan Synder.

In addition to data abstraction, CLU also contained a number of other innovations, including iterators, parametric polymorphism, and exception handling.  Also because modularity works only if module interfaces are well-defined, I did quite a bit of work on how to specify abstract types, both formally and informally, and also how to verify correctness of code that implements abstract types.

Q: Another major area of your accomplishments has been in the area of distributed systems and especially, reliability and fault tolerance.  Explain some of the problems you have tackled and the solutions you have discovered. 

I became interested in reliability and fault-tolerance in the course of the project I started after CLU.  This was a project to design a programming language that could be used to implement distributed programs.  While working in this area, I realized that distribution, if used naively, can reduce availability: the machine where your I became interested in reliability and fault-tolerance in the course of the project I started after CLU.  This was a project to design a programming language that could be used to implement distributed programs.  While working in this area, I realized that distribution, if used naively, can reduce availability: the machine where your data is stored may not be running when you need to access your data. However, a distributed environment can also improve both availability and reliability, because it enables replication, in which your data is stored at multiple machines.
Replication cannot be done naively, however, since this can lead to users observing odd effects in which the in-formation stored at the different replicas is inconsistent. To address this problem, I began to work on replication protocols that coordinate the replicas to assure consistency.

My early work in this area, done jointly with Brian Oki, led to a protocol called “Viewstamped Replication”, which provides consistency under the assumption that the only way in which replicas can fail is by crashing. Later I became interested in the more challenging Byzantine failure model, in which failed nodes can behave arbitrarily. This work was done jointly with Miguel Castro, and led to the first efficient replication protocol, called PBFT (for “Practical Byzantine Fault Tolerance”) to handle malicious attackers and Byzantine failures. PBFT was based on Viewstamped Replication, but it requires more replicas and more phases in the protocol.

Q: What do you see as the most compelling research challenges for the future? 

I think there is still a lot of basic work to be done, e.g., in the area of support for parallel and distributed programs.  But more and more we will be seeing the use of CS to enable other fields and I think much of the most interesting research will arise in such areas, e.g., CS and biology or CS and medicine. 

Q: What were some of your experiences as the first woman to earn a Ph.D. in computer science and as a woman pioneer in pursuing an academic research career? 

When I got my PhD, there were very few women in faculty positions across all fields, and I’m not aware of any woman who was a faculty member in a computer science department. And I was definitely not in demand for faculty positions. As a result I went to work at MITRE. I stayed at MITRE for 4 years and only moved to MIT in 1972. So I believe that I didn’t move forward as fast as I might have done. But on the other hand, the time at MITRE was helpful since I was changing fields (from AI to systems), and it was easier to do this without having teaching responsibilities.  And I have felt supported at MIT.

Of course in the early days there were very few women. There were a couple at Stanford; for example Susan Graham was a year or two behind me.  But I was the first woman faculty member in CS at MIT, and only the second in my EECS department (which had roughly 70 faculty at the time I joined).  Today we have 9 women faculty in CS out of about 55 total

Q: In what CRA-W programs and other activities to encourage women researchers have you participated?

I was one of the founders of the 2007 SOSP Women’s Workshop that was supported, in part, by the CRA-W Dis-cipline Specific Workshops (DSW) program. This workshop was organized to commemorate the 20th anniversary of the formation of the Systers electronic community.  I was one of the women who gathered at lunch at the 1987 SOSP conference at which Systers was born. I actually remember a discussion in the ladies room about how few women were at SOSP, and this led to that first lunch.  We have preserved that tradition of a lunch for women at every SOSP since. For three years between 2002 and 2005 I served as the associate head for CS.  During this period I ran faculty search and we hired 5 women, thus increasing our total from 4 to 9. Another point is that for at least 10 years prior to my tenure, we had hired no women. More recently I am building on this experience to improve hiring and retention of women and underrepresented minorities across all of MIT, in my capacity as associate provost for faculty equity.

Q: What advice do you have for young women researchers entering our field?

It’s a great field with lots of interesting work to do. And furthermore there is plenty of opportunity.  So if you enjoy it, you should go for it.