The Peterman Pod - Turing Award Winner: Data Abstraction, Dijkstra, Distributed Systems | Barbara Liskov

Episode Date: April 27, 2026

Barbara Liskov is a Turing Award winner known for her work in programming languages and distributed systems. We discussed the major problems she solved in her career, stories about Dijkstra, getting rejected from Princeton because she was a woman and misc topics around her work.🔸 My keyboard Kickstarter: https://www.kickstarter.com/projects/ryanlpeterman/compose-simple-ergonomics-beautifully-done𝗣𝗼𝗱𝗰𝗮𝘀𝘁 𝗹𝗶𝗻𝗸𝘀:• YouTube: https://youtu.be/T9CGjbPZeaM• Apple: https://podcasts.apple.com/us/podcast/the-peterman-pod/id1777363835• Transcript: https://www.developing.dev/p/turing-award-winner-data-abstraction𝗘𝗽𝗶𝘀𝗼𝗱𝗲 𝗹𝗶𝗻𝗸𝘀:• Go To Statement Considered Harmful: https://homepages.cwi.nl/~storm/teaching/reader/Dijkstra68.pdf• Viewstamped Replication: https://www.cs.princeton.edu/courses/archive/fall09/cos518/papers/viewstamped.pdf𝗧𝗶𝗺𝗲𝘀𝘁𝗮𝗺𝗽𝘀:0:00 - Intro1:00 - Getting rejected from Princeton2:53 - The software crisis9:03 - The drawbacks of Python10:17 - Getting into distributed computing13:09 - Paxos vs Viewstamped replication21:44 - The significance of Dijkstras letter25:04 - Why she stayed in academia30:39 - Why her award was questioned33:51 - Outro𝗪𝗵𝗲𝗿𝗲 𝘁𝗼 𝗳𝗶𝗻𝗱 𝗕𝗮𝗿𝗯𝗮𝗿𝗮:• Wikipedia: https://en.wikipedia.org/wiki/Barbara_Liskov𝗪𝗵𝗲𝗿𝗲 𝘁𝗼 𝗳𝗶𝗻𝗱 𝗥𝘆𝗮𝗻:• Newsletter: https://www.developing.dev/• X/Twitter: https://x.com/ryanlpeterman• LinkedIn: https://www.linkedin.com/in/ryanlpeterman/• Threads: https://www.threads.com/@ryanlpeterman• Instagram: https://www.instagram.com/ryanlpeterman• TikTok: https://www.tiktok.com/@ryanlpeterman

Don't do incremental work. This is Barbara Liskov. She's a Turing Award winner, famous for her fundamental contributions to programming languages and distributed systems. Encapsulation is a crucial part of making modularity work. Your team is really only as strong as your weakest programmer. I asked her for stories from her career. That paper was the go-to statements considered harmful. Is Dykstra in person also like his writing?

He was not always as tactful. always as tactful as he might be. There were people saying, why did she get the Turing Award? Why do you think that they said that about your work? Here's the full episode. You applied to multiple places, and Princeton was one of them, and they had rejected you on the grounds of you being a woman. How did you get into programming in an environment that's so hostile?

Okay, so this was when I got my bachelor's degree. and I applied to several graduate programs in math, which is what I majored in as an undergraduate. And I got this little card back. It was a postcard from Princeton saying, we do not admit women, which was surprising. I knew they didn't have women in their undergraduate program, but I hadn't realized it extended to the graduate program. but, you know, it was how it was. So what happened was I did get into Berkeley, which is where I did my undergraduate work,

but I decided I really wasn't ready to do a PhD in math and that I should get a job instead and just sort of see, you know, see how things were. And the best job offer I got was as a programmer. So that's how I got into computer science by a happy accent. You were consistently, at least at Berkeley, you were consistently a top student. So it is odd that you wouldn't even get an opportunity to play in some cases. But that's how it was back then. It was just I hadn't realized it was more than an undergraduate thing.

