General Background

Wikipedia and links from there.

Turing Awards

Computer Science has no Nobel prize. The nearest we have is the Turing award. I've asked generations of Chalmers/GU students in computer science what this award is, who has won it, and for what. They typically have no idea. I think this reflects a failing on the part of the department, so here is a first attempt to fix our lack of historical awareness.

Below is a list of researchers who won the Turing award mostly for work in concurrency, though many of the other winners too did related work.


You can read their acceptance speeches (the Turing lectures), and all the others, at


The others you should read are, at least,

  1. Clarke, Emerson and Sifakis (2007).
  2. Wirth (1984).
  3. Floyd (1978).

You will no doubt be tempted by the titles of several of the others. Give in! In fact, glancing through the whole lot (they are all informal and easy to read) will introduce you to several other related issues, whether to do with computers or programming languages, and is an excellent way to get a broad liberal computer science education. Learn from the masters!

The talks also frequently mention other researchers who did not get the Turing award (they only give one a year). It's useful to pick up names.

Classic Papers

Many of the papers below are still under copyright, so we cannot give a direct link. Instead, you will have to get them from the Chalmers library. Search with the paper title, except if otherwise indicated.

Robin Milner.

If I had to pick one person whose collected works give you a liberal education in computer science, it would be Robin Milner. The wikipedia page

gives a starting point, as do


Items 1 and 2 below deal with papers by others describing Milner's work.

  1. A Brief Scientific Biography of Robin Milner
    by Gordon Plotkin, Colin Stirling & Mads Tofte,
    available at

    runs to 16 pages, followed by a 7 page bibliography. And Milner wrote strikingly little, though almost everything he wrote started a huge amount of research activity.
    There were any number of tributes paid to Milner in the months and years after he passed away in 2010, but the three below suffice to give a glimpse of the range of his work.

    • Robin Milner, a Craftsman of Tools for the Mind
      by Plotkin, G.D.
      Logic in Computer Science (LICS), 2010 25th Annual IEEE Symposium on
      DOI: 10.1109/LICS.2010.31
      Publication Year: 2010 , Page(s): 58 - 59

      A brief obituary by one of Milner's most eminent colleagues. Plotkin and Milner were together at Edinburgh for over two decades.

    • Robin Milner's Work on Concurrency
      by Abramsky, Samson
      Electronic Notes in Theoretical Computer Science, 2010, Volume 265
      Another obituary, by another eminent computer scientist, focusing on Milner's work on concurrency.

    • Robin Milner 1934--2010: verification, languages, and concurrency
      by Gordon, Andrew; Harper, Robert; Harrison, John; et al
      Proceedings of the 38th annual ACM SIGPLAN-SIGACT symposium on principles of programming languages, 01/2011

  2. From LCF to HOL: A Short History
    by Mike Gordon,
    Plotkin, G. ; Stirling, C. ; Tofte, M.
    Proof, Language, and Interaction:Essays in Honour of Robin Milner
    Page(s): 169 - 185
    Copyright Year: 2000
    Available from
    Mike Gordon co-authored with Milner a book on LCF.

  3. Elements of interaction: Turing award lecture
    by Milner, Robin
    Communications of the ACM, 01/1993

    The page gives the citation and a brief bio.

    The citation reads

    "For three distinct and complete achievements:

    LCF, the mechanization of Scott's Logic of Computable Functions, probably the first theoretically based yet practical tool for machine assisted proof construction;
    ML, the first language to include polymorphic type inference together with a type-safe exception-handling mechanism;
    CCS, a general theory of concurrency.

    In addition, he formulated and strongly advanced full abstraction, the study of the relationship between operational and denotational semantics."

  4. Milner went on to develop the pi-calculus and bigraphs in the years after 1990. The Turing award lecture itself deals mostly with concurrency.

  5. Functions as processes
    by Milner, Robin
    Mathematical structures in computer science
    ISSN: 0960-1295 EISSN: 1469-8072
    YEAR: 1992 VOL: 2 ISSUE: 2 PAGE: 119-
    DOI: 10.1017/S0960129500001407
    Available also from
    Shows that communication is the only primitive needed to set up computation!

  6. A Calculus of Communicating Systems
    by Robin Milner
    Lecture Notes in Computer Science
    Volume 92 1980

    The original typewritten book, available online from the Chalmers library. This material was developed into the book

  7. Communication and Concurrency
    by Robin Milner
    Prentice Hall International Series in Computer Science, Paperback – September 6, 1995
    Available to borrow from the Chalmers library.

  8. If you follow up the links and bibliographies in the above papers and web pages, you should be able to find most of Milner's works. Most of his work post 1990 is relevant to concurrency, and some of it is very informal and easy to read, but we have restricted ourselves to a few works most appropriate to the level of our course. Please let us know of any others that you think should be included here.

Tony Hoare.

C. A. R. Hoare is together with Milner probably the researcher who has been in the field longest and had a comparable impact.


