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

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 - Intro 00:01:25 - The Bakery Algorithm 00:08:28 - Experiences with Dijkstra 00:14:44 - His most cited paper 00:23:26 - The "Byzantine Generals" problem 00:38:05 - The Paxos Algorithm 00:46:57 - Paxos vs Raft Algorithm 00:51:26 - Building LaTeX 00:54:45 - Why writing improves your thinking 01:00:21 - Why he wasn't an academic 01:02:08 - Grand theory of concurrency 01:07:25 - Why he doesn't think he's smart 01:09:07 - Advice for his younger self 01: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

Speaker names marked ? are inferred from speaking time and the show’s known hosts — they are not voice-verified.

• 0:00Speaker 00

  If you think you know something, but don't write it down, you only think you know it.

• 0:06Ryan Peterman?

  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.

• 0:14Speaker 00

  Their reaction shocked me. They became angry. I really thought they might physically attack me.

• 0:22Ryan Peterman?

  What was it about Dijkstra's old solution that you felt was unsatisfactory?

• 0:28Speaker 00

  It was not an obvious idea to most people. That had actually impressed Dijkstra.

• 0:34Ryan Peterman?

  As the inventor of the Paxos algorithm, I asked him his thoughts on the competing Raft algorithm.

• 0:38Speaker 00

  There was a bug discovered in Raft and fixed, but I believe the algorithm that they found more understandable was one with that bug.

• 0:48Ryan Peterman?

  I also enjoyed reflecting over his 50-year career. You say things like, "You never considered yourself smart." How could that be?

• 0:55Speaker 00

  Stupid people think they're smart because they're too stupid to realize they're not.

• 1:00Ryan Peterman?

  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.

• 1:17Ryan Peterman?

  I wanted to start with the bakery algorithm. What is the problem that the bakery algorithm solves? And how'd you discover the problem?

• 1:25Speaker 00

  Well, the problem was invented or discovered by Edsler-Dijkstra 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...

• 1:51Speaker 00

  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, you know, right at, really at the beginnings of time sharing. And the idea of multiple people using the same computer. People realized that computers worked faster than humans. And so, and computers were very expensive in those days.

• 2:33Speaker 00

  So they wanted, they could use a computer to simultaneously, to be used simultaneously by multiple people. The program that each user was running, you know, was a separate program. But sometimes, you know, 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, you know, 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,

• 3:18Speaker 00

  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.

• 3:57Speaker 00

  And I used to program and I liked little programming problems. And this was just a very nice little programming problem. And so I looked at the solution, which is fairly complicated. I said, "Oh gee, that shouldn't be so hard." And so I whipped off a very simple algorithm 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.

• 4:41Speaker 00

  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 gonna solve that damn problem." And I came up with the bakery algorithm, which was inspired by... The idea came from what we now call the deli problem, where you have a deli counter that collects tickets, a roll of tickets, and every customer would come in and take a ticket.

• 5:23Speaker 00

  And then the next person to be served would be the one with the lowest numbered ticket that hadn't been served yet. And basically, I took that idea. But since there was no central server, or at least the problem as specified by Dijkstra 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...

• 6:09Speaker 00

  This algorithm was, had this very interesting property. There was a general feeling, in fact, somebody published it in a book or a paper, saying, you know, that it was impossible to implement mutual exclusion like this without using some lower level of mutual exclusion. And the way most, the mutual exclusion that was assumed generally was that of shared registers, you know, shared pieces of memory that could be written and read by different processes.

• 6:50Speaker 00

  And the idea is that, you know, you couldn't have one process, you know, 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 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 process. So you didn't have to worry about two processes interfering with each other.

• 7:28Speaker 00

  The only problem that you might come is that somebody reading the value while it was being written might get, you know, some unknown value. But the algorithm worked anyway. If somebody read, if one process read while the registers were being written, that process, reading process, could get absolutely any value, and the algorithm still worked.

• 7:53Ryan Peterman?

  I saw in your, your writing about this problem that you shared it with a colleague named Anatole Holt.

• 8:02Speaker 00

  Yes.

• 8:03Ryan Peterman?

  And the proof was so remarkable that they didn't believe it.

• 8:08Speaker 00

  Well, the result was so remarkable.

• 8:10Ryan Peterman?

  Yes, yes.

• 8:11Speaker 00

  That they didn't believe it. And, you know, I wrote the proof on the.

• 8:18Speaker 00

  Whiteboard for him and, you know, 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.