And Berkeley was co-ed. So, you know, what I found was there weren't very many women in my classes. There were lots of women students, but very few of the majoring. in math. And there were only maybe a couple of women in my classes. But the idea that a door was shut and women couldn't do things, that was not what went on at Berkeley. So it was a different environment. Of course, nowadays, in the top schools, the women are about 50% in computer science. I want to talk about some of the core problems that you were solving in your career. And so I understand that there's the software crisis in the 1970s. And I was wondering if you could give the

context behind what the problem was at that time. Well, it was a huge problem at the time because people did not know how to build big programs that worked. And so you would often pick up the newspaper and see an article about some company that had spent, you know, millions of dollars and hundreds of man years developing some software system for their company, and then in the end they'd have to throw it away because it simply didn't work. The problem was that to get a big program that works, you need modularity. And you need to break your program up into small pieces. Each piece provides an interface with a hopefully,

complete description of what service it provides for you. And then inside is an implementation that's hidden and nobody pays any attention to it on the outside. And if you have a system organized like that, you can actually reason about its correctness, one module at a time. But in those days, people didn't know how they couldn't figure out how to design systems that were modular. And the only kind of modularity mechanism, president programming languages was a procedure, and procedures didn't match the kinds of modules you needed, because if you think about a file system or a database or, you know, Amazon or whatever, you know, they aren't a procedure where you put something in and get something out. They're a much

more complicated thing. So there was no notion of a module that sort of matched the kind of things that people were looking for. So when you saw that problem, you know, what were the early solutions like? Well, so people were proposing modularity, and they were talking about how important modularity was. They didn't exactly know what a module was. And so it wasn't like they could give you a rule. This is a module. It was just a chunk of code.

In fact, there were papers written that talked about how big a module should be and stuff like that, just a chunk of code. that's not going to work because you need to design these systems, so you need a way of thinking of a design that sort of fits into this notion of modularity. They also didn't really know what the rules should be for modularity. And it turned out that in some of the early work I did after grad school when I was working at MITR, I had already invented a notion of modularity that was sort of more complete than what people had been talking about, just because I had a small team of programmers. We were building a complicated system, and I wanted to keep us out of trouble.

And so I had that sort of sitting there when I started to work on this topic. And it enabled me to see this idea of data abstraction. All of a sudden, I sort of saw that this thing I had, this kind of modularity mechanism, which consisted of basically what I just decided. described a bunch of code providing you with an access through a number of what I called operations. So you could call it in various ways and then inside was all hidden and whatever data it was using was not accessible to the outside. And then at some point I saw, I could see this as a data abstraction. It could be a set, it could be a sequence, you know, and so

forth. And that meant we had a new type of module. Now when I look back at the papers from the I see that idea. It's almost there, except people hadn't managed to pick it out. And so it was probably, I think this happens in science a lot. There's sort of a time when an idea is ready, and I happen to see it. You pieced these together and you put it into the Clue programming language that you're working on. How did you see it influencing the industry? The first thing that happened was I wrote a paper with a man who was a graduate student at MIT, Steve Zillis, about this idea of data abstraction, and it sketched a notion of what abstract data types would be

and how a programming language could support them. And this was a very impactful paper. And so there was a big impact on the research community. And then Clue came along, and that involved a lot of additional research in the programming language area. The next thing that happened, so people were watching this

in the research community, but of course people who are in companies that want to write programs, they need a programming language. And I decided I wasn't going to try and turn Clue into a product because that would have required

working in a company. In those days, you didn't just put software out on the internet and people used it. There wasn't an internet, yet, for one thing. And I was much more interested in doing research than in, you know, working in a company. So I put clue on the side. It had a user base. But for companies to use a programming language in those days, they wanted a company behind that language. The next thing that happened was the government put out a call for a programming language they could use. This led to the aid of programming

language. That, so, you know, that was already a big impact, if you think about it, that there was a language explicitly being designed to have data abstraction in it. And then finally, in the 90s, Java came along. I thought it would be interesting because you worked on Clue, you designed that programming language to ask you about other programming languages. You said somewhere that there's something wrong with Python, and I was curious to hear your thoughts of why. Python, has modules, but it doesn't have encapsulation. So it allows code on the outside to muck around with what's going on on the inside of a module. And that's all I was talking about. Encapsulation is a crucial part of making modularity work. And when you're building big programs, so you have many

