Leslie Lamport on the Science of Distributed Systems

**Leslie Lamport** (0:00)
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 Paxos 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.

**Tim Roughgarden** (0:40)
Do you have a recipe of how you find problems that are practical, where you think you can develop important theory for it?

**Leslie Lamport** (0:46)
Well, one thing that helped me at the beginning was...

**Tim Roughgarden** (1:00)
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, Ittai 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. 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 the initial work in distributed algorithms in the mid to late 70s. So for example, the time clocks and the ordering of events paper, was that a natural segue for you from the work you were doing around concurrency?

**Leslie Lamport** (2:52)
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. I've 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. 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 they 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 Ed Schoedijkstra, 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 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, 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 like to solve interesting little programming problems. And concurrency made problems much more interesting, 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 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.