Turing Lecture
To Edsger Dijkstra

It is insufficiently considered that men more often require to be reminded than informed.

Samuel Johnson

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
The Computer
Science of
Concurrency:
The Early
Years
DOI: 10.1145/2771951
Leslie Lamport is the recipient
of the 2013 ACM A.M. Turing Award.