programmers working on them, your team is really only as strong as your weakest programmer. So it's nice if the compiler can enforce things and make certain kinds of bad behavior not possible. I mean, Python has another intended use. It's helping naive programmers learn quickly how to write programs and stuff like that. And people in the programming language world do think about issues like this, like, you know, how to make languages safer and so forth. But since I stopped working in that area, I'm no longer an expert in programming languages. What got you into distributed computing? I read a paper by Bob Kahn, who was with Vint Cerf, considered to be the founders of the

internet. And Bob talked about his dream of distributed computing, where you would have a program composed of pieces on different computers connected by a network. And nobody knew how to build those programs. And so I just thought, great problem. And I was looking for a new problem. So I jumped into distributed computing. And the first project was actually a programming language to write distributed programs in. And then I started looking at other problems in the distributed systems area. What was that first programming language? It was called Argus. It was very strongly influenced by Clue. It was an object-oriented language. had a special kind of object called a guardian, which was a module sitting at a single computer,

and then guardians could communicate through remote procedure calls. One of the things you run into and distributed computing is if you have a computation that starts at one guardian and then makes use of other guardians at other nodes in the network, in the end, you want that computation to either complete entirely or have no effect at all. And how do you do that? Well, I borrowed the notion of transactions coming out of the database field. And that was part of how Argus worked. It ran computations as atomic transactions. Oh, interesting. Like distributed transactions across those nodes. Yeah. Yeah. And I think it led right into the work I did on view stamp replication, which was, that was the beginning of cloud storage. I was thinking in terms

of a file system, but it doesn't really matter what it is. You know, how do you have data out on the internet stored at multiple sites with correct behavior and always accessible as long as enough nodes are up and running and the network is working? I see. And what is view stamp in this context? Oh, that had to do with some details of how the system worked. And it was a way of noticing when some nodes failed and other nodes had to take over, you could figure out which ones had the most recent state in them. So you could pick up and not lose anything that had happened in the past. What if the clocks are out of sync?

It had nothing to do with clocks because it was just numbers. In other words, we were in view 25. The next view was 26. Oh, okay, just incrementing some number that's passed around. Yeah, yeah, yeah. This reminds me a lot of Leslie Lamport's work. Actually, yes. Did you ever work with him?

No. Leslie and I developed what is essentially the same idea independently. And he had the system he called Paxos, and I had this thing called view stamp replication. Oh, interesting. And they're essentially the same thing. They are, yeah. Are there pros and cons? Are the two approaches?

Yeah. I mean, when you do this kind of system, there's lots of little details you can play around with. So you could, you know, decide to do. It gets technical, but, you know, there's just tiny differences. But, no, they're basically the same. In fact, what happened was the first time that I'm aware of that this was actually used in a real system was when the Google file system came along. and one of my former students who was, I think he was a consultant at Google, looked at what was going on in there and he said, oh, he says, that's FUTAMP replication.

So the people at Google seem to think it was Paxos, but in fact, they are the same system. I also noticed, like, when you came up with abstract data types, maybe, and maybe it's just because the internet wasn't as, you know, wasn't there, that there was also the obvious. object-oriented stuff going on on the West Coast. Yes, Alan Kay was developing small talk at the same time that I was working on Clue. And then at Carnegie Mellon, Bill Wolf and Mary Shaw were working on Alphard, which was another data abstraction language. And you're right, there was no internet, although there was the ARPANET. You know, so we did. But it was like there were two independent streams of research going on, and we weren't talking to each other.

And so I wasn't paying much attention to small talk. And on the West Coast, I don't think they were paying much attention to date abstraction. And this led to the Lyskov Substitution Principle, which, I mean, the story is a sort of acute one, because in 1986, I think it was, I was asked to give a keynote at Uppsla. Uppsla. Uppsla is the object-oriented programming conference, and this was the second year it was happening. happening. And so I decided, I think I'll read all those papers about Small Talk, and there were other languages being developed that were based on Small Talk and see what's going on with them. And I discovered, so Small Talk has this idea of inheritance in it, where you can have a class and a subclass, which borrows from the way the class is implemented and changes it a bit.

