The Peterman Pod - Turing Award Winner On Thinking Clearly, Paxos vs Raft, Working With Dijkstra | Leslie Lamport

Episode Date: February 23, 2026

I interviewed Leslie Lamport, a Turing Award winner known for his contributions to distributed systems and the inventor of the Paxos algorithm. We walked through the major contributions of his career for the stories behind them and what he learned along the way.🔸 My keyboard project: https://read.compose.llc/p/our-keyboard-design-reveal𝗣𝗼𝗱𝗰𝗮𝘀𝘁 𝗹𝗶𝗻𝗸𝘀:• YouTube: https://youtu.be/U719vQz-WFs• Apple: https://podcasts.apple.com/us/podcast/the-peterman-pod/id1777363835• Transcript: https://www.developing.dev/p/turing-award-winner-on-working-with𝗘𝗽𝗶𝘀𝗼𝗱𝗲 𝗹𝗶𝗻𝗸𝘀:• Bakery Problem Paper: https://lamport.azurewebsites.net/pubs/bakery.pdf• Time Clocks Paper (most cited): https://lamport.azurewebsites.net/pubs/time-clocks.pdf• The Byzantine Generals Problem Paper: https://lamport.azurewebsites.net/pubs/byz.pdf• The Paxos Algorithm Paper: https://lamport.azurewebsites.net/pubs/lamport-paxos.pdf𝗧𝗶𝗺𝗲𝘀𝘁𝗮𝗺𝗽𝘀:00:00:00 - Intro00:01:25 - The Bakery Algorithm00:08:28 - Experiences with Dijkstra00:14:44 - His most cited paper00:23:26 - The "Byzantine Generals" problem00:38:05 - The Paxos Algorithm00:46:57 - Paxos vs Raft Algorithm00:51:26 - Building LaTeX00:54:45 - Why writing improves your thinking01:00:21 - Why he wasn't an academic01:02:08 - Grand theory of concurrency01:07:25 - Why he doesn't think he's smart01:09:07 - Advice for his younger self01:09:44 - Outro𝗪𝗵𝗲𝗿𝗲 𝘁𝗼 𝗳𝗶𝗻𝗱 𝗟𝗲𝘀𝗹𝗶𝗲:• His works: https://lamport.azurewebsites.net/pubs/pubs.html𝗪𝗵𝗲𝗿𝗲 𝘁𝗼 𝗳𝗶𝗻𝗱 𝗥𝘆𝗮𝗻:• 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

If you think you know something, but don't write it down, you only think you know it. This is Leslie Lamport. He's a Turing Award winner, famous for his contributions to distributed systems, and I interviewed him for the stories behind his papers. Their reaction shocked me. They became angry. I really thought they might physically attack me. What was it about Dykstra's old solution that you felt was unsatisfactory?

It was not an obvious idea. to most people. That had actually impressed Dykstra. As the inventor of the Paxos algorithm, I asked him his thoughts on the competing raft algorithm. There was a bug discovered in raft and fixed, but I believe the algorithm that they found more understandable was one with that bug. I also enjoyed reflecting over his 50-year career. You say things like you never considered yourself smart. How could that be? Stupid people think they're smart because they're too stupid to realize they're not.

You felt like a failure at some point because you wanted to develop this grand theory of concurrency and you never discovered it. Do you still feel that way? Here's the full episode. I wanted to start with the bakery algorithm. What is the problem that the bakery algorithm solves and how did you discover the problem? Well, the problem was invented or discovered by Edzger Dykstra in a 1965. I think it was 1965 paper. And that began, I consider that really the beginning of the theory of concurrency,

concurrent programming. He was the first one who really made use of the idea of concurrency as a way of structuring programs, as a collection of semi-independent tasks. and the processes have to synchronize with one another. One of the processes or among the processes would be, well, this was in the days of time sharing, right at really at the beginnings of timesharing and the idea of multiple people using the same computer.

People realize that computers were worked faster than humans, and computer, were very expensive in those days, so they could use a computer to be used simultaneously by multiple people. The program that each user was running was a separate program, but sometimes there were resources that got shared, for example, a printer. Two people trying to print on the same printer at the same time, well, the result would be not very satisfactory. So he realized there was this problem of synchronizing multiple processes, the idea of what he called a critical section, or some piece of code in each of the processes so that at most

one process can be executing that piece of code at any particular time. so that code might be the code that prints something on the printer. So the problem was how to get the processes to synchronize among themselves so that at most one process was executing its critical section at a time. And it was in 1972 that I learned about the problem because there was an article giving a solution to it in the, CACM communications of the ACM. And I used to program, and I liked little programming problems, you know.

And this was just a very nice little programming problem. And so I looked at the solution, which is fairly complicated, and I said, oh, gee, that shouldn't be so hard. And so I whipped off a very simple algorithm them for two processes and submitted it to CACM. And a couple of weeks later, I received a letter from the editor pointing out the bug in my program. So that had two effects.