• 8:28Ryan Peterman?

  Right. I saw the name of the paper is A New Solution of Dijkstra's Concurrent Programming Problem. What was it about Dijkstra's old solution that you felt was unsatisfactory and made you want to solve this problem?

• 8:44Speaker 00

  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 Knuth's. 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.

• 9:28Speaker 00

  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 before the other process did. And I believe the bakery algorithm was the first one with that, with that property. And also, I think it was simpler than other solutions.

• 10:03Ryan Peterman?

  In a lot of the writing, I see that you worked with Dijkstra. And I saw in 1976, you actually worked for a month in the Netherlands and you worked with them. Can you talk about that a little bit?

• 10:17Speaker 00

  Dijkstra used to have the things, they're called EWDs, its 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...

• 10:36Speaker 00

  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 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 the particular process that created this memory, you know, wouldn't know whether some other process is using that memory or not.

• 11:18Speaker 00

  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 simplify the algorithm because he had some, the handling of the free list was done by a special process that, you know, which had it to worry about its own coordination

• 12:00Speaker 00

  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

• 12:45Speaker 00

  I later realized, much later, that it was not an obvious idea to most people. And that that had actually impressed Dijkstra. And that was the only thing I actually did with Dijkstra. Many years later, he said that I had a remarkable ability at abstraction. Only in very recent years, I mean, maybe, maybe after I got the Turing Award, that I realized that the reason for my success, the reason I got it, wound up getting a Turing Award, was not that I was particularly that smart,

• 13:28Speaker 00

  but that I had this gift of abstraction. And Dijkstra was smart enough to realize that. I was invited to spend a month, not with Dijkstra, with a colleague of his, Carl Schulten. Only one thing that was ever published came out of that. Carl and I would meet with Dijkstra 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

• 14:10Speaker 00

  that came from my month in the Netherlands.

• 14:14Ryan Peterman?

  Yeah, I saw that you wrote that, yeah, you spent one afternoon a week working, talking, and drinking beer at Dijkstra's house. And you kind of don't remember exactly who was in charge of what on that paper, but...

• 14:29Speaker 00

  Yeah. Well, I don't think I was really, could have gotten that drunk because I probably drove to the meeting and back from the meeting, so...

• 14:38Ryan Peterman?

  Right, right.

• 14:39Speaker 00

  The Dutch beer that I was drinking was not very alcoholic.

• 14:44Ryan Peterman?

  I wanted to talk about your most cited paper, the one titled "Time Clocks and the Ordering of Events in Distributed Systems." What's the story behind the paper and the problem you are solving with it?

• 14:56Speaker 00

  The origin was simple. Well, somebody sent me a paper on building distributed databases. And so where you'll have multiple copies of the data in 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 happening before means is not obvious,

• 15:40Speaker 00

  or not obvious to most people. But I happened to learn about special relativity. In particular, it's the spacetime view of special relativity, where you basically consider space and time together as one four-dimensional thing. And 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

• 16:22Speaker 00

  of what it means for one event to occur before another. And that notion is that one event happens before another if a signal...

• 16:37Speaker 00

  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 realized there was an obvious analogy. The notion of "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

• 17:22Speaker 00

  that were actually sent in the system. The thing that blew people away was this definition of "happens before" in a distributed system. Also, this was the first paper, I would call it, had a scientific result about distributed systems. I made, perhaps, a mistake that I 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 that condition,

• 18:05Speaker 00

  that if one event happened before the other, then that first event would be ordered before the other. 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, you know, 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.

• 18:50Speaker 00

  And so you just describe this state machine as just, you know, how commands affect the state and how they produce, and what, you know, 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.

• 19:33Speaker 00

  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 just 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. Concurrent 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.

• 20:17Speaker 00

  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, you know, 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 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,

• 21:02Speaker 00

  is to say, what is the property of the state at each point that ensures that the answer it produces is going to be correct? And that property, which is mathematically a Boolean-valued function of the state, is called an invariant. And understanding the invariant is the way to understand the system, you know, the program. And I realize that the same thing is true of concurrent systems and concurrent programs. People like to write behavioral proofs, reasoning about sequences.

• 21:43Speaker 00

  And the problem with that is that the number of sequences, possible sequences, you know, is exponential in the length of the sequence. While the com-- so your complexity of your reasoning gets to be very complicated. It's very easy to miss cases. But the complexity of an invariance proof, the complexity of the invariant, basically is... Well, okay, look, it's the number of possible executions is exponential in the number of processes. But the behavior of the proof of an invariance proof

