Leslie Lamport on the Science of Distributed Systems

Transcript

So, you're going to have a distributed system, some of those computers are going to fail. So, you want to make it fault tolerant. The general problem is really getting multiple processes to all be doing the same thing. There is an unsolvable problem that's being solved. [music] The problem that Axos has is it's implementing a state machine, but that with failures, it could take forever for the computers to come to a decision. I said, "Oh, that doesn't sound very hard." I had the idea that you didn't really need digital signatures. What you needed was a signature that it would be very unlikely for a failed computer to produce.

>> Do you have a recipe of how you find problems that are practical where you think you can develop important theory for it? >> Well, one thing that helped me at the beginning was >> [music] >> Hi everyone, and welcome to First Principles, a series by the team at a16z crypto. I'm Tim Roughgarden, head of research at a16z crypto. Our guest today is going to be Dr. Leslie Lamport, the Turing Award-winning computer scientist who, among many other research contributions, first formalized the problem of agreement in distributed systems, the so-called Byzantine Generals Problem, which captures the

difficulty of reaching consensus when some participants may fail or act unpredictably. So, through this and his work on logical clocks, state machine replication, and the Paxos consensus protocol, Dr. Lamport helped to lay much of the theoretical groundwork for modern distributed computing, from cloud infrastructure to the consensus layers beneath today's blockchains. So, I'm joined by a16z crypto research partner Etay Abraham as we talk with Dr. Lamport about how these ideas emerged and why careful specification and reasoning remain essential as systems grow more complex.

Here's our conversation. Dr. Lamport, welcome and and thanks so much for taking time to speak to us. We we really appreciate it. So um researchers and engineers who work with blockchain protocols are very familiar with much of your work in distributed algorithms, which is extremely important in that application area. I think that audience may be a little less familiar about the work you were doing that perhaps was a precursor to the work they do know around uh concurrency. And so I thought maybe we could start the conversation um by just setting the stage for what you were thinking about in the early '70s leading up to your work the the initial work in distributed algorithms in the in the mid to late '70s. So, for example, um you know, the time clocks and and the

ordering of events paper. Was that sort of a natural segue for you from the work you were doing around concurrency? >> So, I guess the real question is how I got interested in concurrency. And the answer is simple enough. In 1972, I joined the ACM. I think it was probably my first issue of a CACM of had an algorithm for solving the mutual exclusion problem. Basically, uh you have say a bunch of processes in a computer who want to share a resource say a printer.

Back in the days when printers were really uh you sent one line at a time to the printer. If two processes were doing that, uh you wouldn't like what you got. So, uh the problem was how to get multiple processes synchronized in such a way that they each has a critical section and at most one process can be in this critical section at the same time. And the problem was originally posed by Edsger Dijkstra, who really started the modern study of concurrency.

There was a a solution to that problem uh in CACM, and I thought that, "Well, yeah, that seemed awfully complicated. Should be easier to do." So, I whipped off a uh simple solution for two processes and sent it off to CACM, and a couple of weeks later I got back a letter from the editor uh pointing out where the bug in my algorithm was. And this had two effects. Uh the first was it made me realize how tricky it is uh how concurrency is and how you really have to be uh essentially be able to prove the correctness of a concurrent algorithm.

And the second was, you know, I was just going to solve that damn problem. And uh the result of that was the uh bakery algorithm. Now, the thing that interests me about it was that uh I basically started out as a programmer, and I you know, like solving interesting little programming problems. And uh concurrency made problems much more interesting, you know, much more fun. So, it's what I got into. And the bakery algorithm itself, implementing it involved certain problems, but and basically it got me thinking about concurrency.

And I'd say that, you know, maybe for the next two or three years, everything that I did directly followed from the bakery algorithm. And that's how I got started. >> And so, what led to uh sort of the either change in scope or sort of the increase in your interests beyond just thinking about multiple processes uh on a single machine to thinking about multiple machines, to thinking about algorithms that uh are distributed. >> Yeah, I think it was 1978. I really discovered that there was no difference between the two for reasons after writing the times clocks paper.