And Clue doesn't have that. Clue just has what we call clusters, and they're all independent. So I saw that they were talking about this notion of classes and subclasses. And then I saw that they were also talking about something they called type hierarchy, where they wanted the type implemented by a class to be related in some way that they didn't understand to the type that was implemented by a subclass. I really thought about modules in terms of their specifications. This partly had to do with a class I developed at MIT that I developed jointly with my colleague, John Guttag. And in that class, we taught the students how to do design about modularity, data types, and so forth,

but also how to write specifications, how to reason about correctness. And so it had a big focus on think about the meaning of things first. And the implementation is something that's kind of hidden inside and you don't worry about it very much. And so that was a different way of thinking about things than what was going on in the West Coast, where they were really thinking in terms of classes and subclasses. And I even saw papers where they would describe the behavior of a class by explaining how its implementation was different from the implementation of the superclass. So they were kind of focused on implementations in a way that we weren't. And so when I read these papers about type hierarchy and I saw they just couldn't figure out what it was supposed to mean, I was thinking about it from the terms of meaning.

And so I was able to say it has to do with the behavior. And this subclass better behave like the superclass if you use it in an environment where the superclass is expected. and that became what ended up being called the LISCOS-S substitution principle. And ultimately, Jeanette Wing and I wrote a paper on behavioral subtyping, which is the formal definition. And then how did it get that name? Because you didn't go off on stage and say, hey, everyone, here's the LISCOSCOSC. No, no. But, no, as I said, one day in the 90s after the Internet had arrived, I got an email saying,

can you say if this is the correct interpretation of the LISCoff substitution? principle. That's when I discovered that there was such a name. And I don't think I had really been aware of how important it was until that point, because I wasn't thinking about this stuff. I was working on other stuff. In the academic community, it seems very reasonable to have multiple people have similar ideas, but it seems like some ideas stick more than others. For instance, like the view stamp replication versus Paxos, they're the same thing. I'm wondering, like in that case, for instance, why would Paxos be more known than Vestamp replication?

Yeah. So what Leslie says is, I went around giving all the talks and she implemented it. Really? Something up to that. Then he got notoriety for. Speaking about it. Yeah, he did give lots of talks about it and wrote several papers and so forth. And I didn't realize it was the same system.

But finally, it became clear that they were the same system. I also wonder how much the name matters because Paxos is kind of catchy. It is a cute name. It's a cute name. Yeah, right. So I could see maybe it has better marketing around the idea, I guess. I also think that this approach to solving this problem, which both Leslie and I picked up independently, in my case, came from the work I'd been doing with transactions. Because in transactions, there's a leader that says, now we're going to commit and to ask everybody, can we commit?

And if they all say okay, you know, it's, but unlike in transactions, in transactions, if the leader fails, there's what's called, you know, this can be a real. problem. Here we had to have a way of moving to a new leader if the old leader failed. And that's the big step forward that happened in both VE Stamp replication and Paxos. Now, there was also Byzantine fault tolerance, which came along later that was developed. So View Stamp replication I developed with my student, Brian Oki. It was his PhD thesis. And then Paxos, I developed with my student Miguel Castro, was his PhD student thesis. And Miguel got interested in this problem because there was a DARPA request for proposals. And there was one about this problem on the internet.

By then there were Byzantine attacks and malicious attacks and nodes that were purported to be working correctly, but actually they had been compromised and so forth. And so view stampification in Paxos only handled. crashes and if there were messages that had been played with, you could tell when they arrived that they were bad. And that was about the extent of what we dealt with. But these malicious attacks with nodes that purported to be working when they weren't, that was a big step forward. And Miguel saw this request for proposals and he said to me, why don't we see whether we can come up with a protocol that works in the presence of Byzantine attacks? And