• 22:28Speaker 00

  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 are 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...

• 23:09Speaker 00

  You know, thinking of partial orderings is, in fact, a very good way of doing it. But those are the exceptions. The work, the method that works, you know, that you can be sure will, will, will work is the use of invariance.

• 23:26Ryan Peterman?

  I want to talk about the, I guess, the next paper, which is the Byzantine generals problem. I think that's something that we hear about and we learn about when you're going through college and computer science. And the name's great, and I want to know the, the story behind that problem.

• 23:44Speaker 00

  After I wrote that type clocks paper, that was a, tells you how to build a distributed system, but assuming no failures. And it was obvious that, um, you know, distributed, one reason for distributed systems is you have multiple computers, so if one fails, you can, you know, keep going. Like, in particular, uh, that was the problem that was being solved at SRI when I, uh, when I joined it. But before I got to SRI, I started working on that problem. And I, uh, there's no notion of, idea of, you know, what I should think about is, you

• 24:27Speaker 00

  know, what, what can a failure do? So I assumed that, you know, the worst possible case, that a failed process might do absolutely anything. And I came up with an algorithm that basically would, uh, implement a state machine, uh, under that assumption. And that the algorithm I came out with used digital signatures, you know, so that it used the fact that a faulty process might do anything, but it could not forge the signature of another process.

• 25:02Ryan Peterman?

  Which just means that the message can be trusted, that it came from a prior

• 25:07Speaker 00

  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. Uh, and so, that is a solution using that. When I got to SRI, I realized that the people were trying to solve the same problem, uh, but there are two differences. First of all, at the time I did this was, you know, 1975. 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 Wit Diffie,

• 25:50Speaker 00

  who was one of the author, two authors of that paper,

• 25:55Speaker 00

  was a friend of mine. And in fact, at one point, we were at a coffee house, and he was describing these things, and he said, "We have this problem of building digital signatures,

• 26:08Speaker 00

  you know, and we haven't solved." And I said, "Oh, that seems easy enough." And I sat down, and literally on a napkin, I wrote out a, you know, 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 you're signing. It's not quite that bad, because, you know, as you might think, because you could use, sign not a, the entire document, but a hash of that document, which you assume, you know, people cannot forge.

• 26:52Ryan Peterman?

  The hash, or they can't reverse.

• 26:54Speaker 00

  Yeah, no, you can't revert, 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, 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,

• 27:26Speaker 00

  they would agree, have an algorithm for agreement on a single command. And then that algorithm would be

• 27:37Speaker 00

  executed multiple times to... And, you know, that was a nicer way of describing,

• 27:45Speaker 00

  you know, what you're doing than my method. So the first paper that was published used, gave both the, their original... Oh, so, but since they didn't have digital... Signatures, they used a 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.

• 28:29Speaker 00

  And the general one for N processes was really a work of genius. It was almost incomprehensible. You just had to read it, and this complicated proof that, you know, for the arbitrary case of an arbitrary number of processes, you need N pro-- for to tolerate N faults, you needed four N processes, whereas with digital signatures, you need three N processes. And the algorithm for a single fault wasn't hard, but the one for multiple parts was-- Marshall Pease was the one who did it, and he was just brilliant.

• 29:08Speaker 00

  Later, in a later paper, I discovered a simpler proof, a one that was an inductive proof, namely prove that if it works for N minus one, you know, it worked for N with 3N, it works for 3N times N minus one. The original paper was, you know, the original one was just brilliant. Who 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 Byz-- well, Byzantine fault is one that where a process, assume a process can do anything.

• 29:52Speaker 00

  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-process, 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--

• 30:28Speaker 00

  You know, 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, this works and 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 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

• 31:13Speaker 00

  some way of, of writing a digital signature algorithm that, you know, would have a sufficiently low probability of, of failing. But I never worked on that and nobody else ever did. So that, those, that algorithm was, was pretty much ignored because digital signatures were very expensive in those days. I don't know what's being done now because, you know, computers are, digital signatures are just computing and computing is, you know, is cheap. But I remember at some point I happened to be communicating with someone who was an engineer at Boeing.

• 31:58Speaker 00

  And I asked whether they knew about those results. And he said, yes, that he, in fact, was the one at Boeing who had 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.