will lead you to many more links. A few of Hoare's most important works:

  1. Monitors: an operating system structuring concept by Tony Hoare

    You can read the CACM 1974 typeset paper via the library.

  2. Communicating Sequential Processes by Tony Hoare Communications of the ACM 1978

    Can be read via the library, or at

  3. Communicating Sequential Processes (book by Tony Hoare)

    is available online at

  4. Algorithm 64: Quicksort

    Comm. ACM 4 (7): 321. (1961)

    It is almost unbelievable what an early work this algorithm was, and how fortunate we are that the inventor is still with us!

  5. An axiomatic basis for computer programming by Hoare, C. A. R.

    Communications of the ACM 12 (10): 576–580. (October 1969).

    What we now call axiomatic semantics (pre- and post-conditions, or a version of contracts), as opposed to operational or denotational semantics.

Edsger Dijkstra

A towering figure, particularly in the early days of concurrent programming, and very insistent on properly defining concepts such as priority that tended to be used informally late into the 1970's. He is associated with the first definition of semaphores, and was also a brilliant programmer who invented the concept of guarded commands, a version of which turns up in Promela.

In addition to the usual wikipedia links

you can read Tony Hoare's obituary here:

  1. Cooperating sequential processes by E. W.Dijkstra

    appeared in Programming Languages edited by F. Genuys, Academic Press. (1968). Available online now at

    Behind the old-fashioned notation lurk surprisingly modern treatments of semaphores and still standard problems.

  2. Guarded commands, non-determinacy and formal derivation of programs

    by E. W.Dijkstra Communications of the ACM 18 (1975), 8: 453–457.

    Available online at

  3. Letters to the editor: go to statement considered harmful by Dijkstra, E. W.
    Communications of the ACM 11 (3): 147–148. (March 1968).
    doi:10.1145/362929.362947. ISSN 0001-0782.

    This famous letter started the movement known as Structured Programming, also the title of a book by O.-J. Dahl, E. W. Dijkstra, C. A. R. Hoare, Academic Press, London, 1972 ISBN 0-12-200550-3 which also includes the beginning of object oriented programming.

    The ideas behind the "goto" problem have been so thoroughly absorbed that even beginning students expect to only need sequencing, conditionals and loops. In 1968, most people were puzzled as to how one could program without arbitrary jumps.

A small selection of classic papers.

  1. E. D. Dijkstra (1968) "Cooperating sequential processes"

  2. Tony Hoare, "Monitors: an operating system structuring concept"

    (you can read the CACM 1974 typeset paper via the library)

  3. Tony Hoare's CSP book is online.

    His paper of the same name, CACM 1978, can be read via the library, or at

  4. Carriero and Gelernter's LINDA paper is available at

For most other references from the textbook, you will have to use the library. As and when we locate other versions online, we will add links here. A major failing of Ben-Ari is that he does not link to Milner's work. Read his papers from the library. E.g., his original CCS (calculus of communicating systems) book.

Several of the references in Ben-Ari's textbook (see the Bibliography at the end) are to books, and these are typically not available online. But the papers are, through the library. Look them up! Bibliographies and lists of references, whether in your textbook or in the papers I hope you will read, are not there to be ignored. The original papers have a freshness that can never be recaptured in a re-telling. Reading the original literature is an essential part of becoming a scientist.

  1. See "Det dunkelt sagda är det dunkelt tänkta" in


  3. There are many reports about the Gaisal train accident, but most deal with politics. The timing issue and the mix-up between the various safety systems is mentioned in

Here are two paragraphs from the report referring to the programming-related errors:

"Chandra thought that it is a matter of 15 minutes and the train will make it to Gaisal much before Brahmputra crosses it and then shift to the up-line. He granted paper-line clear to Awadh-Assam Express but his fatal error was that he failed to inform Gaisal about it. He should have told Gaisal station master to ensure that Awadh-Assam has reached, before giving clearance to Brahmputra Mail, an official, part of CCRS inquiry, said.

What the Kishanganj ASM did not know was that Awadh-Assam driver was waiting at the next station, Panjipara, for 12 minutes awaiting paper-line clear. The driver knew he was on the wrong line and wanted to continue only after receiving clearance from Panjipara, which was given to him, in utter complacency. So he proceeded towards Gaisal, unaware that Gaisal did not know about his arrival. The Gaisal station staff, meanwhile, did not know about the approaching Awadh-Assam and gave clearance to Brahmputra for arrival."

##Poster Exhibition

The teaching team will be glad to organize a student poster exhibition if there is interest. The idea is that you (individually or in teams of any size) prepare a brief presentation on any paper or work you choose, classic or recent, in an area at least distantly related to concurrency. You do not give a lecture to the class; instead, you prepare a few minutes' worth of slides, diagrams, animation or films (any or all of those) and stand next to a handwritten poster announcing your topic. Visitors come to you if they wish, and ask whatever they want. You answer as best you can.

Participation is entirely voluntary and carries no credit towards your grade. You do a poster presentation if you wish, and visit the exhibition if you wish. The purpose is only to give you an occasion to get (back) into the habit of finding out something and telling others about it.

We will decide when and where to hold the exhibition once we know how many students would like to take part, so please express your interest via the Google group. If you wish, we can help you pick a paper.

Concurrent Programming 2016 - Chalmers University of Technology & Gothenburg University