General
News
13.03.2012 — The project description is available. Please see the assignment in the project section.
24.02.2012 — The paper assignment has been completed. Please see the paper you have been assigned to in the seminar schedule.
21.02.2012 — The paper selection page is up. Please follow the instructions on the page to register your preferences by Friday, 24 February 2012, at 16:00.
29.11.2011 — 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. The seminar talks will be given about half of the time by well-known international experts in concurrency; the rest of the time they will be given 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 the most recent version 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-16:00 | RZ F 21 |
Lecture
| Date | Lecture | Title | Slides | Readings |
|---|---|---|---|---|
| Tuesday 21.2.2012 | 1 | Welcome and introduction |
pdf
|
|
| Tuesday 28.2.2012 | 2 | Challenges of concurrency |
pdf
|
Chapter 2 |
| Tuesday 6.3.2012 | 3 | Synchronization algorithms |
pdf
|
Chapter 3 |
| Tuesday 13.3.2012 | 4 | Semaphores |
pdf
|
Chapter 4 |
| Tuesday 20.3.2012 | 5 | Monitors |
pdf
|
Chapter 5 |
| Tuesday 27.3.2012 | 6 | SCOOP principles |
pdf
|
Chapter 9 |
| Tuesday 3.4.2012 | 7 | SCOOP type system |
pdf
|
Chapter 9 |
| Tuesday 10.4.2012 | no lecture | Easter break | ||
| Tuesday 17.4.2012 | 8 | Lock-free approaches |
pdf
|
|
| Tuesday 24.4.2012 | 9 | CSP |
pdf
|
Chapter 6 |
| Tuesday 8.5.2012 | 10 | (Seminar talk by Bill Roscoe) | ||
| Tuesday 15.5.2012 | 11 | CCS |
pdf
|
Chapter 7 |
| Tuesday 22.5.2012 | 12 | CCS advanced concepts |
pdf
|
Chapter 7 |
| Tuesday 29.5.2012 | Exam |
= Temporary version
= Final version
Seminar
| Date | Presenter(s) | Title |
|---|---|---|
| Wednesday 22.2.2012 | no seminar | (use the time for paper selection) |
| Wednesday 29.2.2012 | Hassan Gomaa | Modeling Behavioral Design Patterns of Concurrent Objects (paper) |
| Wednesday 7.3.2012 | Bertrand Meyer | How to give a technical presentation |
| Wednesday 14.3.2012 | Student: Nikolaos Kyrtatas | Paper 1 [Savage et al. 1997] (Tutor: Stephan van Staden) [Slides] |
| Student: Chris Dentel | Paper 3 [Boyapati and Rinard 2001] (Tutor: Scott West) [Slides] | |
| Wednesday 21.3.2012 | Student: Marko Peric | Paper 4 [Sen 2007] (Tutor: Scott West) [Slides] |
| Student: Mathias Dürrenberger | Paper 5 [Musuvathi 2008] (Tutor: Carlo A. Furia) [Slides] | |
| Student: Daniel Schweizer | Paper 13 [Lei and Carver 2004] (Tutor: Martin Nordio) [Slides] | |
| Wednesday 28.3.2012 | Eric Jul | Concurrency and Distribution in the Emerald Object-Oriented Language [Emerald semaphore program] |
| Student: Ivo Steinmann | Paper 7 [Berger et al. 2009] (Tutor: Nadia Polikarpova) [Slides] | |
| Wednesday 4.4.2012 | Student: Martin Lanter | Paper 6 [Wang et al. 2008] (Tutor: Christian Estler) [Slides] |
| Student: Zhuoya Xiang | Paper 11 [Jayanti 2003] (Tutor: Benjamin Morandi) [Slides] | |
| Student: David Itten | Paper 12 [Martinez and Torrellas 2002] (Tutor: Stephan van Staden) [Slides] | |
| Wednesday 18.4.2012 | Student: Claudio Gargiulo | Paper 8 [Baumann et al. 2009] (Tutor: Martin Nordio) [Slides] |
| Student: Zsolt Istvan | Paper 9 [Schäfer et al. 2010] (Tutor: Christian Estler) [Slides] | |
| Wednesday 25.4.2012 | Student: Benjamin Hess | Paper 17 [Blumofe et al. 1995] (Tutor: Benjamin Morandi) [Slides] |
| Student: Nicola Vermes | Paper 24 [Boehm 2008] (Tutor: Scott West) [Slides] | |
| Wednesday 2.5.2012 | Student: Fabian Gremper | Paper 22 [Ranger et al. 2007] (Tutor: Carlo A. Furia) [Slides] |
| Student: Yves Bonjour | Paper 25 [Burckhardt et al. 2010] (Tutor: Martin Nordio) [Slides] | |
| Student: Stephan Semmler | Paper 26 [Schäfer and Poetzsch-Heffter 2010] (Tutor: Christian Estler) | |
| Tuesday 8.5.2012, 10:15 | Bill Roscoe | Model-checking Timed CSP |
| Wednesday 9.5.2012 | Student: Erik Jonsson | Paper 15 [Aldrich et al. 2003] (Tutor: Nadia Polikarpova) [Slides] |
| Student: Karolina Alexiou | Paper 16 [Laxmikant and Krishnan 1993] (Tutor: Martin Nordio) [Slides] | |
| Wednesday 16.5.2012 | Student: Martin Enev | Paper 27 [Herlihy 1991] (Tutor: Carlo A. Furia) [Slides] |
| Student: Giulio Valente | Paper 28 [Herlihy and Moss 1993] (Tutor: Stephan van Staden) [Slides] | |
| Student: Tim Grabowski | Paper 33 [Welch and Martin 2000] (Tutor: Stephan van Staden) [Slides] | |
| Wednesday 23.5.2012 | Mordechai (Moti) Ben-Ari | Teaching Concurrency and Nondeterminism with Spin [Promela examples] |
Exercises
Schedule
| Day | Time | Location |
|---|---|---|
| Wednesday (Exercise) | 14:15-15:00 | RZ F 21 |
| Wednesday (Exercise or Seminar) | 16:15-17:00 | RZ F 21 |
Assignments
| Date | Title | Material |
|---|---|---|
| Wednesday 22.2.2012 | no exercise | (use the time for paper selection) |
| Wednesday 29.2.2012 | Introduction and challenges of concurrency | assignment |
| Wednesday 7.3.2012 | Synchronization algorithms | assignment |
| Wednesday 14.3.2012 | Semaphores | assignment |
| Wednesday 21.3.2012 | Monitors | assignment |
| Wednesday 28.3.2012 | SCOOP principles | assignment |
| Wednesday 4.4.2012 | SCOOP type system | assignment |
| Wednesday 18.4.2012 | Lock-free approaches | assignment |
| Wednesday 25.4.2012 | CSP | assignment |
| Wednesday 9.5.2012 | Review of concurrent languages | slides |
| Wednesday 23.5.2012 | CCS | assignment |
| Wednesday 17.5.2012 | CCS advanced concepts | assignment |
Assistants
Project
Please read the project assignment.