And I think by the way, Leslie is the one that invented the word Byzantine to have. I think he did. Yeah, right. I saw in the software crisis stuff, there's the paper with Dykstra that you had mentioned was one of the papers you wrote that said, we need modularity. And that paper was the go-to statements considered harmful. Right. And I'm curious because Dykstra, I mean, when I was studying computer science, we all know his name. Did you ever meet him or work with him?

Oh, yeah, many times. I never worked with him, but I did meet him multiple times. And, you know, he had very interesting ideas. And that paper, go-to statement, consider harmful, it's not actually a paper. It was a letter to the editor of the communications of the ACM. But it was very impactful. And what was really important about that paper was that Dykstra was talking about how different, it is to reason about the correctness of code. And this was at a time when in the sciences, computer science was kind of dismissed as nothing much, and anybody can write code. And,

you know, Dykstra was trying to make a point, which I think was actually important, that it's not as trivial as you think it is. It's not trivial at all. And he was also pointing out that go-toes can be misused. And it was controversial at the time. It was, yeah. But today, I don't, I mean, I've written code for over a decade. People don't

use go-chis. I haven't even seen a go-to in the go-to. So, why was it controversial at the time? The programming languages were different then. First of all, there were people writing programs in assembler. In assembler, you have to use go-toes.

Programming languages didn't have some of the constructs in them that we think of today. And so some people were using go-toes because they had to. And also, compilers didn't do all the kinds of optimizations that they do today. So there was a concern if you didn't have go-toes, maybe your program wouldn't be efficient enough. And then there were people who used go-toes and wrote really good code and they were offended. That Dypster was saying your code is bad. So there was a whole butt. And Dyckshire was not the most diplomatic person.

So he didn't write it in a nice, you can imagine writing that paper more nicely where you said. So that, but there were many reasons why it was controversial. You know, people were offended, but then there were also concerns about programming languages don't have these features I need. What am I supposed to do? And then there were concerns about what the compiler was doing, and so the world is very different now. But clearly, Dykstra won the day because no go-toes. And is Dykstra in person also like his writing? He was not always as tactful as he might be.

But, you know, he was a very distinguished researcher. Computer science has had such a huge impact on the industry. Why did you choose to stay in academia instead of going into industry? So I like doing research and I enjoy working with students. And teaching was never my favorite thing, but I always felt teaching and research were very closely connected. But also it was a different time. So this business about how professors are all forming companies and so forth, which goes on today, that wasn't happening 20 years ago.

Or maybe it was happening 20 years ago, but 30 years ago it wasn't. So when I was young, it wasn't the thing that you did. It was sort of an either-or sort of thing. So I wasn't even thinking about doing stuff like that. I did work in a startup briefly at the end of the 90s. I didn't like it. I much prefer doing research. And as a professor, you have this, it's a gift and a curse.

The gift is you can do whatever you want. The curse is you have to figure out what it is that you're doing. But I like that freedom and the fact that I just could go off in any, I mean, my career is full of these interesting zigzags where I would switch to something else. I had the freedom to do that. What stops you from going off in a very useless direction? You won't get tenure. Who's the judge? The community.

Yeah, it's not, you know, what, what, the way that you're viewed at your university has mostly to do with, one very important facet of it is how are you viewed in your research community? So because that's one of the important things they want from their faculty if you're in a research university. You mentioned earlier that research and teaching were heavily related in your opinion. But why is that? Because when you teach, you have to teach from first principles. And if you're doing good research, you need to understand deeply what's working, what's not working, what is something. you're making, it's really the same thought process. It sounds like in research, I mean, and this is true in every walk of life, there's the,

I guess the direction that you take and then the work that you do towards that direction. And it sounds like for research, the direction is maybe the most important thing, because you could have a phenomenal researcher doing an idea that has no, even if you did it at 100% it's not going to lead to anything. That's right. So you tell students, graduate students, don't do incremental work.

Don't, you know, you've got, you can't just keep working on the same thing over and over, just making little teeny improvements you need to find. You're right, you have to find a good problem, but you also have to find a problem that's amenable to a solution and one that matches your skill set.