• 32:26Speaker 00

  And I had learned one thing from Dijkstra. Dijkstra, you know, one of the things I learned from Dijkstra. He wrote this paper called "The Dining Philosophers' Problem", and that paper got a lot of attention. But the Dining Philosophers' Problem, I won't go into what it is, but I think the basic problem was not particularly interesting. 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.

• 33:04Speaker 00

  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, 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 attacked, you know, they would lose.

• 33:45Speaker 00

  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.

• 34:06Speaker 00

  And, you know, I called it the Byzantine Generals' Problem.

• 34:11Ryan Peterman?

  I saw in your, your notes about the 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?

• 34:22Speaker 00

  Oh, yeah, that, yeah, I was, there was a different problem that Jim Gray

• 34:31Speaker 00

  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, it's a 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 add and that, so it should have a different name."

• 35:16Speaker 00

  And then I realized that Byzantine, there aren't any Byzantium, Byzantines around. And that was the perfect name, so.

• 35:25Ryan Peterman?

  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 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?

• 35:50Speaker 00

  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 our airplane, fly airplanes. And the reason, in fact, because was, was that this was during the time of the oil crisis in the seventies. And that they knew, people knew that they could build more energy efficient planes by reducing the size, the size of the control surfaces. But that made the plane aerodynamically unstable. And a pilot couldn't make the, all the adjustments needed to, you know, to keep it flying, but a computer could.

• 36:30Speaker 00

  So it was clear the future was, you know, airplanes were going to be flying, being flown by computers, as they are, you know, today. And.

• 36:42Speaker 00

  People didn't realize, they thought that, oh, if you want to be able to tolerate one fault, you could just use three computers. And they didn't realize that 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.

• 37:02Ryan Peterman?

  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 based 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?

• 37:37Speaker 00

  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, disk Paxos, for example, was a case of that, that somebody actually wanted an algorithm to do it.

• 38:05Ryan Peterman?

  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.

• 38:17Speaker 00

  Well, the problem I was trying is exactly the same problem as I was solving in the Byzantine Generals 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 Paxos is an algorithm for...

• 38:49Speaker 00

  For building fault tolerant systems for handling that class of faults. And the people I was working at was the DEC CIRC lab. And that's what I joined in 1985. And they built a, one of 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 PARC and had invented personal computing.

• 39:33Speaker 00

  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, what they did was possible.

• 40:13Speaker 00

  Namely, I didn't think, well, I forget exactly why I didn't think it was possible. But anyway, I started, you know, trying to come up with an impossibility proof. And the impossibility proof, well, an algorithm to solve this would have to do this and it would have to do that. And at some point, I stopped and said, oh, this isn't a proof, this is an algorithm that does it.

• 40:45Ryan Peterman?

  You said that they had code, but not an algorithm?

• 40:50Speaker 00

  Yeah.

• 40:51Ryan Peterman?

  What do you mean by that?

• 40:53Speaker 00

  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 in 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 interested in algorithms. And an algorithm is something that's more abstract than a program.

• 41:35Speaker 00

  An algorithm can be, you know, a program is written in some particular code, but an algorithm can be implemented in 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, you know, even without realizing that that's what I was doing.

• 42:01Speaker 00

  And so, what I've spent a large part of my career, basically from maybe about, you know, 2,000 or so onward, was getting people who build concurrent systems

• 42:21Speaker 00

  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 distributed system to different computers. And that code...

• 42:48Speaker 00

  You know, it's very hard to get, you know, that correct. So you don't want to think in terms of code because that encoding, you know, 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.

• 43:11Ryan Peterman?

  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?

• 43:32Speaker 00

  Oh, well, the referees originally said, "Well, this paper is okay, you know, not terribly important," but fortunately Butler-Lamson realized the importance of the algorithm. And together with the idea of, you know, "I guess I can implement anything because it's implementing a state machine," and, you know, went about proselytizing, building your systems, you know, using Paxos, you know, and thinking in terms of state machines. And so, you know, I wasn't...

• 44:13Speaker 00

  So the idea was getting out, so I was in no hurry to publish. So, you know, I just let the paper 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 it needed revision. And so he decided that, yeah, let's, you know, publish it. And it was eventually published with a little, some, a few things.

• 44:51Speaker 00

  To take, well, to mention work that had been done in the interim. And what I got is, got a Keith Marzullo to do that part for me. And so the story was that this manuscript, this was that, well, the story about Paxos was that, you know, this 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 not interesting, you know, the paper would say, it's not clear how the Paxons, what the Paxons did, you know, at this point.