It made me think that I had to write a correctness proof for a distributed algorithm. Um and because time clocks made me think that oh, you need to think about distributed systems in a very different way. The way I was doing for you know, multi-process algorithms you know, shouldn't work and you know, I tried a bunch of things and they weren't working and I uh I was writing uh a final report for a project under a government contract that SRI and the promise was we'd write a correctness proof of this distributed algorithm.

And finally, I just gave up and said, oh, what the hell, I'll just do it the way I know how to do it for uh uh non-distributed concurrent systems uh and it's not going to be really good, but it'll be you know, I'll get it done. And so, when I did it, I realized that it worked perfectly. And it was exactly the right way to reason about that distributed algorithm. And that's when I learned that there's no basic difference in how you reason about the non-distributed versus distributed concurrent algorithms.

>> That's fascinating. Is that distributed algorithm and the correctness proof, is that public domain? Is that from one of your published papers or >> Oh, yeah, I published that algorithm uh I think it's in 1978, but it's something like has a title like correctness proof of a distributed algorithm. >> So, that's the I I I wonder you mentioned multiple times uh proving correctness and thinking about correctness of of algorithms. Can you say a little bit about what what that means? What does it mean that a protocol is correct? >> Basically, it took me uh till about 1990 to understand or realize, you know, what correctness means.

It started off with properties that was you know, fairly simple like mutual exclusion. Please to state no two processes are ever in their critical section at the same time. And the time clock paper was brought about which started my interest in distributed systems. I never, you know, thought of them particularly when two I guess they'd be called computer scientists. They wrote a paper about uh maintaining consistency in a distributed database.

That is when you have uh multiple copies of the database and making sure that all the copies are consistent. One has a general idea of what that means although when you start trying to state, you know, make it really precise it gets a little hard. But at any rate, well, their algorithm I realized didn't satisfy causality in the sense that one command that preceded another command in another part of the system those commands could be executed out of order, you know, out of the order in which they were actually submitted.

And um I fixed the algorithm and that was you know, the the algorithm that was in the uh time clocks paper. But I realized and what seemed to me to be completely obvious is that there was nothing special about you know, the particular problem of distributed databases that the general problem is is really getting multiple processes to all be doing the same thing and the obvious way to describe what they were doing was with a state machine.

That is all the processes were executing the same state machine and where state machine basically is something that has a state and commands come in and each command produces an output and changes the state. I realized that if you could do that, you can basically implement anything in a distributed system. And in fact, I uh what I realized relatively recently is that abstracting from your duplicate databases to an arbitrary system that involves abstraction.

And I happen to be much better at abstraction than most people. It's what Dijkstra wrote a paper with some colleagues colleagues on the concurrent garbage collector. That is a garbage collector that operates in parallel with the program that's creating the garbage. And I made a observation which I thought was pretty obvious that the algorithm could be simplified because it had two data structures, one the data structure that you had to collect garbage from and another one which was the free list.

And I realized that it was quite easy to make the free list part of that same structure. Dijkstra made me an an author on the paper for producing that and apparently that was an abstraction that Dijkstra hadn't thought of. And if something that Dijkstra hadn't thought of is not going to be obvious to many people. And in the time clocks paper, I think that really the most important thing uh is that introducing the notion of of implementing a distributed system as a state machine.

>> And indeed the the state machine abstraction and just the articulation of state machine replication as a as a problem has been It's very, very central in blockchain protocol design. You can really view modern blockchain protocols like Ethereum and Solana as sort of aspiring to solving uh the general version of state machine replication. So, very, very important work. I'd love to turn a little bit to sort of the next chapters in your work on distributed algorithms. So, for example, the famous Byzantine Generals Problem um paper and then also later the Part-Time Parliament or or Paxos. And in particular, I'd love to hear more about, you know, what led you to introduce the notion of fault tolerance and in particular the notion of Byzantine faults

as opposed to perhaps, you know, something like crash faults or some simpler notion of of machine failure. >> Well, again, that seems a very a very obvious thing to do. Uh, you know, having Lamport time clocks, which was an algorithm for implementing a state machine, but with no fault tolerance. And it's obvious that if you're going to have a distributed system, some of those computers are going to fail. So, you want to make it fault tolerant. And as far as Byzantine faults, well, at that time, there was no notion of what a fault might be, you know? And so, I just said, "Well, I'll just take the the most general fault that a uh failed process