The first was that I realized that concurrent programs were hard to get right and that you needed a proof that they were correct. And the second was that made me feel, I'm going to solve that damn problem. And I came up with the bakery algorithm, which was inspired by the idea came from what I've now called the deli problem, where you have a deli counter that collects, you know, tickets, a roll of tickets, and every customer would come in and take a ticket. and then the next person saw it to be served would be the one with the highest number,

the lowest number ticket that hadn't been served yet. And basically that I took that idea, but since there was no central server, or at least the problem as specified by Dykstra, involved no central control, each process basically had to choose, their own ticket. That was the basic idea and the algorithm was quite simple. And I wrote a proof of correctness. And the proof of correctness revealed to me that this algorithm had this very interesting property. There was a general feeling, in fact, somebody published in a book or paper saying, you know, that

It was impossible to implement mutual exclusion like this without using some lower level mutual exclusion. And the way most the mutual exclusion that was assumed generally was that of shared registers, you have shared pieces of memory that could be written and read by different processes. And the idea is that you know, you couldn't have one process, two processes writing at the same time, or one process reading while the other process was writing.

People assumed that those actions were atomic. They always were performed as if they occurred in some specific order. But the amazing thing about the bakery algorithm was that it didn't require that assumption. It used each shared memory, a piece of memory, was only written by a single. single process, so they didn't have to worry about two processes interfering with each other. The only problem that you might come is that somebody reading the value while it was being written might get some unknown value. But the algorithm worked anyway.

If somebody read, if one process read while the registers were being written, that reading process could get absolutely any value. And the algorithm still worked. I saw in your writing about this problem that you shared it with a colleague named Anatole Holt. And the proof was so remarkable that they didn't believe it. Well, the result was so remarkable. Yes, yes, the result.

That he didn't believe it. And I wrote the proof on the whiteboard for him. And he couldn't find it, but he went home and saying there must be something wrong with it. And he obviously never found anything wrong with it. Right. I saw the name of the paper is a new solution of Dykstra's concurrent programming problem. What was it about Dykstra's old solution that you felt was unsatisfactory

and made you want to solve this problem? Well, there was an unsatisfactory aspect of his original solution that had the property that, if there were a lot of, if processes kept trying to enter their critical section, an individual process might be starved, might never get access to the critical section. That was solved by, you know, the next solution, I think, was Don Knuths. The condition that was desired, or that measured, that what was considered the efficiency of it was how long a process might have to wait.

And I believe that the bakery algorithm was the first one that was really first come, first served. That is, if one process came, what it meant, is if one process chose its number before another process tried to enter, that first process would enter the critical section critical section before the other process did. And I believe the bakery algorithm was the first one with that property. And also, I think it was simpler than other solutions. In a lot of the writing, I see that

you worked with Dykstra. And I saw in 1976 you actually worked for a month in the Netherlands and he worked with them. Can you talk about that a little bit? Dykstra used to had the things that are called EWD's initials. They're little papers, things that when he thought of something, had some idea, he would write it down and send it out to people. Well, one of those EWDs was about he and some associates are actually sort of mentees, I guess you would call them, wrote this algorithm, was the first concurrent garbage collection algorithm, a way of very. writing programs evolved where there was a pool of memory that when a program would need a piece of memory, it would ask some server for it and be given this piece of memory. But at some point,

it would stop using that memory. But the program itself wouldn't know that one particular process that created this memory, wouldn't know whether some other processes, you know, is using that memory or not. So there was an additional process called the garbage collector, which would go around examining the memory and decide which pieces of memory were no longer being used and then put them back on the, it's called the free list in which the server, the process that was giving out the memory

would be able to take it. I looked at it and I realized that I could see simplified the algorithm because he had some special, the handling of the free list was done by a special process that, you know, which had it to worry about its own coordination with the processes that were using the memory. And I realized that that free list could just be made part of the regular data structure. so it didn't need special handling. And that seemed to me like a very simple idea, a very obvious idea, and I said it to him, and then when I got the next version of the paper,

I discovered he had made me an author. And I thought that was very generous of him to have done that, because it seemed like a very simple idea. and a very obvious idea. And I later realized, much later, that it was not an obvious idea to most people, and that that had actually impressed Dykstra.

And that was the only thing I actually did with Dykstra, many years later, he said that I had a remarkable ability at abstraction only in very recent years, I mean, maybe after I got the touring award, that I realized that the reason for my success, the reason I got it to wind up getting a touring award was not that I was particularly that smart, but that I had this gift of abstraction. And Dykstra was smart enough to realize that.

I was invited to spend a month, but not with Dykstra, with a colleague of his Carl's Hulton. Only one thing that was ever published came out of that. Carl and I would meet with Dykstra once a week. In the course of that discussion, the idea somehow came up that led to a variant of the bakery algorithm that I wrote up and published. So that was the one tangible result that came for my month in the Netherlands. Yeah, I saw that you wrote that,

