To Edsger Dijkstra
It is insufficiently considered that men more often require
to be reminded than informed.
I don’t know if concurrency is a science, but it is a field
of computer science. What I call concurrency has gone by
many names, including parallel computing, concurrent programming, and multiprogramming. I regard distributed
computing to be part of the more general topic of
concurrency. I also use the name algorithm for what
were once usually called programs and were generally
written in pseudo-code.
This is a personal view of the first dozen years of the
history of the field of concurrency—a view from today,
based on 40 years of hindsight. It reflects my biased per-
spective, so despite covering only the very beginning
of what was then an esoteric field, it is
far from complete. The geneses of my
own contributions are described in
comments in my publications web page.
The omission that would have seemed
most striking to someone reading this
history in 1977 is the absence of any
discussion of programming languages.
In the late 1960s and early 1970s, most
papers considered to be about concurrency were about language constructs for
concurrent programs. A problem such
as mutual exclusion was considered to
be solved by introducing a language construct that made its solution trivial. This
article is not about concurrent programming; it is about concurrent algorithms
and their underlying principles.
The Beginning: Mutual Exclusion
The Problem. While concurrent program execution had been considered
for years, the computer science of concurrency began with Edsger Dijkstra’s
seminal 1965 paper that introduced the
mutual exclusion problem.
5 He posed
the problem of synchronizing N
processes, each with a section of code
called its critical section, so that the following properties are satisfied:
Mutual Exclusion. No two critical sections are executed concurrently.
(Like many problems in concurrency, the goal of mutual exclusion
is to eliminate concurrency, allo wing us to at least pretend that
everything happens sequentially.)
Livelock Freedom. If some process is
waiting to execute its critical section, then some process will eventually execute its critical section.
Mutual exclusion is an example of what
is now called a safety property, and livelock freedom is called a liveness property. Intuitively, a safety property asserts
that something bad never happens; a
liveness property asserts that something
good must eventually happen. Safety and
liveness were defined formally in 1985.1
Dijkstra required a solution to allow
any computer to halt outside its critical
section and associated synchronizing
BY LESLIE LAMPORT
Leslie Lamport is the recipient
of the 2013 ACM A.M. Turing Award.