could do anything." I, you know, I wrote an algorithm that that solved that problem, uh but it uh assumed that digital signatures. Now, I was one of the the few people in the world who happened to have heard about digital signatures because Whitfield Diffie was a friend of mine. Whit was one of the uh founders of modern, I guess you'd call civilian cryptography. We were sitting at uh at a coffeehouse in Berkeley around '76.

I don't remember the exact date. He and and Marty Hellman had the problem of, you know, the need for digital signatures. But they didn't have an algorithm for them. And I said, "Oh, that doesn't sound very hard." So I just wrote literally on a napkin and then a simple algorithm uh for writing digital signatures. For the purposes of my of fault tolerance, I had the idea that you didn't really need digital signatures. What you needed was a signature that it would be very unlikely for a failed computer to produce.

And I thought that that should be pretty easy simple engineering problem to to do that. Then I went to uh SRI. It was a research project uh for NASA. They knew that future airplanes uh pilots wouldn't be able to fly them that they need a computer because the pilot couldn't react fast enough to what had to be done. And so as a research project, they were building a multiple computer system for flying an airplane.

And they figured again, they didn't know what a failed computer could do. So and since they needed real high reliability, they had to assume that it could do anything and therefore they were faced with again the Byzantine generals problem. They they probably hadn't heard of digital signatures at the time. So they came out with an algorithm that didn't need them. I was with digital signatures, you know, you could tolerate n faults with 2n + 1 computers. But without digital signatures, you needed 3n + 1 computers.

For reasons that I've never understood, you know, people building airplanes decided that oh, they needed 3N + 1 computers because they would seem to think that, you know, digital signatures were impractical. But, I thought they should be practical if you're not worried about malicious opponents, but random failures. The people at SRI when, you know, when they were trying to solve the problem, you know, they tried to come up with solutions that weren't provably correct, but they would say, "Oh, that could not happen in practice."

They would be able to construct some kind of failure that was not so implausible that could break the algorithm. And Rob Shostak was one of the people who were working on that, and Marshall Pease and Michael Melliar-Smith I think were the other ones. So, I don't know who actually came up with the uh algorithm for was hailing a single failure, which required four processors. But, the uh one for the general one for N was discovered by Marshall Pease, and that was uh an amazing uh amazingly brilliant because it was so difficult to understand. Later on, I found a a way to describe

uh his algorithm recursively. That is, describe the N process one, you know, recursively in terms of the N - 1 process one. Uh and that made it understandable, but he didn't have that that trick. And so, he did it by sheer brainpower. So, anyway, so that's how, you know, Byzantine Generals came to be. And of course, you know, once uh hackers, you know, started appearing on the scene, then it was obvious that really did need to uh Byzantine fault tolerance.

>> Absolutely. And 2025 is is literally the right model for how some of these distributed protocols are being attacked. So just again an amazing power of abstraction is ultimately capturing you know exactly what the problem is in in some future generation of the technology. So to wrap up sort of the discussion of of these fundamental works in distributed algorithms, I wanted to chat a little bit about the evolution of how you thought about communication network reliability or message delays and asynchrony, which is something that plays an important role in the Part-Time Parliament paper.

So what led you to to to think about more relaxed models of communication between the different the different machines? >> I'm not sure. I mean I I know exactly where Paxos came from. I was working at that time at the Systems Research Center at Digital. And the people there had a a local area network and they believed that failures would just be a computer would just die, would just crash. They weren't worried about Byzantine behavior.

I was convinced that well, what they were trying to do was impossible. You know, that there did not exist an algorithm that would have the features that they claimed that their program had. So I started out trying to write an impossibility proof. But instead of an impossibility proof, I wound up with an algorithm. And that's how Paxos came to be. Actually, the problem that was impossible was the impossibility a result of Fisher, Lynch, and Patterson in terms of their paper, you know, there is an unsolvable problem that's being solved.