you spent one afternoon a week working, talking, and drinking beer at Dexter's house, and you kind of don't remember exactly who was in charge of what on that paper. Yeah. Well, I don't think I really could have gotten that drunk because I probably drove to the meeting and back from the meetings. Right, right.

The Dutch beer that I was drinking was not very alcoholic. I wanted to talk about your most cited paper, the one titled Time Clocks and the ordering of events and distributed systems. What's the story behind the paper and the problem you were solving with it? The origin was simple. Well, somebody sent me a paper on Bill. distributed databases. And so where you'll have multiple copies of the data at different places, and you need to keep them synchronized in some way.

I looked at it and I realized that their solution had this problem, that it had the property that things would be executed as if they occurred in some sequence. But that sequence could be different from the sequence in which they actually happened. The notion of what, you know, happening before means is not obvious, or not obvious to most people. But I happen to, you know, learn about, you know, special relativity.

In particular, what's known as the, it's the space-time view of special relativity, where you basically consider space and time together is one four-dimensional thing. And that was, Einstein wrote his paper in 1905, and in I think it was 1909, somebody whose name I'm blocking on, provided this four-dimensional view. And that four-dimensional view has the particular notion

of what it means for one event to occur before another. And that notion is that one event happens before another if a signal was emitted from the first event and received by whoever did that second event before that second event happened. But the communication could not travel faster than the speed of light because nothing can travel faster than the speed of light. Well, I realize there was an obvious analogy. The notion that happens before is exactly the same as in relativity, except instead of being whether something, one event can influence another by things traveling at the speed of light, it's whether the first event could have affected the other by information sent over messages that were actually sent. in the system. The thing that, you know, blew people away was this definition of happens before

in a distributed system. Also, this was the first paper, I would call it, you know, had a scientific result about distributed systems. I made, perhaps, you know, a mistake that it was warned against at some point of having two ideas in one paper. The other thing that I realized, was that there was an algorithm that would show whether one event, that it would produce an ordering that satisfied this condition, that if one event happened before the other, then that first event would be ordered before the other. And I realized that if you had an algorithm to do that,

you could use it to basically provide the synchronization you needed for any distributed system, because you could describe that system in terms of a state machine. And a state machine, as I described it then, is something that has a state, and process executes commands that need to be executed in order. And the command simply is something that makes a change of the state and produces a value. And so you just describe this state machine as just, you know, how commands affect the state and how they produce, and what the new state is as a function of the original state and what the value is as a function of the original state. It turns out that this was very obvious to me, but that's really in practice the important idea in that paper.

because it showed that this method of building distributed systems by thinking in terms of a state machine and thinking about concurrent systems in terms of state machines. But that part was completely ignored. As a matter of fact, twice I talked to people about that paper and they said there was nothing in that paper about state machines. And I had to go back and reread the paper

to be sure I wasn't going crazy, and it really did talk about state machines. It's important for another reason if you're trying to understand a concurrent program. The recurring programs are written. The bakery algorithm is really an exception. Concurrent programs are written assuming atomic actions,

so that you assume that the execution behaves like a sequence. You can assume that the execution proceeds as a sequence of events. It turns out that the way to understand, you know, why does a program produce the right answer? Well, the answer is, well, you give it the right input. You give it the input and then it produces the right answer.

Well, but by the time you're in the middle of execution, what it was given at the beginning is ancient history. The only thing that tells the program what to do next is its current state. And the way to understand a program, you know, a simple program that just, you know, takes input and produces an answer, is to say what is the property of the state at each point that ensures that the answer it produces This is going to be correct. And that property, which is mathematically a bullion-valued function of the state, is called an invariant. And understanding the invariant is the way to understand the system, the program.

And I realize that the same thing is true of concurrent systems and concurrent programs. People like to write proof, behavioral proofs, reasoning about sequences. And the problem with that is that the number of sequences, possible sequences, is exponential in the length of the sequence. So your complexity of your reasoning gets to be very complicated, and it's very easy to miss cases. But the complexity of an invariance proof, the complexity of the invariant basically is, well,

Okay, the number of possible executions is exponential in the number of processes, but the behavior of the proof of an invariance proof is quadratic in the number of processes. You know, that's basically why invariance proofs are better. But, you know, there's still, for a long time that, you know, people, you know, doing, distributed systems theory of trying to do it, you know, develop, you know, methods and formalism, something that are based on partial orderings and that. They've, you know, published a lot of papers, but it's just, you know, not the way if you want to do it in practice. That's not the way to do it. And I shouldn't say, you know, it's not the way. You know, there are algorithms, like the bakery

algorithm that, you know, thinking of partial orderings is, in fact, a very good way of doing it. But those are the exceptions. The method that works, you know, that you can be sure will work, will work is the use of invariance. I want to talk about the, I guess, the next paper, which is the Byzantine general's problem. I think that's something that we hear about and we learn about when you're. and going through college and computer science. And the name is great. And I want to know the story behind that problem.

