# Distributed Systems Theory Drives Modern Infrastructure

**Podcast:** web3 with a16z crypto
**Published:** 2026-06-25

## Transcript

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.
The general problem is really getting...
multiple processes to all be doing the same thing.
There is an unsolvable problem that's being solved.
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...
Hi, everyone, and welcome to First Principles, a series by the team at A16Z Crypto.
I'm Tim Roughgarden, head of research at A16C 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, Itai 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 thanks so much for taking the time to speak to us.
We really appreciate it.
So, 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 concurrency.
And so I thought maybe we could start the conversation by just setting the stage for what you were thinking about in the early 70s, leading up to your work, the initial work in distributed algorithms in the mid to late 70s.
So, for example, you know, the time clocks 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 CACM had an algorithm for solving the mutual exclusion problem.
Basically, 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, you sent one line at a time to the printer, and if two processes were doing that, you wouldn't like what you got.
So the problem was how to get multiple processes synchronized in such a way that each has a critical section, and at most one process can be in its critical section at the same time.
And the problem was originally posed by Edziger Dijkstra, who really started the modern study of concurrency.
There was a solution to that problem in CACM, and I thought that, boy, that seemed awfully complicated.
It should be easier to do, so I...
Whipped off a simple solution for two processes and sent it off to the CACM.
And a couple of weeks later, I got back a letter from the editor pointing out where the bug in my algorithm was.
And this had two effects.
The first was it made me realize how tricky it is, how concurrency is, and how you really have to be 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 the result of that was the bakery algorithm.
Now, the thing that interests me about it was that I basically started out as a programmer.
And I, you know, like solve interesting little programming problems.
And concurrency made problems much more interesting, you know, much more fun.
So that's what I got into.
And the bakery algorithm itself, implementing it, involved certain problems.
But 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 sort of the...
either change in scope or sort of the increase in your interests beyond just thinking about multiple processes on a single machine to thinking about multiple machines, to thinking about algorithms that 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-Clock's paper, it made me think that I had to write a correctness proof for a distributed algorithm.
And because time clocks maybe 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 was writing a final report for a project under a government contract at 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 non-distributed concurrent systems.
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.
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 non-distributed or 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?
Oh, yeah.
I published that algorithm.
I think it's in 1978, but it's something like, has a title like Correctness Proof of a Distributed Algorithm.
So, Leslie, I wonder, you mentioned multiple times proving correctness and thinking about correctness of algorithms.
Can you say a little bit about what that means?
What does it mean that a protocol is correct?
Basically, it took me until about 1990 to understand or realize, you know, what correctness means.
It started off with properties that was fairly simple, like mutual exclusion.
Easy 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 thought of them particularly.
I guess they'd be called computer scientists.
They wrote a paper about maintaining consistency in a distributed database.
That is when you have 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 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, out of the order in which they were actually submitted.
And I fixed the algorithm, and that was the algorithm that was in the Time Clocks paper.
But I realized, and what seemed to me to be, completely obvious is that there was nothing special about the particular problem of distributed databases.
That the general problem 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 a 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, 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.
Edswood Dijkstra wrote a paper with some colleagues on a 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 author on the paper for producing that.
And apparently that was an abstraction that Dijkstra hadn't thought of.
Something that Dijkstra hadn't thought of is not going to be obvious to many people.
And in the Time Clarks paper, I think that really the most important thing is that introducing the notion of implementing a distributed system as a state machine.
And indeed, the state machine abstraction and just the articulation of state machine replication 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 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 paper, and then also later the part-time parliament 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 machine failure.
Well, again, that seems a very obvious thing to do.
You know, having runtime 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.
And so I just said, well, I'll just take the most general fault that a failed process could do anything.
I wrote an algorithm that solved that problem, but it assumed digital signatures.
I was one of 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 founders of modern, I guess we'd call it, Sylvelyan cryptography.
We were sitting at a coffee house in Berkeley around 76.
I don't remember the exact date.
He 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 for writing digital signatures.
For the purposes of my 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, a simple engineering problem to do that.
Then I went to SRI.
It was a research project for NASA.
They knew that future airplanes, 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.
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 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 plus 1 computers.
But without digital signatures, you needed 3N plus 1 computers.
For reasons that I've never understood, you know, people building airplanes decided that, oh, they needed 3N plus 1 computers because they would.
seemed to think that digital signatures were impractical, but I thought they should be practical if you're not worried about malicious opponents, but random failures.
People at SRI, when they were trying to solve the problem, they tried to come up with solutions that weren't proofably 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 Melior-Smith, I think, was the other one.
So I don't know who actually came up with the algorithm for handling a single failure, which required four processes.
But the one for the general one for N was discover of my Marshall Pease, and that was...
Amazingly brilliant because it was so difficult to understand.
Later on, I found a way to describe his algorithm recursively.
That is, describe the end process one recursively in terms of the n-1 process one.
And that made it understandable.
But he didn't have that trick.
And so he did it by sheer.
Anyway, so that's how Byzantine generals came to be.
And of course, once hackers started appearing on the scene, then it was obvious that it really did need Byzantine fault tolerance.
Absolutely.
In 2025, it's 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 some future generation of the technology.
So to wrap up sort of the discussion of these fundamental works and 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 think about more relaxed?
models of communication between the different machines?
I'm not sure.
I mean, 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 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 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.
You know, that's how Paxos came to be.
Actually, the problem that was impossible was the impossibility 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 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.
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 the probability of not making the decision forever is just negligible.
And so it works in practice.
Yeah, I think Paxos went through this story about legislators.
They're trying to...
reach agreement on a ledger.
Yeah, well, I learned something years earlier.
It's phrased in terms of some bunch of philosophers dining around a table, and there's one chopstick between each pair of philosophers sitting around a round table, and it requires two chopsticks in order to eat.
The problem was, how do you make an algorithm that keeps everybody from starving and lets each person eventually be able to eat.
And I 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 Byzantine general's results, I realized that that was important.
To make people aware of it, I thought there should be a nice story behind it.
And that's how the Byzantine generals came about.
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 terrible job of it, and it just confused people and put them off rather than making it.
accessible.
And so the significance of that paper was understood by very few people.
One of them was fortunately Butler Lampson, who went around popularizing it.
And the referees said that this paper, well, it's not very interesting, but it's worth publishing, but then you get rid of all this Paxos stuff.
And that annoyed me, so I just put the paper aside.
When it became clear how, you know, that it was important, I got it published with the Paxos stuff.
So in some sense, the condition for liveness, for success in the Paxos algorithm, is that all these legislators, or a majority of them, are actually inside this chamber where communication is synchronous.
So I wonder, was that kind of a, how did you come up with that?
I mean, by the way, that is essentially the abstraction that is now used by...
almost all distributed systems.
You know, there's nothing about that in the paper, talking about synchrony, asynchrony, or anything like that.
It's just, you know, gives the algorithm, and in order for the algorithm to work, you have to have this condition.
And I suppose people, you know, gave a name to the condition or whatever, but I don't know how that happened.
But in some sense, it was kind of, you were trying to prove a lower balance, saying it's impossible.
Then you said, oh, actually, if this thing happens, then I can make progress.
Is that kind of how things evolved?
I mean, I thought it was impossible.
Maintaining safety would be impossible, even if you didn't worry about liveness.
On the other hand, it was sort of clear that with the kinds of failures that people were thinking about.
One process just dies and others keep going and can communicate reasonably.
That was just the natural assumption to make.
This was an algorithm for real engineers to build real systems.
Real engineers are not worried about the kinds of highly unlikely failures that would defeat Paxos.
That may be a good point to talk a little bit about the interplay between theory and practice through this sequence of works.
Because, Dr.
Lamport, you've mentioned 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 to engineers, looking at existing code, existing attempts at solving perhaps not yet articulated problems.
And it's...
Remarkable.
A number of your works, on the one hand, you look at them and they're in some sense a theory paper, but 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 combining these two things?
And 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 wants to do work along those same lines?
helped me, certainly at the beginning, was a lot of the people, you know, who were working in those early days, they seemed to be thinking 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 mathematical problem, you know, 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 things.
For instance, in the early days, people would talk, say they'd solved the mutual exclusion problem by inventing some language construct that would implement mutual exclusion.
And, you know, that to me was not solving mutual exclusion.
So I 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 make sense.
I'm curious if working largely in the milieu of an 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, some problems came to me because an engineer or a programmer had this problem to solve, like disk Paxos, for example.
That came because he didn't want to use more than two computers, but he would be able to use three or four disks.
His autobiography, Jean Renoir, who was the son of August Renoir, the famous painter, said that his father had told him that when asked why he went outdoors, you know, lugging all this stuff instead of painting in the studio, was that he said, well, if I was in my studio and was going to draw a tree, I might be able to come up with five or six different kinds of of leaves.
But we go out in nature and there are thousands of different kinds of leaves.
That's my explanation of why I like working in a company that's actually building things.
I think that's an amazing and deep analogy.
That's great.
I think that distinction between academia and industry in terms of practicality and stuff, that gap has closed.
a lot since the days when I was doing that stuff.
So great.
So perhaps moving on to the, just briefly at least, the topic of abstraction, and Dr.
Lampo, 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 taught?
Well, you know, I've devoted much of the end of my career to getting programmers or I would say more system designers than, you know, average programmers to be able to abstract and, you know, think more abstractly about what they're doing.
My understanding of how one should reason about.
concurrent programs, concurrent algorithms, led me to develop a language called TLA+.
I will say I've got enough experience to say that very good 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 upcoming book, A Science of Concurrent Programs.
I would love it if you could speak a little bit about that and the goals of the book.
The goal of the book is very simple.
I've worked, like I said, starting, well, really, in some sense, starting from 1975 or so when I wrote this first paper on proving correctness of multiprocess programs, you know, on figuring out how to A, state very precisely what the problem is, what 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 in one place.
you know, pretty much everything that I learned about the theory 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've promised to publish it and the last they said their goal was in March.
Fantastic.
So Dr.
Lampard, thank you again for the time.
Really appreciate you, you speaking to us.
Okay.
It's my pleasure.
I had fun doing it.
Fantastic.
Well, that was pretty amazing hearing from both Leslie Lamport and Barbara Liskov.
I thought maybe we could circle back on something we talked about, the power of mathematical abstraction of sort of real systems and sort of the feedback loop between practice and theory.
And I do feel like that came up pretty explicitly in both of the interviews.
Yeah, I thought 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-lemas 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 in 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 system or of math, and it's very, very hard to understand what's happening.
Yeah.
Yeah.
Your head explodes.
Yeah.
And they build extremely complicated systems, right?
So if you look at PBFC, this is like a huge endeavor.
And really this power of abstraction is what enabled that.
And this pattern, right, of abstraction 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 a discipline.
Yeah.
Yeah.
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 to particular points.
We heard from Dr.
Lamport about, you know, Paxos.
We heard from Dr.
Liskoff about, you know, view stamp replication.
It's funny how 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 it's an idea that in principle, all the tools were available 10 years prior, but somehow there's a right moment in time for this idea to emerge.
It's something even after 25 or whatever years 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, the interplay between theory and practice, but 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 Barbara Liskopf, she was kind of one of the founders, I guess, of systems research in computer science, industry systems.
So, you know, she was at MIT working with a lot of students 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 doing a lot of theoretical work, but...
being very connected to engineers and kind of talking to systems researchers and people who build large systems.
So both of them worked on the interface of, I guess, theory and systems, trying to build things and working with builders.
But both of them came from kind of different, very different career paths.
So it's interesting to see how different influences kind of push you to different directions.
Yeah.
In both cases, it was, you know, U.S.
government funding for different projects that wound up being pretty important, right?
Dr.
Lamport mentioned NASA, he mentioned SRI, and then Dr.
Ilskopf talked about sort of a big DARPA announcement.
So that was sort of 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 force in the academic world.
In a sense, you could think about...
The internet, right, that's coming from DARPA-pushed use cases and then maybe flourished through kind of economic incentives.
I'm sure as most listeners know, the original internet was actually called the ARPANET because it was an ARPA project, ARPA being the precursor to DARPA.
Yep, yep.
And, you know...
Byzantine agreements might have the same type of path in a way.
It was kind of pushed by DARPA as a focus for survivability.
They really cared about this notion of having large scale distributed systems that would survive attacks or would survive faders, would survive even if part of the system got destroyed or got maliciously attacked.
And it's actually fascinating to see that this technology is now being...
used for economic use, right, in blockchain technologies.
So it's kind of the same type of pattern of a movement of technology from, I would say, 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 timescale is like the one at which sort of really sort of fundamental breakthrough ideas.
emerge, 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 a very long-term game, fundamental research.
And I think that came through very strongly today.
Yeah, and 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, because that's something, again, you know, I mentioned cryptography and snarks earlier.
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 Itay, thank you for joining us, the co-host.
Super, super fun.
Thank you, Tim.
This was a lot of fun.
Yeah, we should do this more.
We should.
We should.
Let's work on that.
All right, let's do it.