And you have to recognize when you're going in a good direction versus not going in a good direction. Looking back on your career, you say that it was luck and that it seems like things just fit together. I feel there was luck involved.

There was a lot of hard work involved. There was not allowing something negative to, you know, cause you great difficulty. So, for example, when I finished my Ph.D., I would have liked a faculty position, but I didn't have any good offers. So I went back to MITR, the company I had worked for initially, as a researcher. In other words, I just kept on marching along.

And it turned out to be a very good choice because I was switching. from AI to systems, and this gave me, I worked there for four years, gave me four years to make that transition without having to worry about students and teaching and all the other stuff. So it worked out well. But it also meant that I didn't, you know, feel really sorry for myself that I didn't get a job. And then I just kept on going. And then Title IX was about to be passed. And finally, academia was opening up to women. and I was ready. But I think, you know, when I talk to other people about their careers,

they talk about doors opening and doors closing. So I didn't get the academic job I wanted, but I had this other opportunity. I majored in math, and fortunately I was offered a programming job. I mean, doors opened, and then you have to decide am I going to step through. And this is a pattern that people see in their own. careers. It's not just me. Many people have those kinds of choices that you make along the way. Opportunities and things that aren't so great, you know, and you're sort of working your way through.

I've interviewed a few people who have won Turing Awards and I've done research and watched a lot of these speeches that people give after they receive the award. And I noticed something different in in your speech or some of the stuff that I read about your work, which is that in yours, it seems like when you got the Turing Award, there were people saying, why did she get the Turing Award? It was kind of negative commentary on that. And I didn't see that in the other cases. Why do you think that they said that about your work? So I'm not so sure this doesn't happen to other people, by the way. It was just that my husband was out on the internet. By the way, by the way, there was an internet by then.

Okay. Okay. As you know, the internet is not necessarily nice. I know that. Right. And so I can imagine that other people might have had a similar experience, have they bothered to look. But I also think that the world had changed so much. And the work that I had done was so basic.

to what was going on, that people really didn't understand that there was a before. I mean, my graduate students really didn't understand that there was a before because I discovered that at the time I got the award, it really hadn't struck them that data abstraction didn't always exist. So I think that, I mean, I viewed it as, in a way, a huge compliment, not really just to me, but to the group of researchers who, you know, all together got us to the point where we had these modular programming languages and we understood about abstract data types and we understood about how to reason about correctness. All that stuff was so fundamental that people thought

there was no time when it hadn't already existed. So they took it for granted? They took it for granted. I mean, the Byzantine fault tolerance, you look at that, there's a protocol. And you can understand that there was a protocol. Somebody invented that protocol. You know, so you get the credit for that. This was much more fundamental. This was the whole mindset you had about how to develop programs. And that's what people were talking about. And things had changed so much that all these inventions of mine and others were just there in the woodwork and people didn't realize that there was a time before. That's validating then.

Yeah. It's so impactful and everyone uses it all the time that they don't even know what it was like before what you did. So I thought, you know, it's a huge, the person who said it didn't mean it nicely, but I thought really it's a huge, a huge compliment and a statement about where we are now as opposed to where we were then. So. Okay.

Well, that's all the questions I have for you. Thank you so much for. for your time. I really appreciate it. You're welcome. Thank you for listening to the podcast. It's a passion project of mine that I really enjoyed building. Another passion project that I've been working on kind of in secret is building an ergonomic keyboard that I wish existed and I finally have a prototype so I'd love to show you what we've built. It's ultra low profile and ergonomic and I couldn't find anything like it on the market. So that's why we built it. I'll put a link to the keyboard in the description. You can take a look and learn more about the project there.

we could definitely use your support. Also, if you have any feedback for me about the show, I'd love to hear it. Comments on YouTube have led to guests coming on like Ilya Gregorik and David Fowler. I wasn't aware of them until someone dropped a comment. Also, feedback in the comments helped me learn to reduce the number of cliffhangers in the intros. So your comments definitely make a difference. Please keep letting me know what you'd like to see more of in the show, and I'll see you in the next episode.