• 45:36Speaker 00

  But at any rate, and so Keith, you know, kept up that idea that, you know, this was a, you know, a description of this ancient thing. And he wrote, you know, a little prefix or a preface or something to it and, you know, added maybe, I think, some references.

• 46:03Ryan Peterman?

  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?

• 46:17Speaker 00

  Well, I think the lecture may have gone well, but I think nobody understood the algorithm, where nobody understood the significance of the algorithm.

• 46:27Ryan Peterman?

  It sounds like no one understood it, except for Butler Lamson. What, what did he see that made him unique, I guess?

• 46:35Speaker 00

  Well, he had a good understanding of building systems, you know, he really deserved his Turing Award. And he was one of the original people at Xerox PARC who were building distributed personal computing. Ian Chuck Thacker, I think, were probably the two senior people in that lab.

• 46:57Ryan Peterman?

  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.

• 47:12Speaker 00

  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 "Send it back to me when you have a proof." I forget which one it was. And I got the idea and they really, they did write, you know, add a proof in the paper.

• 47:38Speaker 00

  And I never read the later versions. And someone whose judgment I value, 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.

• 48:19Speaker 00

  And it turns out, you can do the first phase once for, it involves a leader.

• 48:30Speaker 00

  And the leader has to get elected. So, but it turns out that you can do the first phase once.

• 48:40Speaker 00

  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, the engineers, you know, like to think about it is, well, you do this, you know, you're talking about the first part. The second phase, you 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.

• 49:21Speaker 00

  And in fact, you know, when you start it from fresh, you don't have to do the first

• 49:29Speaker 00

  phase. You can, you're basically, what started 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.

• 49:44Speaker 00

  But, you know, the R A F people also had this idea that, you know, R A F 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 some people in five minutes and they understood it. At any rate, the R A F people said that one of the ideas were simpler because, and they even have, you know, Paxos to one class and R A F 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 R A F and fixed.

• 50:28Speaker 00

  But I believe that the algorithm that they found more understandable was one with that bug.

• 50:36Speaker 00

  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 Raff description gave them, you know, more of a warm, fuzzy feeling because, you know, you know, that that was seems to be the way, you know, programmers, like to think about the the algorithm, you know, you know, the second phase, you know, first until, you know, you get a failure.

• 51:16Speaker 00

  And but the way I describe it is one that helps you get a better understanding of why it actually works.

• 51:26Ryan Peterman?

  So, yeah, we talked about a lot of your papers. I know one of your other contributions, whether you knew it or not at the time, was LaTeX and building that and something that has impacted the entire academic community. What's the story behind wanting to build LaTeX?

• 51:46Speaker 00

  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 type setting 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 with a little extra effort, I could make macros usable by other people.

• 52:30Speaker 00

  The system I had been using before tech, it's called Scribe. And that really had, the basic idea of Scribe was that you describe the logical structure of of the document, not and the and Scribe will do the formatting. Well, Scribe didn't do that great a job of formatting, so but.

• 53:00Speaker 00

  Obviously, you know, I like the idea abstraction, that it's the ideas that matter, not the text that matters, you know, the writing that matters, not the typesetting. And so, I actually,

• 53:21Speaker 00

  at some point, I met Peter Gordon of Addison Wesley. I'm not sure what you would call them, but he looks for, you know, books to publish. And he convinced me that I should write a book on it. And those days, it never occurred to me, people would 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 typographic design that's in the standard latex styles.

• 54:02Speaker 00

  You know, basically, I just did that in my, quote, "spare time." You know, 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.

• 54:26Ryan Peterman?

  On the topic of writing, you have a quote that I really enjoy. It's, "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.

• 54:40Speaker 00

  Well, it was really meant for, you know, 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 want to use. Well, write a description of it. There's an old maxim that I don't, 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 definitely when I was writing the book and I discovered that something was hard to describe, hard to explain,

• 55:24Speaker 00

  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.

• 55:36Ryan Peterman?

  Why is writing conducive to good thinking?

• 55:41Speaker 00

  Because it's very easy to fool yourself. I mean, that underlies 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 math, PhD in math. I knew how to write proofs. And I was starting writing the proofs the way I would normally do.

• 56:21Speaker 00

  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 a computer science, you know how to deal with concurrency. It's hierarchical structure. And so I devised this hierarchical structure where a proof is, you know, is a sequence of steps, each of which has a proof. And the proof is either a, well, 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, you know, so you break the whole problem up into these smaller pieces.