It can't be solved without the use of clocks. And so the the problem that Paxos has is in principle basically it's implementing a state machine, but that with failures, it could take forever for the computers to come to a decision. Uh and what Paxos does is an algorithm that makes it highly unlikely that that will happen. And so, it gives up liveness in principle, but maintains safety.

And uh and the probability of not making a decision forever is is just, you know, negligible. And so, it works in practice. >> Yeah, I I I think Paxos went through this uh story about legislators, right? They're trying to reach agreement on uh on a ledger of a >> Yeah, well, I learned something uh years earlier. It's phrased in terms of uh some bunch of philosophers dining a a round a table, and there's one chopstick between each uh pair of of philosophers are sitting around a round table.

And it requires two chopsticks in order to eat. Problem was, how do you make a an algorithm that keeps everybody from starving and, you know, lets each person eventually be able to to eat. And I've never found that problem so interesting. I think that people were aware of that problem because it had this story attached to it. And so, when we discovered the the Byzantine uh generals results, I realized that that was important.

And to make people aware of it, I thought there would should be a nice story behind it. And that's how the Byzantine generals came about. Uh well, I was successful with that that when Paxos came around, I tried to do the same thing and that was a flop. I just did a a terrible job of it and it just confused people and put them off rather than uh making it uh you know, accessible. And so, the significance of that paper was understood by very few people. One of them was, fortunately, Butler Lampson who went around uh popularizing it.

And uh the referee said that this paper, well it's not very interesting, but it's worth publishing but then you can get rid of all this uh Paxos stuff. And you know, that up- annoyed me, so I just put the paper aside. And uh when it became clear of how, you know, that was important, uh I uh got it published with the Paxos stuff. >> So, so in some sense, the uh the condition for liveness, for success uh in the Paxos algorithm, is that uh all these legislators or a majority of them are actually inside this chamber where communication is synchronous. So, I wonder, was that kind of uh how did you come up with that that

abstract? I mean, by the way, that is essentially the abstraction that is now used by uh almost all uh distributed systems. >> You know, there's nothing about that in the paper, you know, talking about synchrony, asynchrony, or anything like that. It's just uh you know, gives the algorithm. And in order for the algorithm to work, you have to have this this condition. And I suppose people >> [snorts] >> you know, gave a name to the condition or whatever, but I don't I don't know how that happened.

>> But in some sense, it was kind of you were trying to prove a lower bound saying it's impossible and you said, "Oh, actually, if this thing happens, then I can make progress." Is that kind of how how things evolved? >> I mean, I thought it was impossible maintaining uh safety would be impossible even if you didn't you know worry about liveliness. On the other hand, you know, it was it was sort of clear that with the kinds of failures that people were thinking about, you know, one process just dies and the others keep going and then can communicate reasonably.

That was just a natural assumption to make and this was now going to you know just for real engineers to to work uh to to build real systems and you know, real engineers are not worried about the kinds of highly unlikely uh failures that would uh defeat Paxos. >> That may be a good point to um talk a little bit about the interplay between theory and practice through this through the sequence of works cuz you know, Dr. Lamport, you've mentioned you know, enjoying programming puzzles and we've talked a lot about the importance of mathematical formalism and abstraction. At the same time, you've told several stories about talking

engineers, looking at existing code at existing attempts at at solving perhaps not yet articulated problems and it's remarkable. You know, a number of your works on the one hand, you look at them and they're in some sense a theory paper, but [snorts] the practical impact has been massive. So, I'm curious if you could speak just a little bit, you know, why have you been so successful in in combining these two things and do you have a do you have a recipe of how you find problems that are practical where you think you can develop important theory for it? What else would you advise the next generation who who wants to do work along those same lines?

>> Well, one thing that helped me at certainly at the beginning was a lot of the people you know, who were working in those early days they seem to be thinking in in terms of programming languages or in terms of mathematical theories. And it always seemed to me that since concurrency is in some sense more of a physics problem than either a language or a a mathematical problem. You know, [snorts] like mutual exclusion. You know, two things not happening at the same time. Same time, that's physics.

And so I've just really thought in terms of real uh things. For instance, in the early days people would talk say they'd solve the mutual exclusion problem by inventing some language construct that would implement mutual exclusion. And you know that's to me was not solving mutual exclusion. So, I've guess I've always had a sense of whether some problem makes sense in terms of you know real computers, real you know, electrons flowing or whatever.

