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

Lamport drew the notion of 'happens before' from special relativity: just as one event can influence another via light-speed-limited signals in physics, in distributed systems one event can influence another via messages actually sent in the system; this is the fundamental notion of causality in distributed computing.

“I happen to you know learn about you know special relativity in particular uh what's known as the it's the space-time view of of special relativity where you basically consider space and time together just one four-dimensional thing and that was Einstein wrote his paper in 1905 and and in I think it was 1909 uh somebody whose name I'm blocking on provided this four-dimensional view and that four-dimensional view has the the particular notion of what it means for one pro one event to occur before another and that notion is that one event happens before another. If a a signal uh was emitted from the first event and received by the 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. Uh 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 that were actually sent in the system.”

The insight that 'happens before' could be formalized mathematically blew people away because it provided a precise definition of causality in distributed systems, whereas before the notion of what it means for one event to occur before another in a distributed system was vague and obvious to most people.

“The thing that you know blew people away was this this definition of of happens before in a distributed system with also this was the first paper I would call like you know had a scientific result about distributed systems.”

Writing an instruction manual before coding forces the developer to discover design flaws and necessary changes—when writing the LaTeX book, Lamport discovered things that were hard to explain, requiring him to revise the design.

“it was really meant for, you know, people building computer systems. You have an idea and you think it's going to work. Uh 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. Uh there's an old maxim that I don't I heard uh that is you know write the instruction manual before you write the program. a great advice. Uh I did not do that uh with latte but it I definitely when I was writing the book and I discovered that something was hard to to describe hard to explain that needed to be changed and I made you know a number of uh of changes to it uh as a result of that”

The bakery algorithm has the remarkable property that it does not require atomic (all-or-nothing) writes to shared memory: if one process reads a register while another is writing to it, the reader can get any arbitrary value and the algorithm still works correctly.

“The amazing thing about the bakery algorithm was that it didn't require that assumption. It it used uh each shared memory a piece of memory was only written by a single process. So it didn't have to worry about two processes interfering with each other. The only problem that you might come is that somebody reading the uh 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 was being written that process reading process could get absolutely any value and the algorithm still worked.”

The origin of the time-sharing problem was that computers were expensive and fast, so they could be used simultaneously by multiple people whose programs would compete for shared resources like printers, requiring synchronization to prevent garbled output.

“computers were worked faster than humans and so and computers were very expensive in those days. So uh 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.”

The bakery algorithm was inspired by the deli ticket system, where customers take a numbered ticket and the lowest remaining number is served next, adapted to work without central control by having each process choose its own ticket number.

“I came up with the bakery algorithm which was inspired by uh the idea came from you know what now called the deli problem where you have a deli counter and that collects you know tickets a roll of tickets and every customer would come in and take a ticket and then the the next person s to to be served would be the one with the highest the lowest numbered ticket uh that hadn't been served yet. And basically that I took that idea uh but since uh there was no central server uh or at least the the problem is as specified by Dystra involved no central control. Each process basically had to choose their own ticket.”

The Byzantine generals problem arose from Lamport's work on fault-tolerant state machines at SRI, where the challenge was how systems could reach agreement when some processes might fail arbitrarily (do 'anything')—including sending malicious or contradictory messages.

“distributed one reason for a distributed systems is you have multiple computers so if one fails you can you know keep going. in particular uh that was the problem that it was being solved at SRRI when I uh when I joined it but before I got to SRRI and 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 know what what can a failure do so I assume that you know the worst possible case that a failed process might do absolutely anything.”

Lamport's initial Byzantine generals algorithm used digital signatures, which allowed it to tolerate one faulty process with three total processes, whereas algorithms without signatures required four processes—a critical difference for practical systems.

“algorithm that would uh implement a state machine uh under that assumption and that the algorithm I came out with used digital signatures. Yeah. So that it used the fact that a faulty process might do anything but it could not forge the signature of another process uh which just means that the message can be trusted that it came from a private uh 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”

The Byzantine generals problem is practically important because computers will fly aircraft, and during the 1970s oil crisis engineers realized that fuel-efficient aircraft must be aerodynamically unstable (smaller control surfaces), which pilots cannot control—only computers can make the necessary adjustments.

“this one it was because you know the 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 the oil crisis in the 70s and that they knew people knew that they could build more energyefficient planes by reducing the size the the size of the control surfaces. But that made the plane aerodynamically unstable. Uh and a a pilot couldn't make the all the adjustments needed to, you know, to keep it flying, but a computer could.”

There was an eight-year gap between when Lamport developed the Paxos algorithm (in the late 1970s) and when the 'Part-Time Parliament' paper was finally published (in 1998), during which the paper sat with acceptance but no publication because the original referees thought it was 'okay' but 'not terribly important.'

“I was looking at the Paxos paper and uh some of your notes about it and I saw that um there's a there's an eight-year gap between when you came up with the algorithm and when the the paper was actually published called Part-Time Parliament is the name of the paper. Why why is there an eight-year gap? Oh, well the re the referees originally said well this paper is okay you know not terribly important but fortunately butler Lamson realized the importance of the algorithm”

Lamport simplified Dijkstra's concurrent garbage collection algorithm by recognizing that the free list handling—which Dijkstra had made a special process—could be integrated into the regular data structure, requiring no special handling.

“I looked at it and I realized that uh I could simplify the algorithm. Uh because he had some some spe the 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 uh uh the processes that were using the memory. And I realized that that free list could just be made part of the regular data structure. uh so it didn't need special handling”

Understanding a concurrent program requires identifying invariants—boolean-valued properties of the state that, if true at each step, guarantee the output is correct—and reasoning about invariants rather than behavioral sequences reduces complexity from exponential to quadratic in the number of processes.