After I wrote that, the Time Clocks paper, that tells you how to build a distributed system, but assuming no failures. And it was obvious that, you know, distributed, one reason for distributed systems as you have multiple computers, so if one fails, you can, you know, keep going. In particular, that was the problem that was being solved at SRI when I joined it.

But before I got to SRI, I started working on that problem. And there was no notion of the idea of what I should think about is what can a failure do. So I assume that the worst possible case, that a failed process, that a failed process, might do absolutely anything. And I came up with an algorithm that basically would implement the state machine under that assumption. And the algorithm I came out with used digital signatures, so that it used the fact that a faulty process might do anything,

but it could not forge the signature of another process. Which just means that the message can be can be trusted that it came from a proper process. Right, so that you can relay messages. And the people know can check that the relayed message is actually the one that was originally sent. And so a solution using that. When I got to SRI, I realized that people

were trying to solve the same problem. But there are two differences. First of all, at the time I did this was 19, Very few people knew about digital signatures. And in fact, I don't remember when the Diffie Hellman paper was published, but it was around 1975. And I happened to know about digital signatures because with Diffy, who was one of the authors, two authors of that paper,

was a friend of mine. And in fact, at one point, we were at a coffee house and he was describing these things that he said, that he said, we have this problem of building digital signatures. You know, we haven't solved. And I said, oh, that seems easy enough. And I sat down and literally on a napkin, I wrote out the first digital signature algorithm.

It was not practical at the time because it required basically something like, you know, 128 bits to sign one bit of the, you know, of the thing they're signing. It's not quite that bad because, you know, as you might think, because you could use, sign not a, the entire didn't document, but a hash of that document, which you assume, you know, people cannot forge a hash.

They can't reverse. Yeah, no, you can't reverse, you know, take a hash and, you know, find some other hash that, you know, or some other document that satisfies, that hash. But anyway, that's why I had, you know, digital signatures were part of my toolkit. So the people at SRI didn't have that. But they also had a nicer abstraction of it. Instead of getting agreement on a sequence among the processes on a sequence of commands, they would agree, have an algorithm for agreement on a single command.

And then that algorithm would be executed multiple times. And that was a nicer way of describing, you know, what you're doing than my method. So the first paper that was published used gave both their original. Oh, but since they didn't have digital signatures, they used the different algorithm, and they had the property that, to tolerate one faulty process,

you needed four processes, whereas if you used digital signatures, you only needed three processes. So the original paper contained both algorithms, and so I was one of the authors. The other algorithm without digital signatures is more complicated, and the general one,

for N processes was really a work of genius. It was almost incomprehensible. You just had to read in this complicated proof that, you know, for the arbitrary case of an arbitrary number of processes, you need N-pros to tolerate N faults, you needed four N processes, whereas with digital signatures,

you need three-end processes. And the algorithm for a single fault wasn't hard, but the one for, multiple four parts was Marshall Peas was the one who did it and it's just brilliant. Later in a later paper, I had discovered a simpler proof, a one that was an inductive proof, they'd probably prove that if it works for n minus one, you know, it would work for n with 3n, it works for 3 n times n minus one. The original paper was a You know, the original one was just brilliant.

You would have discovered it. Anyway, so we published that paper, and I realized that this was this whole idea of Byzantine fault. So the thing is, well, Byzantine fault is one that we're a process, assume the process can do anything. Now, I was assuming that, you know, processes can do anything because, you know, I didn't know what to assume. but the people at SRI had the contract for building a multi-processing

a multi-computer system for flying airplanes. And so they were the ones who appreciated the need for solving processes that can do malicious things because they really couldn't assume what it would do. And every time you would get an algorithm and you'd see, oh, well, this algorithm, try to get an algorithm with three processes, you know, for one fault. You know, you'd find that, you know, oh, you know, this works, but it must be, you know, really couldn't happen in practice.

And then you'd be able to find some sequence of plausible failures that would lead the algorithms to be defeated if there were a faulty process. So you needed four. And for some reason, you know, I thought that digital, signatures was almost a metaphor in the algorithm that it should be possible, you know, since we weren't worried about malicious failures, but, but, you know, just things that happen randomly, that there should be some way of writing a digital signature algorithm that, you know, would have a sufficiently low probability of failing.

but I never worked on that and nobody else ever did. So that algorithm was pretty much ignored because digital signatures were very expensive in those days. I don't know what's being done now because computers are digital signatures are just computing and computing is cheap. But I remember at some point I happened to be communicating with someone

who was an engineer at Boeing. And I asked whether they knew about those results. And he said, yes. He, in fact, was the one at Boeing who would read that paper, and his reaction was, oh, shit, we need four. Four computers. But at any rate, I realized that this was an important result, and it should be well known.

And I had learned one thing from Dykstra. One of the things I learned from Dykstra, he wrote this paper called The Dining Philosopher's Problem. And that paper got a lot of attention. But the dining philosophers problem, I want to go into what it is, but I think the basic problem was not particularly interested. But it had a cute story to it.