I guess you know, for a problem to interest me, I guess I usually always had some physical situation where it seemed to it to make sense. >> I'm curious if if working largely in the milieu of a industrial research lab played an important role in this as opposed to say being in academia. Was that important? >> Well, I've always used to say so. I mean, I've some problems, you know, came to me because some engineer or programmer, you know, had this problem to solve like uh disk Paxos uh for example, that came because he didn't want to use more than you know, two computers, but you know, he wouldn't be able to use three or four disks.

And his autobiography uh Jean Renoir who's the son of August Renoir, the famous painter said that his father had told him that when asked why he went and carrying looking all this stuff instead of painting in the in the studio was that he said well, if I was in my studio and was going to draw a tree, I you know, I might be able to come up with, you know, five or six different kinds of of leaves.

But you go out in nature and there are thousands of different kinds of leaves. That's my explanation of why I like the you know, working in a company that's you know, actually building things. >> I think that's an amazing and deep analogy. That's great. >> I think that that distinction between uh academia and industry in terms of you know, practicality and stuff that gap has has has closed uh a lot since the days when I was was doing that stuff. >> So great. So perhaps moving on to the just briefly at least the topic of abstraction and Dr.

Lamport you already in some sense alluded to the answer to this, but Don Knuth has said on many occasions that 2% of the population is meant to be programmers. And I'm curious what you think of that quote and perhaps also if we substitute the word abstraction for programming in that quote or alternatively is it something that can to some extent be be taught? >> Well, you know, I've devoted much of the end of my career uh to getting programmers or I would say more system designers than uh you know, average programmers to be able to abstract and you know, to think more abstractly about what they're

doing. My understanding of of how one should reason about concurrent programs and concurrent algorithms led me to develop a language called TLA+ I will say I've got enough experience to say that very good uh engineers will by using TLA+ improve their ability to abstract and make them better designers.

>> And so maybe this is a good segue into I believe you have a a coming book, A Science of Concurrent Programs. I would love it if you could speak a little bit about that and and the goals of the book. >> The goal of the book is very simple. I've worked as I said starting well really in some sense starting from uh 1975 or so when I wrote this first paper on proving correctness of multiprocess uh programs. You know, I'm figuring out how to a state very precisely what what the problem is, what the you want the algorithm to do

and describing the algorithm precisely and being able to show that mathematically and with tools that this algorithm satisfies the correctness property that it should. Basically, the book is putting all that in one place you know, pretty much everything that I learned about the theory uh behind it. It's not about you know, how to use it in practice, but it's about the underlying theory.

>> And this is on Cambridge University Press, is that right? >> That's they promised to to uh publish it and the last they said their goal was in March. >> Fantastic. So, Dr. Lamport, thank thank you again for the time. Really appreciate you you speaking to us. >> Okay, it's my pleasure. I had fun uh >> Fantastic. Well, that was pretty amazing hearing from both Leslie Lamport and Barbara Liskov. I thought maybe we could circle back on on something we talked about the power of you know mathematical abstraction of sort of real systems and sort of the feedback loop between practice and and theory. And I I do feel like that came out pretty explicitly in both of the interviews.

>> Yeah, I thought both both of them focused on these deep connections between the practical work that they've done and the theoretical underpinning, correctness proofs, and the way that they thought about distributed systems through kind of a mental model that looks a lot like how we think about mathematics sometimes. I think Barbara talked about this mathematical hierarchy of a theorem that has lemmas and sub lemmas and so on. So the analog here is that you look at a system, you don't think about it as a monolithic system, but you kind of look at it as a series of encapsulations and abstractions. And that's extremely important because these distributed systems are very very complicated. So if you just kind of you know just think about this as like a whole lump of of system or of math then it's very very hard to understand what's

happening. Yeah. >> Yeah, your head explodes, yeah. >> And they built extremely complicated systems, right? So if you look at PBFT, this is like a huge endeavor and really this power of abstractions what enabled that. And and this pattern, right? Of abstraction and encapsulation is like a core factor of how distributed systems are built today. >> I mean arguably it's like at the very center of computer science as as a discipline. >> Yep, yep. >> I mean in addition to just how the overall themes there were such strong parallels. I mean it was wild how their actual work also converged at least at particular points. We heard from Dr.

