Leslie Lamport

Leslie Lamport

2019 Fellow

For his contributions to the analysis and design of distributed computer systems, and for the initial creation of the LaTeX document production system.

Biography

Leslie Lamport was born in New York City in 1941. Over a career spanning five decades, Lamport has made multiple groundbreaking contributions to the theory and practice of distributed and concurrent computing systems, insights that have dramatically improved the performance and reliability of such systems. Equally foundational, but in a completely different field of computing, Lamport developed the initial version of the LaTeX document preparation system, an extension of Donald Knuth’s TeX system—both world standards for composing and publishing scientific documents. Lamport’s papers on logical correctness, concurrency, and multiprocessor computing are some of the most frequently cited articles in all of computer science, essentially laying the foundations for the theory of distributed systems.

Lamport graduated from MIT in 1960 with a bachelor’s degree in mathematics and then attended Brandeis University for a master’s and doctorate in mathematics (1972), while working part-time, from 1962–1965, at the Mitre Corporation. His thesis focused on partial differential equations. Lamport’s professional career began in 1970 at Massachusetts Computer Associates (until 1977), SRI International from 1977 to 1985, and Digital Equipment Corporation and Compaq from 1985 to 2001. Since 2001 he has been with Microsoft Research, where he is a Distinguished Scientist.

Lamport’s decision to work in industry, instead of academia, was by design: he prefers working on real-world problems faced by computer developers—hardware and software—and saw early on that there were some particularly poorly understood aspects of computer science that were holding back progress. Many of Lamport’s deepest contributions are philosophically rooted in much simpler, often day-to-day problems. For example, he expressed the computing issue of concurrency—multiple processes “in flight” to the computer’s main processor—in terms of customers at a bakery and how they might organize themselves so that only one customer (process) had access to the cashier (CPU) at one time. In the first instance, people just take a number and wait their turn. But there are other subtleties that can occur and the “Bakery Algorithm” can be extended to account for them; the Bakery model itself has been a recurring theme in Lamport’s work, inspiring him to generate several other seminal insights into concurrency based on the general idea. This algorithm now appears in undergraduate computer science textbooks around the world.

Another area in which he made major contributions was with the notion of fault tolerance, the idea that computer systems can be designed and built to withstand occasional, limited failures or bad data. While working on a cockpit avionics control system for NASA at SRI in the early 1970s, he identified the notion of the “Byzantine Generals” model, an approach that sees the computer processor as an army general trying to coordinate the actions of his troops, while also accounting for traitors in the army that will deliberately send conflicting signals. Lamport was a member of the group that identified and first studied the problem of tolerating “Byzantine” failures in which a computer might do anything, including acting maliciously.

Lamport’s other contributions are equally profound and foundational to computer science. If you use a computer today, you are benefitting from Lamport’s deep thinking as well as his fundamental algorithms.