It involved a bunch of philosophers sitting around the table with some, funny kind of spaghetti that it required two forks and there was one fork between, you know, each fork would be shared with two people. And I think, realized it was because of that cute story that that problem was popular. And so I decided that, you know, this, our work needed a cute story, you know, a nice story. And I invented Byzantine generals, the idea being that you have a group of, you know, for the one failure case, you have four generals who have to agree whether or not to attack. And if they all attack, they'll win the battle.

But if only some of them attack, or even if three of them attack, they'll win the battle. But if only two attacks, you know, they would lose. but one of the generals might be a traitor. And so how could you, you know, solve this problem? And so it's phrased in terms of these generals having to communicate and decide whether to make the single decision whether to attack or retreat. And, you know, I called it the Byzantine generals problem.

I saw in your notes about the point, problem that there was maybe a subset of the problem or a prior version that was called the Chinese generals problem or something like that? Oh, yeah. Yeah, I was, there was a different problem that Jim Gray described as an impossibility result, basically. It's called the Chinese generals problem. And I won't bother going into what it is. And so that gave me the idea of generals. I actually originally thought of the idea of Albanian generals, because at that time, Albania was a black hole as far as the rest of the world was concerned.

It was a communist regime, so part of the Soviet bloc, but it was even more Soviet than the Soviet Republican and more restrictive. So when my boss said, well, you know, there are Albanians in the world, so you shouldn't that? and so I should have a different name.

And then I realized that Byzantine, there aren't any Byzantiums, Byzantines around, and that was the perfect name. It's interesting to me in the story that, because this isn't the first time the problem was specified, but it's the first time that you had named it, gave it a good catchy name, essentially, and added some additional results.

What was it that you saw in that problem that made it interesting? Or rather, like, how do you know that a problem is worth putting extra time into? Oh, well, this one, it was because, you know, it was obvious that people were going to be building, that computers were going to fly airplanes, fly airplanes. And the reason, in fact, because was that this was during the time of the oil crisis in the 70s, and that they knew, people knew that they could build more energy-efficient planes,

by reducing the size of the control surfaces, but that made the plane aerodynamically unstable and a pilot couldn't make all the adjustments needed to keep it flying, but a computer could. So it was clear the future was, you know, airplanes were going to be flying, going to be flown by computers, as they are today. And people, people,

didn't realize, they thought that, oh, if you want to be able to tolerate one fault, you'd just use three computers. And they didn't realize that, you know, with arbitrary faults, you need four. And so that was a really important result. And that's why I believe that it needed to be well known. Generally, when you look at the problems that you are solving with your work, how'd you decide? Because if you're working at a company, you can decide basically, off of maybe the, I guess, the impact to the company. Like, is it going to make more money or save costs or something like that? But I wonder in your work across your career, you know, think about the bakery problem

or some of your later work as well. How do you know it's so open-ended? How do you know which problems are the ones worthwhile? Throughout my career, I worked for private companies, you know, not in academia. or for the government. And so some problems arose because of, you know, sometimes, you know, an engineer would have a problem and come to me. And so, you know, disc Paxos, for example,

was a case of that, that somebody actually wanted an algorithm to do what it did. You mentioned earlier Paxos, and I know that's one of your most famous works, curious about the story behind maybe that paper and the problem you're solving? Well, the problem I was trying is exactly the same problem as I was solving in the Byzantine General's work, basically building a fault-tolerant state machine. But by that time, it was, you know, the faults that interested industry were ones where failure meant that the computer just stopped.

not that it did arbitrary things. So the Paxos is an algorithm for building fault tolerance systems for handling that class of faults. And the people I was working at was, which the Dexerc Lab, which I joined in 1985, And they built a, what are the first operating systems that was a distributed operating system. So that basically everybody had, they basically, these are the people who had come from Xerox Park and had invented personal computing. But they also had the notion of distributed personal computing.

They invented the Ethernet, you know, for that. So they, basically, all of the computers in the building were on a single Ethernet network and shared a common storage. And they had an algorithm for maintaining consistency of that storage. And I didn't believe, well, they didn't have an algorithm. They had an operating system with code that did that. And I didn't believe that what they did was possible. Namely, I didn't think, well, I forget exactly why I didn't think it was possible.

But at any rate, I started, you know, try to come up with an impossibility proof. And then it started to solve this would have to do this. and it'll have to do this, they don't have to do that. And at some point, I stopped and said, oh, this isn't a proof. It can't. This is an algorithm that does it. You said that they had code, but not an algorithm.

Yeah. What do you mean by that? When most people sit down and start writing programs, you know, they start by thinking in terms of code. And one of the things I learned fairly early at, my career. I don't remember exactly when. That back in the days when I started writing concurrent algorithms, people talked about, people were calling them programs. And I was probably calling them programs too. I mean, I remember. Then at some point, I realized that I wasn't talking