Lamport about you know Paxos, we heard from Dr. Liskov about you know view stamp replication. It's probably sometimes you know ideas there's just like the right time for them and sometimes it's because you actually lacked kind of the tools to come to the idea. Sometimes sometimes it's an idea that in principle all the tools were available 10 years prior, but somehow it was just there's a right moment in time for this idea to emerge. It's something even you know after 25 or whatever years of of doing this I still find, I must say, a little bit mysterious.

>> Yeah, this is kind of a fascinating aspect of the academic world, for sure. >> Another thing that I thought was an interesting parallel, you know, the interplay between theory and practice, but you know, their career paths are on paper somewhat different, right? So, they somehow both really leaned into the synergy between those two things, but in different ways. >> I would say, uh, Barbara Liskov, she was kind of a one of the founders, I guess, of systems research in computer science, I industrial systems. So, you know, she was at at MIT working with a lot of students and and trying to build systems. And kind of on the other side, Leslie Lamport spent his whole career in industrial research. So, he was kind of, you know, doing a a lot of theoretical work, but but being very connected to engineers, uh, and and kind of talking

to systems researchers and and people who built, uh, large systems. So, both of them worked on the interface of, I guess, theory and systems, and trying to build things and working with with builders, but both of them came from kind of different very different career paths. Uh, so, it's interesting to see how different influences kind of, uh, push you to different directions. >> Yeah. Though, in both cases, it was, you know, US government funding for different projects that wound up being pretty important, right? So, Dr. Lamport mentioned NASA, he mentioned SRI, and then Dr. Liskov talked about sort of a big DARPA announcement. So, that was sort of a also a common theme for both of them about where some of the problems that they worked on and the motivation for them came from.

>> DARPA was kind of this huge, uh, force in the academic world. In the sense, you could think about, uh, the internet, right? As coming from DARPA pushed, uh, use cases, and then maybe flourish through kind of economic, uh, incentives. >> I'm sure as most listeners know, the original internet was actually called the ARPANET because, uh, it was a ARPA project, ARPA being the precursor to to DARPA. >> Yeah, yeah. And, you know, Byzantine agreements might have the same type of path in a way. It was kind of, uh, pushed by DARPA as a focus for survivability. They really cared about this notion of having large-scale distributed systems that survive attacks or would survive failures or would survive even if part of the system, you know, got destroyed or got maliciously attacked. And it's actually fascinating to see that this technology is now being used for in a for economic use, right?

In in blockchain technologies. So, it's kind of you know, the same type of pattern of a movement of technology from, I would say, you know, government focused funding to kind of economic value. >> I mean, it also just shows I mean, we've seen this over and over and over again, but I mean, blockchain technology just alone has multiple instances of where the decades long, even kind of half century long time scale is like the one at which sort of really sort of fundamental breakthrough ideas emerge, right? Which is just if you're not sort of working with this stuff day-to-day, it can kind of be sometimes hard to see, okay, where is this going? What's the payoff going to be? But it's it's a very long-term game, fundamental research. And and I think that came through very strongly today.

>> Yeah, who knows? Maybe this notion of survivability of systems will actually become very important in the future as well. So, you know, you might see technology go back from, you know, blockchain technologies back to focus on survivability of systems. >> That's a great point cuz that's something again, you know, I mentioned cryptography and SNARKs earlier and that's sort of another example where blockchain technology, I think is really pushing the state of the art with SNARK design, but a lot of the applications of SNARKs are outside of blockchain technology. So, as much as blockchain technology has stood on the shoulders of ideas of other parts of computer science, engineering, I do think it's reaching a maturity state where it's giving gifts back, kind of returning the favor, which has been a very cool development.

>> Yeah, absolutely. >> All right. So, it's I thank you for joining us to co-host. Super super fun. >> Thank you for having me. This was this was a lot of fun. This was a lot of fun. Yeah, we should do this more. >> We should. We should. Let's work on that. >> let's do it.