• 57:06Speaker 00

  So there's never any question of, you know, where's this coming from? You know, you're stating that this step follows from, you know, this step, 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 that means your proof is wrong. Well, you know, so I've discovered that worked great on writing my proofs of programs. But I decided that really, you know, I also write proofs of theorems, you know.

• 57:37Speaker 00

  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 try to convince mathematicians to write these proofs, I started in one small seminar, I won't describe what it was about, but I described this proof to 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...

• 58:20Speaker 00

  I mean, 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 that mathematicians are afraid of, is that they're gonna 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, you know, 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.

• 59:05Speaker 00

  Nothing about, "Oh, I'm listening," or anything. You know, after I gave that talk, someone got up and said, "I don't want to have to write 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.

• 59:30Speaker 00

  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 real, 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 paper's errors can, you know, you know, come in. Because it really makes you honest.

• 1:00:02Ryan Peterman?

  When I look across your career, I think you had a lot of contributions people might expect, might 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?

• 1:00:20Speaker 00

  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 it was, you know, there could be a computer, a science of computing. It wasn't until, you know, maybe until mid to late seventies that I realized, yes, there was a computer science. I know as a computer scientist. But it never seemed to me that like computer science was an academic subject. At some point, I, you know, had to make a choice between doing computer science without calling it computer science

• 1:01:05Speaker 00

  or, or teaching math at a university. And I chose for random, fairly random reasons to do computer science. So, you know, for the first, I don't know.

• 1:01:26Speaker 00

  Well, till maybe the mid 80s or something. It just didn't seem to me that, you know, you know, computer science was something that people needed to go to 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, so.

• 1:01:49Ryan Peterman?

  I saw in your writing, you had a footnote that said somewhere that you, you you felt like a failure at some point because you 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?

• 1:02:08Speaker 00

  Lots of people, you know, a large percentage of the people who are doing things like I was doing, which is not a large number of people. There's this notion that

• 1:02:19Speaker 00

  they're looking for the Turing machine of concurrency. You know, the Turing machine was this abstraction which really captured what computing was.

• 1:02:31Speaker 00

  And they were looking for something that would be the, you know, the Turing machine of concurrent computing. And

• 1:02:47Speaker 00

  you know, nobody succeeded. I mean, there are some people who think they've succeeded. The patronets are or something that, I guess I don't have time to to explain it, but there was a big, there was a big in the 70s. And I was actually surprised to think that there's still a large community of people doing patronets. But what I now realize is that patronets 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 realized, in some sense, you know,

• 1:03:31Speaker 00

  maybe I've realized what the Turing machine of of of computing is, state machines.

• 1:03:37Speaker 00

  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, you know, to me, you know, that's the Turing machine of concurrency. But it doesn't have the function that Turing machines offer. Because it doesn't... What Turing machines do is describe what's possible.

• 1:04:18Speaker 00

  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, you know, 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.

• 1:05:03Speaker 00

  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 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.

• 1:05:45Speaker 00

  And that's what you use this mathematics... The state machine is described for me, by me, using mathematics. That's the right, you know, the most powerful way of doing it. But...

• 1:06:01Speaker 00

  Computer people, computer scientists and programmers are really hung up on languages. And so they are looking 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.

• 1:06:45Speaker 00

  But for understanding, you know, 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, to, to deal when you're trying to deal with concurrency.

• 1:07:06Ryan Peterman?

  When I look at everything that you've written and all the stories, there's these little anecdotes, there's things where you say things like you, 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, that doesn't connect with me because you've also won a Turing Award and done all these amazing things. So how could that be that you, you know, just merely discover things and are not smart, yet you've achieved so much?

• 1:07:48Speaker 00

  Well, this general thing that psychologists talk about is that when someone is good at something, they don't realize how good they are at it because it's simple to them.

• 1:08:08Speaker 00

  There's the opposite one, that people who are bad at something think they're better than they are because they're bad at it. Or to put a little bit more concisely, stupid people think they're smart because they're too stupid to realize they're not.

• 1:08:28Speaker 00

  The gift that I have is not, in some sense, raw intelligence. It's abstraction. And it's only recently, you know, last 10 or so years, that I realized how much better I am at that than other people, most other people.

• 1:08:50Ryan Peterman?

  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?

• 1:09:05Speaker 00

  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, you know, what I should have done, because that's a question that I don't have to answer.

• 1:09:25Ryan Peterman?

  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

• 1:10:10Ryan Peterman?

  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.