about programs. I was talking about how interested in algorithms. And an algorithm is something that's more abstract than a program. An algorithm can be, you know, a program is written in some particular code, but an algorithm can be implemented. It programs written in any kinds of code. It's something that's at a higher level of abstraction. And of course, I like that because abstraction is something I was good at, even without realizing that that's what I was doing.

And so what I've spent a large part of my career, basically maybe about 2000 or so onward, was getting people who build concurrent systems to not just write code, but to have an algorithm. Now, a system does lots of things. But there should be some kernel of the program that's involved with synchronizing the different processes or the distributed system of the different computers. And that code is very hard to get that correct. So you don't want to think in terms of code,

because that encoding conflates. you know, a lot of issues that are irrelevant to the concurrency aspect. And so you should be thinking, you know, first get an algorithm that does that synchronization and then implement that algorithm. I was looking at the Paxos paper and some of your notes about it. And I saw that there's an eight-year gap between when you came up with the algorithm and when the paper was actually published called... part-time parliament, is the name of the paper.

Why is there an eight-year gap? Oh, well, the referees originally said, well, this paper is okay, you know, not terribly important, but fortunately, Butler Lampson realized the importance of the algorithm. And together with the idea of, you know, it's going to implement anything because it's implementing a state machine. And, you know, went about process. facilitating, building your systems, you know, using Paxos, you know, and thinking in terms of state machines.

And so, you know, I wasn't, so the idea was getting out, so, you know, I was in no hurry to publish. So, you know, I just let the papers sit. and eventually there was a new editor that came along and he said that, you know, I think the status of the paper was that it was just, you know, it had been accepted, but had no, and needed revision. And so he decided that, yeah, let's, you know, to publish it. and it was eventually published with a little, some, a few things to take, well, to mention work that had been done in the interim. And what I got is, got Keith Marzullo to do that part for me. And so the story was that this manuscript, this was, well, the story about, well, the story about, Paxos was that, you know, it's happened, you know, centuries ago and, you know, this manuscript.

And I used that, the effect that, you know, when something, you know, the tales of something were, I considered obvious and, you know, not interesting, you know, the paper would say, it's not clear how the Paxons, what the Paxons did, you know, at this point. But at any rate, and so, Keith, you know, kept up the, that idea that, you know, this was a, you know, a description of this ancient thing. And, and he wrote, you know, a little prefix or a preface or something to do it and, you know, added maybe, I think, some references. I saw in your writing, too, when you were talking about presenting the paper initially, you even dressed up in like an Indiana Jones style archaeologist.

Well, how did that go when you presented about this Paxos paper and algorithm? Well, I think the lecture may have gone well, but I think nobody understood the algorithm where nobody understood the significance of the algorithm. It sounds like no one understood it except for Butler Lampson. What did he see that made him unique, I guess? Well, he had a good understanding of building systems. You know, he really deserved History Award. He was one of the original people at Xerox Park who were building distributed personal computing.

He and Chuck Thacker, I think, were probably the two senior people, you know, in that lab. I saw later there was a paper which describes a new algorithm, which seems to solve the same problem. the raft paper. I was wondering if you read that and what your thoughts were on that versus Paxos. The authors of that actually sent me a draft of the original paper, and I looked at it and said, I forget whether I said, send it back to me when you have an algorithm or said it back to me when you have a proof. I forget which one it was. And you got the idea and they really, they did write, you know, add a proof in the paper and not. And I never read future later versions.

And someone whose judgment I value, I said, had read it and said that it's basically it's the Paxos paper, but with some of the details left unfinished by the Paxos paper by, you know, some of the details filled in. but they described it in a very different way. The basic idea of what Paxos works is it's two phases, and you're trying to implement a sequence of decisions. And it turns out you can do the first phase once for a whole,

it involves a leader. So, and the leader has to get elected. So, but it turns out that you can do the first phase once. And you don't have to do it again as long as you have the same leader. But it's only the second part that you have to do, and then you have to elect the new leader, if a new leader fails and do the first part. So think about it in those two phases, but the way people,

way engineers, you know, I'd like to think about it, is, well, you do this, you know, you're talking about the first part, the second phase, you know, we keep doing this, until the leader fails, and then you go back, then you have to do this thing. So it's explaining it in the opposite order. And in fact, you know, when you started from fresh, the, you don't have to do the first, the first, the first phase. phase. You can, you know, basically, what's done of the first phase could be just built in into the initial state. But, you know, I think that that's the, you know, of those two phases is the way to understand it. But, you know, the RAF people also had this idea that, you

know, raft is better because it's simpler. I must say that a lot of people say that Paxos is hard to understand, and I don't understand why. I mean, I've explained it to people who in five minutes and they understood it. At any rate, the RAF people said that one of the ideas were simpler because, and they even have, you know, talks us to one class and they're raft to another and they took, and then yes, the people, all the students said that, yes, it was more understandable.

