The Laureates

Copyright © Klaus Tschira Stiftung / Peter Badge

Leslie Lamport

Born 7 February 1941, New York, New York, USA

ACM A.M. Turing Award (2013) “for fundamental contributions to the theory and practice of distributed and concurrent systems, notably the invention of concepts such as causality and logical clocks, safety and liveness, replicated state machines, and sequential consistency.”

Leslie Lamport took his bachelor’s degree in mathematics at the Massachusetts Institute of Technology (1960), before starting work at Mitre Corporation between 1962 and 1965. At the same time he continued his studies and received his master’s degree at the Brandeis University in 1963. From 1965 until 1969 he taught mathematics at Marlboro College; in 1972, he took his doctorate with a thesis in analysis (“The Analytic Cauchy Problem with Singular Data”). Between 1970 and 1977 he worked for Massachusetts Computer Associates, before moving to SRI International, followed by his work as a Senior Consulting Engineer at Digital Equipment Corporation/Compaq between 1985 and 2001. Since 2001 he has been working for Microsoft Research.

Leslie Lamport received the Dijkstra Prize three times, namely for his paper “Time, Clocks, and the Ordering of Events in a Distributed System” (2000), the paper “Reaching Agreement in the Presence of Faults” (2005, together with Robert Shostak and Marshall Pease), and for the work “Distributed Snapshots: Determining Global States of Distributed Systems” (2014, together with Mani Chandy). Additionally, the IEEE awarded him the Emanuel R. Piore Award (2004) and the John von Neumann Medal (2008). He holds five honorary doctorates and he is a member of the US-American National Academy of Sciences (2011).

For several decades, Leslie Lamport has been focusing on so-called “distributed systems”. These are systems of several processors, which can communicate with each other and which are performing calculations without a “chief processor” that is supervising or coordinating the computations.

The aim is to construct distributed systems and the algorithms they are running in such a way that a clear and well defined order on the computations is established by itself. To avoid chaos in distributed systems, he developed in the 1970s the socalled Lamport Clocks. These are logical clocks – essentially counters running in each processor and stepping forward, when messages are being received or sent out – which are producing timestamps to mark the messages between the processors. In this way it is possible to reconstruct who is responsible for which computation and to build a consistent overall result from the intermediary results. The paper “Time, Clocks, and the Ordering of Events in a Distributed System” from 1978 has become one of the most cited works in computer science.

Moreover, Lamport developed a temporal logic, which allows to build a time dependence into logical statements, which he subsequently developed into a “temporal logic of actions” (TLA), in order to analyse parallel running algorithms.

Lamport has also contributed to cryptography, inventing the first digital signature algorithm, which is mentioned in Diffie & Hellman’s seminal paper that introduced public key cryptography.

Leslie Lamport gave many of his ideas small fictional settings. A famous example is the Byzantine Generals Problem: some generals who are communicating via messengers want to fix the point of time when they attack together – but they cannot be sure if there are traitors among them. Lamport showed together with Robert Shostak and Marshall Pease in 1982 that the generals can indeed arrive at an agreement in spite of the double crossers, if they use the proper protocol.

Lamport is also famous for his software package LaTeX that made Donald E. Knuth’s typesetting software TeX easier to use.