Leslie Lamport
Encyclopedia
Leslie Lamport is an American
computer scientist
. A graduate of the Bronx High School of Science
, he received a B.S.
in mathematics
from the Massachusetts Institute of Technology
in 1960, and M.A.
and Ph.D.
degrees in mathematics from Brandeis University
, respectively in 1963 and 1972. His dissertation was about singularities in analytic partial differential equation
s. Lamport is best known for his seminal work in distributed systems and as the initial developer of the document preparation system LaTeX
.
Professionally, Lamport worked as a computer scientist at Massachusetts Computer Associates, SRI International
, Digital Equipment Corporation
, and Compaq
. In 2001 he joined Microsoft Research
in Mountain View, California
.
These papers relate to such concepts as logical clocks (and the happened-before
relationship) and Byzantine failures. They are among the most cited papers in the field of computer science and describe algorithms to solve many fundamental problems in distributed systems, including:
Lamport is also known for his work on temporal logic
, where he introduced the temporal logic of actions
(TLA). Among his more recent contributions is TLA+, a logic for specifying and reasoning about concurrent and reactive systems, that he describes in the book “Specifying Systems: The TLA+ Language and Tools for Hardware and Software Engineers” and defines as a “quixotic
attempt to overcome engineers' antipathy towards mathematics”.
and Christian Albrechts University of Kiel
in 2003, EPFL in 2004 and University of Lugano
in 2006. In 2004, he received the IEEE Emanuel R. Piore Award
. In 2005, the paper “Reaching Agreement in the Presence of Faults” received the Dijkstra Prize
. In honor of Lamport's sixtieth birthday, a lecture series was organised at the 20th Symposium on Principles of Distributed Computing
(PODC 2001). In 2008, he received the IEEE John von Neumann Medal
. In 2011, he was elected to the United States National Academy of Sciences
.
:
United States
The United States of America is a federal constitutional republic comprising fifty states and a federal district...
computer scientist
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
. A graduate of the Bronx High School of Science
Bronx High School of Science
The Bronx High School of Science is a specialized New York City public high school often considered the premier science magnet school in the United States. Founded in 1938, it is now located in the Bedford Park section of the Bronx...
, he received a B.S.
Bachelor's degree
A bachelor's degree is usually an academic degree awarded for an undergraduate course or major that generally lasts for three or four years, but can range anywhere from two to six years depending on the region of the world...
in mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
from the Massachusetts Institute of Technology
Massachusetts Institute of Technology
The Massachusetts Institute of Technology is a private research university located in Cambridge, Massachusetts. MIT has five schools and one college, containing a total of 32 academic departments, with a strong emphasis on scientific and technological education and research.Founded in 1861 in...
in 1960, and M.A.
Master's degree
A master's is an academic degree granted to individuals who have undergone study demonstrating a mastery or high-order overview of a specific field of study or area of professional practice...
and Ph.D.
Doctor of Philosophy
Doctor of Philosophy, abbreviated as Ph.D., PhD, D.Phil., or DPhil , in English-speaking countries, is a postgraduate academic degree awarded by universities...
degrees in mathematics from Brandeis University
Brandeis University
Brandeis University is an American private research university with a liberal arts focus. It is located in the southwestern corner of Waltham, Massachusetts, nine miles west of Boston. The University has an enrollment of approximately 3,200 undergraduate and 2,100 graduate students. In 2011, it...
, respectively in 1963 and 1972. His dissertation was about singularities in analytic partial differential equation
Partial differential equation
In mathematics, partial differential equations are a type of differential equation, i.e., a relation involving an unknown function of several independent variables and their partial derivatives with respect to those variables...
s. Lamport is best known for his seminal work in distributed systems and as the initial developer of the document preparation system LaTeX
LaTeX
LaTeX is a document markup language and document preparation system for the TeX typesetting program. Within the typesetting system, its name is styled as . The term LaTeX refers only to the language in which documents are written, not to the editor used to write those documents. In order to...
.
Professionally, Lamport worked as a computer scientist at Massachusetts Computer Associates, SRI International
SRI International
SRI International , founded as Stanford Research Institute, is one of the world's largest contract research institutes. Based in Menlo Park, California, the trustees of Stanford University established it in 1946 as a center of innovation to support economic development in the region. It was later...
, Digital Equipment Corporation
Digital Equipment Corporation
Digital Equipment Corporation was a major American company in the computer industry and a leading vendor of computer systems, software and peripherals from the 1960s to the 1990s...
, and Compaq
Compaq
Compaq Computer Corporation is a personal computer company founded in 1982. Once the largest supplier of personal computing systems in the world, Compaq existed as an independent corporation until 2002, when it was acquired for US$25 billion by Hewlett-Packard....
. In 2001 he joined Microsoft Research
Microsoft Research
Microsoft Research is the research division of Microsoft created in 1991 for developing various computer science ideas and integrating them into Microsoft products. It currently employs Turing Award winners C.A.R. Hoare, Butler Lampson, and Charles P...
in Mountain View, California
Mountain View, California
-Downtown:Mountain View has a pedestrian-friendly downtown centered on Castro Street. The downtown area consists of the seven blocks of Castro Street from the Downtown Mountain View Station transit center in the north to the intersection with El Camino Real in the south...
.
Research and publications
Lamport’s research contributions have laid the foundations of the theory of distributed systems. Among his most notable papers are- “Time, Clocks, and the Ordering of Events in a Distributed System”, which received the PODC Influential Paper AwardDijkstra PrizeThe Edsger W. Dijkstra Prize in Distributed Computing is given for outstanding papers on the principles of distributed computing, whose significance and impact on the theory and/or practice of distributed computing has been evident for at least a decade...
in 2000, - “How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs”, which defined the notion of Sequential consistencySequential consistencySequential consistency is one of the consistency models used in the domain of concurrent programming . It was first defined as the property that requires that ".....
, - “The Byzantine Generals' Problem”,
- “Distributed Snapshots: Determining Global States of a Distributed System” and
- “The Part-Time Parliament”.
These papers relate to such concepts as logical clocks (and the happened-before
Happened-before
In computer science, the happened-before relation is a means of ordering events based on the potential causal relationship of pairs of events in a concurrent system, especially asynchronous distributed systems...
relationship) and Byzantine failures. They are among the most cited papers in the field of computer science and describe algorithms to solve many fundamental problems in distributed systems, including:
- the Paxos algorithmPaxos algorithmPaxos is a family of protocols for solving consensus in a network of unreliable processors.Consensus is the process of agreeing on one result among a group of participants...
for consensusConsensus (computer science)Consensus is a problem in distributed computing that encapsulates the task of group agreement in the presence of faults.In particular, any process in the group may fail at any time. Consensus is fundamental to core techniques in fault tolerance, such as state machine replication.- Problem...
, - the bakery algorithmLamport's bakery algorithmLamport's bakery algorithm is a computer algorithm devised by computer scientist Leslie Lamport, which is intended to improve the safety in the usage of shared resources among multiple threads by means of mutual exclusion....
for mutual exclusionMutual exclusionMutual exclusion algorithms are used in concurrent programming to avoid the simultaneous use of a common resource, such as a global variable, by pieces of computer code called critical sections. A critical section is a piece of code in which a process or thread accesses a common resource...
of multiple threads in a computer system that require the same resources at the same time and - the snapshot algorithm for the determination of consistent global states.
Lamport is also known for his work on temporal logic
Temporal logic
In logic, the term temporal logic is used to describe any system of rules and symbolism for representing, and reasoning about, propositions qualified in terms of time. In a temporal logic we can then express statements like "I am always hungry", "I will eventually be hungry", or "I will be hungry...
, where he introduced the temporal logic of actions
Temporal Logic of Actions
Temporal logic of actions is a logic developed by Leslie Lamport, which combines temporal logic with a logic of actions.It is used to describe behaviours of concurrent systems.- Details :...
(TLA). Among his more recent contributions is TLA+, a logic for specifying and reasoning about concurrent and reactive systems, that he describes in the book “Specifying Systems: The TLA+ Language and Tools for Hardware and Software Engineers” and defines as a “quixotic
Quixotism
Quixotism is impracticality in pursuit of ideals, especially those ideals manifested by rash, lofty and romantic ideas or extravagantly chivalrous action. It also serves to describe an idealism without regard to practicality...
attempt to overcome engineers' antipathy towards mathematics”.
Honors
Lamport received four honorary doctorates from European universities: University of RennesUniversity of Rennes 1
The University of Rennes 1 is one of the two main universities in the city of Rennes, France. It is under the Academy of Rennes. It specializes in science, technology, law, economy, management and philosophy. The University of Rennes 1 has been in existence since 1969, but its heritage stems back...
and Christian Albrechts University of Kiel
University of Kiel
The University of Kiel is a university in the city of Kiel, Germany. It was founded in 1665 as the Academia Holsatorum Chiloniensis by Christian Albert, Duke of Holstein-Gottorp and has approximately 23,000 students today...
in 2003, EPFL in 2004 and University of Lugano
Università della Svizzera italiana
Università della Svizzera italiana is a public university located in Lugano, Switzerland, founded in 1996...
in 2006. In 2004, he received the IEEE Emanuel R. Piore Award
IEEE Emanuel R. Piore Award
The IEEE Emanuel R. Piore Award is a Technical Field Award given each year by the IEEE to an individual or small team that has made outstanding contributions to information processing systems in relation to computer science. The award is named in honor of Emanuel R. Piore.The award was established...
. In 2005, the paper “Reaching Agreement in the Presence of Faults” received the Dijkstra Prize
Dijkstra Prize
The Edsger W. Dijkstra Prize in Distributed Computing is given for outstanding papers on the principles of distributed computing, whose significance and impact on the theory and/or practice of distributed computing has been evident for at least a decade...
. In honor of Lamport's sixtieth birthday, a lecture series was organised at the 20th Symposium on Principles of Distributed Computing
Symposium on Principles of Distributed Computing
The Symposium on Principles of Distributed Computing is an academic conference in the field of distributed computing organised annually by the Association for Computing Machinery ....
(PODC 2001). In 2008, he received the IEEE John von Neumann Medal
IEEE John von Neumann Medal
The IEEE John von Neumann Medal was established by the IEEE Board of Directors in 1990 and may be presented annually "for outstanding achievements in computer-related science and technology." The achievements may be theoretical, technological, or entrepreneurial, and need not have been made...
. In 2011, he was elected to the United States National Academy of Sciences
United States National Academy of Sciences
The National Academy of Sciences is a corporation in the United States whose members serve pro bono as "advisers to the nation on science, engineering, and medicine." As a national academy, new members of the organization are elected annually by current members, based on their distinguished and...
.
Miscellaneous
Lamport is the author of the aphorismAphorism
An aphorism is an original thought, spoken or written in a laconic and memorable form.The term was first used in the Aphorisms of Hippocrates...
:
See also
- Lamport signature – The Lamport one-time signature scheme is a method for constructing a digital signature.
- S/KEYS/KEYS/KEY is a one-time password system developed for authentication to Unix-like operating systems, especially from dumb terminals or untrusted public computers on which one does not want to type a long-term password. A user's real password is combined in an offline device with a short set of...
– a one-time password system sometimes referred to as Lamport's scheme