The interesting thing about it though is that there was a bug discovered in RAFed and fixed, but I believe that the algorithm that they found more understandable was one with that bug. So made me realize that, you know, what most people, you know, what does understanding mean? And for me, understanding means, you know, you can write a proof of it. But what understanding means for most people is a warm, fuzzy feeling.

And, you know, the raft description gave them, you know, more of a warm, fuzzy feeling because, you know, you know, that seems to be the way, you know, programmers, you know, like to think about the, the algorithm, you know, the second phase, you know, first until, you know, you get a failure. And, but the way I describe it is one that helps you get a better understanding of why it actually works. So, yeah, we talked about a lot of your papers. one of your other contributions, whether you knew it or not at the time, was lay tech and building that and something that has impacted the entire academic community. What's the story behind wanting to build lay tech? Oh, that was very simple. I was wanted, I was in the process of starting to write a book,

And it was clear that tech was the basic typesetting system that one had to use. But, you know, I felt that I would need macros to make tech do what I wanted it to do. And so I decided, figured it with a little extra effort, I could make macros useable by other people. The system I had been using before tech, it's called Scribe. And that really had basic idea of Scribe was that you described the logical structure of the document. And Scribe will do the formatting. Well, Scribe didn't do that great a job of formatting, so, but obviously, you know, I like the idea, abstraction, that it's the ideas that matter, not the, you know, the writing that matters, not the typesetting. And so I actually, at some point, I met Peter Gordon, I have an attestine.

Wesley, I'm not sure what you would call them, but he looks for books to publish. And he convinced me that I should write a book on it. And those days, it never occurred to be people that actually spend money for a book about software, but, you know, what the hell? And what he did was he introduced me to a typographic designer at Addison Wesley, who was responsible for, really, for the type of graphic design that's in the standard latex styles. Basically, I just did that in my quote, spare time.

It took me six or nine months or so. I suppose the statute of limitations has run out, but I was really, you know, spent some time working on that when I was allegedly, you know, billing the time to some project, that had nothing to do with it. On the topic of writing, you have a quote that I really enjoy. If you're thinking without writing, you only think you're thinking.

And I was curious to hear your thoughts on what you mean by that. Well, it was really meant for people building computer systems. You have an idea and you think it's going to work. Or you have something that, you know, you think is something that somebody else, will you want to use. Well, write a description of it. There's an old maxim that I heard that is, you know, write the instruction manual

before you write the program. Great advice. I did not do that with latex, but I definitely, when I was writing the book, and I discovered that something was hard to describe, hard to explain, that needed to be changed. And I made a number of changes to it as a result of that. But I didn't start at the beginning with the instruction manual.

Why is writing conducive to good thinking? Because it's very easy to, it's very easy to fool yourself. I mean, that underlies my, my whole idea of writing proofs. One thing I learned is that you had to write a correctness proof of a concurrent algorithm. And when my algorithm was starting to get more complicated, the proofs started, I started to write, you know, I was a PhD in math. I knew how to write proofs. And I was starting writing the proofs the way I would normally do.

And I realized it just didn't work because there were just so many details involved. And I just couldn't keep track of them and whether I had done it. And so as computer science, know how to deal with concurrency. It's hierarchical structure. And so I devised this hierarchical structure where a proof is a sequence of steps, each of which has a proof. And the proof is either a... a proof is either a paragraph or a statement, a sequence of steps, each with its proof.

And that proof can be either a paragraph or a sequence of steps with its proof. And so you break the whole problem up into these smaller pieces. So there's never any question of, you know, where is this coming from? You know, you're stating that this step follows from, you know, this step, this step, this step. And if it does not follow from that step, your proof is wrong. The theorem might be correct, but it means your proof is wrong. Well, you know, so I've discovered that worked great on writing my proofs of programs. But I decided to really, you know, I also write proofs of theorems, you know, think proofs that are things that are, you know, more like ordinary math.

And I started trying that on them. And I discovered it worked beautifully. So when I started to convince mathematicians to write these proofs, I started in one, the small seminar, I went, you know, I wouldn't describe what it was about, but I described this proof through maybe 20 mathematicians or something. Their reaction shocked me. They became angry. I really thought that they might physically attack me. So I believe that what's going on is that when people, I believe that's totally irrational. And when people act irrationally, it tends to be out of fear. And what I believe people are afraid of is the mathematicians are afraid of, is that they're going to have to write their proofs to convince a computer program. And in fact, you know, and I give it one of those talks,

I gave, you know, I say very clearly, this doesn't have to be, you don't have to be any more formal than you do. You can write the exact same thing, proof, but it's just a matter of organizing things, and it's very simple, you know, hierarchical structure, and then when you're using a fact, mention that you're using that. Nothing about formalism or anything. You know, after I gave that talk, someone got up and said, I don't want to have to write my proof, my, my, my, my proofs for a computer program. And in fact, it's more work doing that because the reason it's more work

