Before Blockchains, There Was State Machine Replication (ft. Barbara Liskov and Tim Roughgarden)

**Barbara Liskov** (0:00)
DARPA had recognized that this was a serious problem, the problem of malicious attacks, and was looking for research in that area. I had a student, Miguel Castro, he came to me and he said, why don't we see whether we can figure out a way to do replication that handles these malicious attacks? And that seemed like a great idea. The problem, if the primary failed, the primary that was running the protocol, the whole thing came to a crashing halt. We came up with a protocol that if the primary seemed to not be doing its job, the backups then carried out another protocol in which a different replica became the primary. We thought that at some point, people would start to use this. And then along came blockchains.
And so that was very funny.

**Tim Roughgarden** (0:45)
Someone who loves computer science, loves research, wants to do important work, wants to have an impact. What would you suggest as kind of a mindset, as an approach?

**Barbara Liskov** (0:53)
Computer science is in a very strange place right now. With the advent of AI, I think that as far as research is concerned.

**Tim Roughgarden** (1:10)
Hi, everyone, and welcome to First Principles, a series by the team at a16z crypto. I'm Tim Roughgarden. I'm the head of research at a16z crypto. And today we're exploring a core challenge in distributed computing. How can a system remain reliable when some of its parts fail or behave maliciously?
In this episode, we're going to speak with the Turing Award-winning computer scientist whose work helped answer this question, Dr. Barbara Liskov. She's famous for many things, but today we're going to focus on her work that laid the foundations for modern blockchain systems. For example, from view standard replication from the 1980s to practical Byzantine fault tolerance or PBFT a decade later.
A16z crypto research partner, Ittai Abraham, joins me as we talk with Dr. Liskov about her path from programming languages to distributed systems, the evolution of practical replication protocols, the state machine replication paradigm underlying blockchains and how emerging technologies like AI are reshaping systems research. Here's our conversation. Professor Liskov, thanks so much for joining us for the conversation today. I really appreciate you taking the time.

**Barbara Liskov** (2:22)
Sure.

**Tim Roughgarden** (2:22)
I thought maybe it would be fun to start to just discuss a little bit about how you got into distributed systems research, which my understanding was maybe around 1980 or so, especially given that throughout the 1970s, you did a lot of extremely important work on other topics, operating systems, programming languages, data abstraction. Why this segue into distributed systems around that time?

**Barbara Liskov** (2:45)
What happened was I had finished working on Clue, which was the programming language that I developed with my group to provide access to data abstraction as a way of building programs.
I had thought a little bit about maybe starting a company to market the language, but I realized that I was much more interested in research. I also thought that I had done as much programming language research as I had anything interesting to do at that point. I started looking around and I read a paper by Bob Kahn, in which he talked about the dream of distributed computing and how there would be distributed programs that had components at different nodes in a network and communicated over the network, and only nobody knew how to build them. So I thought, there's a great problem. So I jumped into distributed computing.

**Tim Roughgarden** (3:49)
Wow, fantastic.

**Barbara Liskov** (3:50)
It was a great move.

**Tim Roughgarden** (3:52)
Well, it was great for computer science that that happened, that about it. I'm curious, did it feel like a pivot at the time, like you were really changing your research field? And maybe a related question would be, how much did sort of the mindset and the approach to abstraction that you developed early in your career, how much did that port over, versus how much did you need to really have a new sort of toolbox for working on those problems?

**Barbara Liskov** (4:13)
Well, I may have thought of it as a pivot, but my first project there was a programming language. And that programming language was really an extension of the language I had already developed. We had this language called Clue, which supported abstract data types and objects. And in Argus, which was the new language, we had abstract data types, and then we had one additional feature, this new kind of object, which we called a guardian. And the idea with the guardian was it resided at one node of a network. It provided operations that could be called from other nodes. And so the idea was a distributed program consisted of all these guardians, each running on its node, communicating with each other.