Facilitating the Spread of Knowledge and Innovation in Professional Software Development

Write for InfoQ


Choose your language

InfoQ Homepage News Leslie Lamport on Distributed Systems and Precise Thinking

Leslie Lamport on Distributed Systems and Precise Thinking

Lire ce contenu en français

Leslie Lamport is the author of some of the most cited computer science papers and won a Turing Award in 2013 for his seminal work in distributed and concurrent systems. This is a summary of an interview that Lamport gave to Software Engineering Radio touching themes such as his early work in distributed systems and the importance of precise thinking in programming.

The early years

Lamport's interview begins reconstructing his discovery that causality, i.e., the notion that one event can coarsely affect another depending on whether or not information from one can physically reach the other, is as important in distributed systems as it is in special relativity. This intuition was the base for his Time, Clocks, and the Ordering of Events in a Distributed System paper, where he came to the realization that any system can be described as a state machine and proposed an algorithm that could implement an arbitrary state machine in a distributed system.

The next major step, as Lamport defines it, was introducing the concept of failure into his algorithms. Again, intuition drove him to consider that to treat the possibility of failures, we need to take real time into account. So, the basic notion of failure was for a process not to be able to respond in a given time. Yet, this idea of failure was, in Lamport's words, a bit naïve, since it did not take into account the possibility of a process computing the wrong result. This gave birth to the notion of Byzantine failures, which basically invalidated the idea of handling failures by majority voting. In majority voting, you need three systems so you can use voting on their outputs and as long as two of them are correct, you get the right result. If Byzantine failures are considered, this approach does not work anymore because of the possibility of a system reporting different results to different processes.

The paper about Byzantine generals introduced the use of an allegory or metaphor in order to describe complex problems, an approach that Lamport also took in The Part-Time Parliament paper. Lamport recounts how this idea of telling stories was due to Dijkstra's and his dining philosophers problem, which proved an effective way to make a problem popular and get people's attention. Unfortunately, the part-time parliament metaphor did not work out as expected and possibly delayed the appreciation of the Paxos algorithm) by a decade. Lamport also mentions that one of the concepts that were introduced in this paper is that of "leases", i.e., the idea of assigning a resource to a system for a limited time, so it can be reclaimed and reused even in case that system stops working.

Thinking for programmers

The next topic in the interview is introduced through a talk that Lamport gave on the topic "Thinking for programmers." Lamport's thesis is that a lot of the problems that exist in writing and building a system are caused by not thinking about what you were doing before starting to code.

Success really depends on the conception of problems, the design of the system, not on the details of how it's coated.

The biggest point that Lamport tries to convey here is that for many tasks where no established solution is available, "you need to stop and think [...] before you start coding and the thinking is really independent of the coding process," it applies equally no matter what language you are using. Computational complexity is one of the aspect of design that Lamport says should be well thought out, another one being simplicity.

You're not to come up with a simple design through any kind of coding techniques or any kind of programming language concepts. Simplicity has to be achieved above the code level before you get to the point which you worry about how you actually implement this thing in code.

This leads directly into Lamport's main area of interest today, which is specification and verification. A specification can be anything, "from a few English sentences to a completely formal mathematical description of what or how to program is supposed to do things," and all specification types can be effectively used depending on the context. According to Lamport, the most important attribute of a specification is precision. That is the reason why he uses mathematics, and the reason why he rejects the use of UML, "a language [that] was invented first and then people came around and try to get semantics."

One idea about formal specifications that Lamport tries to dispel is that they require mathematical capabilities that are not available to programmers: "The mathematics that you need in order to write specifications is a lot simpler than any programming language [...] Anyone who can write C code, should have no trouble understanding simple math, because C code is a hell of a lot more complicated than" first-order logic, sets, and functions. The most complex part of the equation is then acquiring the discipline required to write a formal specification, above all when a programmer has never done that before.

The benefit of using [a formal specification language] is that it teaches you to think rigorously, to think precisely, and the important point is the precise thinking. So what you need to avoid at all costs is any language that's all syntax and no semantics.

Leslie is employed by Microsoft Research and has recently been working with TLA+, a logic which combines temporal logic with a logic of actions and is used to describe behaviours of concurrent systems. He is also the creator of the document preparation tool LaTex

Rate this Article