is that it reveals what you haven't said and that there's steps in there that you may think they're obvious, but you haven't written them down. And if you believe something is correct, but don't realize, if you think you know something, but don't write it down, you only think you know it. And that's where errors come in. That's where that one-third of the papers errors can, you know, come in. Because it really makes you

honest. When I look across your career, I think you had a lot of contributions people might expect when it come from academia, these papers and things, but you did all of your work in industry. Why did you not see yourself as an academic and more of working for industry? Well, I started out programming, and I eventually got jobs where it took me into what we now call computer science. At the time, I never even realized that there could be a science of computing. It wasn't until, you know, maybe until mid-term. to late 70s that I realized, yes, there was the computer science, I know, as a computer scientist.

But it never seemed to me that computer science was an academic subject. At some point, I had to make a choice between doing computer science without calling a computer science or teaching math at a university. And I chose for fairly random, really random, reasons to do computer science. So for the first, I don't know, until maybe the mid-80s

or something, it just didn't seem to me that computer science was something that people needed to go to a university to learn. And I suppose afterwards that I was sort of, I guess, I just didn't think it would be fun. teaching computer science. I saw on your writing. You had a footnote that said somewhere that you, you felt like a failure at some point because you wanted to develop this grand theory of concurrency and you never discovered it. Do you still feel that way? Or what are your thoughts on that

footnote? Lots of people who, you know, a large percentage of the people who were doing things like I was doing, which is not a large number of people. There's this notion that there's this notion that, that they were looking for the touring machine of concurrency. The touring machine was this abstraction, which really captured what computing was. And they were looking for something that would be the touring machine of concurrent computing. And nobody should.

succeeded. I mean, there are some people who think they've succeeded. The patronettes are something that, I guess I don't have time to explain it, but there was a big, it was big in the 70s. And I was actually surprised to think that there's still a large community of people doing patronettes. But what I now realize is that patronettes and most of the things that people were doing was really language-based. And I was never interested in languages. I'm interested in what the language is expressing. And, you know, I realize, in some sense, you know, maybe I've realized what the Turing machine of computing is, state machines. State machines are a little bit different the way I now describe them. They don't have commands. They just have a state and a next state relation,

even simpler than talking about commands and values and stuff. And to me, you know, that's the touring machine of concurrency. But it doesn't have the function that touring machines offer because it doesn't, what touring machines do is describe what's possible. And state machines can describe anything, including things that are not possible. And in fact, there's a good reason for that.

For example, when I describe an algorithm, I will talk about, you know, the values of a variable can be any integer. Now, you can't implement the program where you have any integer. But that makes the... But talking about, you know, computer integers would complicate things unnecessarily. See, people have this funny idea that, you know,

because something is infinite, it's more complicated. They got it backwards. Infinity was introduced to simplify things. You know, the first thing you learn is arithmetic. You're learning arithmetic with an infinite number of integers because if you were restricted to a finite set of integers, arithmetic becomes a much more complicated. So, you know, the abstractions of mathematics,

which people find, you know, because they don't have the proper training in mathematics, find, you know, difficult are really what's simplifying things. And that's what you use, this mathematics. The state machine is described by me, using mathematics. That's the right, you know, the most powerful way of doing it. But computer people and computer scientists and programmers are really hung up on languages.

And so they are looking at. for, you know, they invent all sorts of languages, and they're all describable, and in fact, if you want to give them a semantics, you would do it in terms of a state machine. And they just think that this, you know, this language is, improves your thinking. It doesn't. I mean, there are reasons why you use computer languages and you don't write your programs, code, in math. And they involve basically efficiency. But for understanding, you can't build math, you can't beat math. And, you know, attempts to do it by something that looks like a programming language is just the wrong way to deal when you're trying to deal with concurrency.

When I look at everything that you've written and all the stories, there's the these little anecdotes, there's things where you say things like you never considered yourself smart, but you noticed that other kids had an awful time understanding things. Or, yeah, there's a problem that you solved where someone else had difficulties, but you don't view your contribution as a brilliant one or anything like that. And that doesn't connect with me because you've also won a Turing Award and done all these amazing things. So how can you? could that be that you, you know, just merely discover things and are not smart, yet you've achieved so much? Well, this general thing that, you know, psychologists talk about is that

when someone is good at something, they don't realize how they're good they are at it because it's simple to them. There's the opposite one that, uh, that, uh, People who are bad at something think they're better than they are because they're bad at it. Or put a little bit more concisely, stupid people think they're smart because they're too stupid to realize they're not. The gift that I have is not, in some sense, raw intelligence. It's abstraction. and it's only recently, you know, the last 10 or so years, that I realized how much better I am at that than other people,

most other people. At this point, you've experienced so much. And when you look back on your career, if you could go back to yourself when you just graduated college and give yourself some advice knowing what you know now, what would you say? One thing I've learned fairly early in my life is that I shouldn't waste time

trying to answer questions that I don't have to answer. I don't think about what I should have done because that's a question that I don't have to answer. 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.