“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 that tells the program what to do next is its current state. And the way to understand uh 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 is correct is going to be correct. And that property which is mathematically a fun a boolean valued function of the state is called an invariant. And understanding the invariant is the way to understand the system.”

The problem Lamport encountered in building distributed databases was that the original solution would execute actions as if they occurred in a sequence, but that sequence could be different from the actual order in which they happened—a violation of the causal consistency that Lamport's 'happens before' relation was designed to capture.

“somebody sent me a paper on building distributed databases and so where you'll have well 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 the se that it it had the property that things would be executed as if they occurred in subsequence but that sequence could be different from the sequence in which they actually happened.”

A state machine is defined by its state and a next-state relation: each command takes the system from one state to another, with correctness determined by invariants—boolean-valued properties of the state that ensure correct output regardless of what happened in the past.

“A state machine as as I described it then is something that has a state and process executes you know uh commands that need to be executed in order and the command simply is something that makes a change of the state and and produces a value.”

At DEC (Digital Equipment Corporation), which Lamport joined in 1985, they had built one of the first distributed operating systems with all computers on an Ethernet network sharing common storage, maintaining consistency via algorithms rather than explicit code.

“the it was the dec circ was in which I joined in 1985 and they built a uh one of the first operating systems that uh was a a distributed operating system. Uh so that um basically everybody had the 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 and they invented the Ethernet uh you know for that. So they basically all of the uh computers in the building were on a single Ethernet network and shared a common storage uh and they had an algorithm for maintaining consistency of that storage”

When Lamport first presented the Paxos paper at a lecture dressed as an archaeologist (playing up the fictional 'ancient Greek parliament' framing), the audience may have enjoyed the presentation, but they did not understand the algorithm or its significance.

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

Edsger Dijkstra invented the formal theory of concurrent programming in a 1965 paper by introducing the concept of critical sections—pieces of code that at most one process can execute at a time—as a way to structure programs as collections of semi-independent tasks that must synchronize.

“the problem was invented or discovered by Edkar Dystra in a 1965 I think it was 1965 paper and that began I consider that really the beginning of the theory of uh concurrency concurrent programming. He was the first one who really made use of the idea of of concurrency as a way of structuring programs as a as a collection of semi-independent tasks and the processes have to uh synchronize with one another.”

Much research in distributed systems theory attempts to use partial orderings and behavioral proofs, which is not the practical way to build systems; the method that reliably works is invariance proofs, though there are exceptions like the bakery algorithm where partial orderings are useful.

“for a long time that you know people you know doing uh distributed systems theory are trying to do it uh 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 that's not the way to do it and I shouldn't say you know it's not the way uh you know there are algorithms like the bakery algorithm that you know you know thinking in partial orderings is in fact a very good way of doing it but those are the exceptions the the work the method that works you know that you can be sure will will will work is the use of invariance”

Computer people and programmers are 'really hung up on languages,' inventing languages and believing they improve thinking, but for understanding and reasoning about systems, mathematics beats any programming language.

“but computer people and 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 uh you know this language ES improves your thinking. uh it doesn't you may I mean there are reasons why you use computer languages and you don't write your your programs code in math and they involve basically efficiency but for understanding you know you can't beat math and you know attempts to uh do it by something that looks like a programming language uh is is just the wrong way to to to deal when you're trying to deal with concurrency.”

Dijkstra's original solution to the critical section problem had the defect that processes could be starved—an individual process might never get access to the critical section if other processes kept entering.

“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 uh enter their critical section uh an individual process might be starved. might never get access to to the critical section”

The SRI team developed a simpler abstraction for the Byzantine problem: rather than getting agreement on a sequence of commands, they created an algorithm for agreement on a single command and executed it repeatedly—this was a nicer abstraction than Lamport's sequence-based approach.

“the people at SRRI 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, uh they would agree have an algorithm for agreement on a single command and then that algorithm would be uh executed multiple times to and you know that was a nicer way of of describing uh you know what you're doing than than the than than my method.”

An algorithm is more abstract than a program—it can be implemented in any programming language, whereas a program is concrete code in a specific language; thinking in terms of algorithms rather than code is crucial for concurrent systems.

“when most people sit down and start writing programs that 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 in the days when I started writing 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 that wasn't wasn't talking about programs. I was talking about al interested in algorithms. Uh and an algorithm is something that's more abstract than a pro than than a program. U an algorithm can be you know a program is written in in some particular code. But an algorithm can be implemented if programs written in any any kinds of code.”

Paxos has two phases: a leader-election phase (phase 1) that can be done once, then a sequence of decision phases (phase 2) that repeat as long as the same leader exists; when the leader fails, a new leader must be elected (phase 1 again) before phase 2 continues.

“The basic idea of the what Paxos works is it's two phases and you're trying to implement a sequence of you know of decisions and it turns out you can do the first phase once for a whole it involves a leader. So um and the leader has to get elected. Uh so but it turns out that you can do the first uh phase once uh and you don't have to do it again as long as you have the same leader. Uh but it's only the second part that you have to do and then you have to elect the the new leader if a new leader fails and do the first part.”

When describing algorithms, Lamport talks about variables that can hold any integer, not just finite-precision integers—a deliberate abstraction that simplifies reasoning, not a complication; infinity was introduced into mathematics to simplify arithmetic, not complicate it.

“For example uh when I describe a uh an algorithm I will talk about you know the values of a variable you know can be any integer. Now you can implement the program where you have any integer uh but that makes the but talking about you know computer integers would complicate things unnecessarily. The 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 restricted to a finite set of integers, arithmetic becomes much more complicated.”