General
News
11.03.2013 — The project description is available. Please see the assignment in the project section.
22.02.2013 — The paper assignment has been completed. Please see the paper you have been assigned to in the seminar schedule.
19.02.2013 — The paper selection page is up. Please follow the instructions on the page to register your preferences by Friday, 22 February 2013, at 12:00.
12.12.2012 — The initial version of this page is up.
Course description
252-0268-00 Concepts of Concurrent Computation
Abstract: Concurrent programming is one of the major challenges in software development. The "Concepts of Concurrent Computation" course explores important models of concurrency, with a special emphasis on concurrent object-oriented programming and process calculi.
Objective: After completing this course, students will understand the principles and techniques of concurrent programming, supporting theories allowing formal reasoning about concurrent systems, and advances in concurrent object-oriented programming.
- Overview
- Concurrent and parallel programming
- Multitasking and multiprocessing
- Shared-memory and distributed-memory multiprocessing
- Notion of process and thread
- Performance of concurrent systems
- Approaches to concurrent programming
- Issues: data races, deadlock, starvation
- Synchronization algorithms
- Semaphores
- Monitors
- Java and .NET multithreading
- Concurrent object-oriented programming: the SCOOP model
- Processors; handling an object
- Synchronous and asynchronous feature calls
- Design by Contract in a concurrent context
- Separate objects and entities
- Accessing separate objects; validity rules
- Synchronization: waiting, reserving, preconditions as wait conditions, Wait by Necessity
- Examples and applications
- Programming approaches to concurrency
- Message-passing vs. shared-memory communication
- Language examples: Ada, Polyphonic C#, Erlang (Actors), X10, Linda, Cilk and others
- Lock-free programming
- Software Transactional Memory
- Reasoning about concurrent programs
- Properties of concurrent programs
- Temporal logic
- Process calculi: CSP, CCS
- Proofs of concurrent programs
Grading: No Testat is delivered for the course. The assessment consists of a project (35%), a seminar talk (15%), and a written semester end exam (50%) for which no supporting material is allowed. The only way to get a grade is to take the written exam, deliver a seminar talk, and submit the project. This applies regardless of your department or status. The performance assessment is only offered at the end after the course unit. Repetition is only possible after re-enrolling.
Lecture layout: The course's lectures are of two different kinds: the Tuesday session (two hours) is a traditional lecture; the Wednesday lecture (one hour) is devoted to seminar talks, given either by well-known international experts in concurrency or by the student participants, based on research papers related to the topics of the course. The research papers to be presented will be assigned at the start of the course. Depending on the number of participants, some of the exercise sessions may also be used for seminar presentations.
Helping and getting help
Talk to the assistants or use the VIS forum.
Tools
For the development of SCOOP programs, we ask you to use version 7.1 of EiffelStudio. Once you installed EiffelStudio, follow the SCOOP practical matters guide to start a new project. To find example SCOOP programs, open the directory where you installed EiffelStudio and look for the folder examples/scoop. For the development of Java programs, you can use a Java development environment of your choice. For example, you can use Eclipse.
Textbooks
- Bertrand Meyer, Sebastian Nanz. Course textbook (draft) Electronic version
- Maurice Herlihy and Nir Shavit. The Art of Multiprocessor Programming. Morgan Kaufmann, 2008, ISBN 978-0123705914.
- Gregory R. Andrews. Foundations of Multithreaded, Parallel, and Distributed Programming. Addison Wesley, 1999, ISBN 978-0201357523.
- Mordechai Ben-Ari. Principles of Concurrent and Distributed Programming. Prentice Hall, 2006, ISBN 978-0321312839.
Further reading
- Piotr Nienaltowski. Practical framework for contract-based concurrent object-oriented programming. PhD Dissertation, ETH Zurich, 2007. [paper pdf]
- Bertrand Meyer. Object-Oriented Software Construction, Second Edition, Chapter 30, Prentice Hall, 1997, ISBN 0-13-629155-4. [chapter 30 html]
- Howard Bowman and John Derrick (Editors). Formal methods for distributed processing: a survey of object-oriented approaches. Cambridge University Press, 2001.
- Bertrand Meyer. Eiffel: The Essentials. [paper pdf]
- Marcel Kessler. DO IT WITH STYLE - A Guide to the Eiffel Style. [paper pdf]
- EiffelSoftware. Eiffel and EiffelStudio Documentation. [website html]
- EiffelSoftware. Concurrent Eiffel with SCOOP. [website html]
- Allen B. Downey. The Little Book of Semaphores Second Edition. Green Tea Press, 2005. [paper pdf]
Lecture and Seminar
Schedule
| Day | Time | Location |
|---|---|---|
| Tuesday (Lecture) | 10:15-12:00 | RZ F 21 |
| Wednesday (Seminar) | 15:15-17:00 | RZ F 21 |
Lecture
| Date | Lecture | Title | Slides | Readings | |
|---|---|---|---|---|---|
| Tuesday 19.2.2013 | 1 | Welcome and introduction |
pdf
|
||
| Tuesday 26.2.2013 | 2 | Challenges of concurrency |
pdf
|
Chapter 2 | |
| Tuesday 5.3.2013 | 3 | Synchronization algorithms |
pdf
|
Chapter 3 | |
| Tuesday 12.3.2013 | 4 | Semaphores |
pdf
|
Chapter 4 | |
| Tuesday 19.3.2013 | 5 | SCOOP principles |
pdf
|
Chapter 9 | |
| Tuesday 26.3.2013 | 6 | SCOOP type system |
pdf
|
Chapter 9 | |
| Tuesday 2.4.2013 | no lecture | Easter break | |||
| Tuesday 9.4.2013 | 7 | Monitors |
pdf
|
Chapter 5 | |
| Tuesday 16.4.2013 | 8 | CCS |
pdf
|
Chapter 7 | |
| Tuesday 23.4.2013 | 9 | CCS advanced concepts |
pdf
|
Chapter 7 | |
| Tuesday 30.4.2013 | 10 | CSP |
pdf
|
Chapter 6 | |
| Tuesday 7.5.2013 | 11 | SCOOP outlook | |||
| Tuesday 14.5.2013 | 12 | Lock-free approaches |
pdf
|
||
| Tuesday 21.5.2013 | 13 | Languages for concurrency and parallelism |
pdf
|
||
| Tuesday 28.5.2013 | Exam |
= Temporary version
= Final version
Seminar
| Date | Presenter(s) | Title |
|---|---|---|
| Wednesday 20.2.2013 | Bertrand Meyer | How to give a technical presentation [slides] |
| Wednesday 20.3.2013 | Emanuele Rudel | Paper 24 [Zhang et al., ISSTA'12] [slides] |
| Benjamin Bucheli | Paper 21 [Hong et al., ISSTA'12] [slides] | |
| Wednesday 27.3.2013 | Ahmad Salim Al-Sibahi | Paper 11 [Bocq and Daenen, OOPSLA'12] [slides] |
| Christian Klauser | Paper 46 [Kasikci et al., ASPLOS'12] [slides] | |
| Wednesday 10.4.2013 | Eiríkur Fannar Torfason | Paper 33 [Pradel and Gross, PLDI'12] [slides] |
| Hartmut Keil | Paper 39 [Lochbihler, ESOP'12] [slides] | |
| Wednesday 17.4.2013 | Dominic Meier | Paper 34 [Burckhardt, ESOP'12] [slides] |
| Karolos Antoniadis | Paper 47 [Volos et al., ASPLOS'12] [slides] | |
| Wednesday 24.4.2013 | Roman Schmocker | Paper 9 [Kumar et al., OOPSLA'12] [slides] |
| Paolo Antonucci | Paper 7 [Okur et al., FSE'12] [slides] | |
| Wednesday 8.5.2013 | Moritz Hoffmann | Paper 10 [Sartor and Eeckhout, OOPSLA'12] [slides] |
Exercises
Schedule
| Day | Time | Location |
|---|---|---|
| Wednesday (Exercise) | 14:15-15:00 | RZ F 21 |
Assignments
| Date | Title | Material |
|---|---|---|
| Wednesday 20.2.2013 | (no exercise class) | (use the time for paper selection) |
| Wednesday 27.2.2013 | Introduction and challenges of concurrency | assignment solution Haiku |
| Wednesday 6.3.2013 | Synchronization algorithms | assignment solution TBME |
| Wednesday 13.3.2013 | Semaphores | assignment solution unisex bathroom precedence graph |
| Wednesday 20.3.2013 | SCOOP principles | assignment solution |
| Wednesday 27.3.2013 | SCOOP type system | assignment solution |
| Wednesday 10.4.2013 | Monitors | assignment solution unisex bathroom |
| Wednesday 17.4.2013 | CCS | assignment solution |
| Wednesday 24.4.2013 | CCS advanced concepts | assignment solution |
| Wednesday 8.5.2013 | CSP | assignment solution |
| Wednesday 15.5.2013 | Lock-free approaches | assignment solution |
| Wednesday 22.5.2013 | Languages for concurrency and parallelism | assignment |
Assistants
Project
Please read the project assignment. The starting point for the visualization is available here.