General
News
04.03.2014 — The project assignment has been updated with some hints and known issues of EiffelStudio.
25.02.2014 — The project assignment has been posted.
21.02.2014 — The paper assignment has been completed. Please see the paper you have been assigned to in the seminar schedule.
18.02.2014 — The paper selection page is up. Please follow the instructions on the page to register your preferences by Friday, 21 February 2014, at 12:00.
02.12.2013 — The initial version of this page is up. Please note that the schedule and other details remain, for the moment, provisional and subject to change.
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
- Petri nets
- 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 is a traditional lecture; the Wednesday session is devoted to seminar talks 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.
Helping and getting help
The course has a mailing list with all the registered students and assistants: se-ccc@lists.inf.ethz.ch. If your e-mail address is missing, ask the assistants. In addition to the mailing list, we offer office hours on Friday from 14:00 to 16:00 in RZ J6. Please send a message at least 15 minutes in advance to either Mischael Schill or Georgiana Caltais.
Tools
For the development of SCOOP programs, we provide a virtual machine, the link is provided within the project description. For the development of Java programs, you can use a Java development environment of your choice. For example, you can use NetBeans or 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 |
Lecturers
- Prof. Dr. Bertrand Meyer (BM)
- Dr. Sebastian Nanz (SN)
- Dr. Chris Poskitt (CP)
Lecture
| Date | Lecture | Title (Lecturer) | Slides | Readings |
|---|---|---|---|---|
| Tuesday 18.2.2014 | 1 | Welcome and introduction (BM) |
pdf
|
|
| Tuesday 25.2.2014 | 2 | Challenges of concurrency (SN) |
pdf
|
Chapter 2 |
| Tuesday 4.3.2014 | 3 | Synchronization algorithms (SN) |
pdf
|
Chapter 3 |
| Tuesday 11.3.2014 | 4 | Semaphores (CP) |
pdf
|
Chapter 4 |
| Tuesday 18.3.2014 | 5 | Monitors (CP) |
pdf
|
Chapter 5 |
| Tuesday 25.3.2014 | 6 | SCOOP principles (BM) |
pdf
|
Chapter 9 |
| Tuesday 1.4.2014 | 7 | SCOOP type system (BM) |
pdf
|
Chapter 9 |
| Tuesday 8.4.2014 | 8 | Lock-free approaches (CP) |
pdf
|
Herlihy & Shavit, 2008 (especially Chapters 3 and 18) |
| Tuesday 15.4.2014 | 9 | Languages for concurrency and parallelism (SN) |
pdf |
|
| Tuesday 22.4.2014 | no lecture | Easter break | ||
| Tuesday 29.4.2014 | 10 | CSP (BM) |
pdf
|
Chapter 6 |
| Tuesday 6.5.2014 | 11 | Petri nets (CP) |
pdf
|
Reisig, 2013 (Chapters 1-3) Esparza & Heljanko, 2008 (Chapters 1-3) Furia et al., 2012 (Chapter 8) |
| Tuesday 13.5.2014 | 12 | CCS (SN) |
pdf
|
Chapter 7 |
| Tuesday 20.5.2014 | 13 | CCS advanced concepts (SN) |
pdf
|
Chapter 7 |
| Tuesday 27.5.2014 | Exam |
= Temporary version
= Final version
Seminar
| Date | Presenter(s) | Title |
|---|---|---|
| Wednesday 19.2.2014 | Bertrand Meyer | How to give a technical presentation [slides] |
| Friday 7.3.2014 (*) | Concurrency Symposium (international speakers) |
Programme |
| Wednesday 12.3.2014 | Erik Henriksson | Paper 2 [Pradel and Gross, ICSE'13] [slides] |
| Claudio Corrodi | Paper 4 [Liu et al., ESEC/FSE'13] [slides] | |
| Wednesday 19.3.2014 | Susanne Graf | Verification of distributed systems and use of knowledge for implementing them [abstract] |
| Wednesday 26.3.2014 | Jeremy Bradford | Paper 34 [Kasikci et al., SOSP'13] [slides] |
| Jesse Badash | Paper 8 [Clebsch and Drossopoulou, OOPSLA'13] [slides] | |
| Wednesday 2.4.2014 | Nadja Müller | Paper 27 [Golan-Gueta et al., PLDI'13] [slides] |
| Patrick Lüthi | Paper 30 [Lu et al., ESOP'13] [slides] | |
| Wednesday 9.4.2014 | Teruki Tauchi | Paper 1 [Marino et al., ICSE'13] [slides] |
| Andreas Dillier | Paper 36 [Zhang et al., ASPLOS'13] [slides] | |
| Wednesday 16.4.2014 | Jost Joller | Paper 38 [Heumann et al., PPoPP'13] [slides] |
| Wednesday 30.4.2014 | Jingjing Du | Paper 40 [Marques et al., Euro-Par'13] [slides] |
| Wednesday 7.5.2014 | Stefan Zurfluh | Paper 12 [Herhut et al., OOPSLA'13] [slides] |
| Maciej Besta | Besta & Hoefler: Fault Tolerance for Remote Memory Access Programming Models. In Proc. HPDC'14. ACM, 2014. [slides] |
(*) The symposium on Friday 7.3.2014 will consist of several research talks from international experts on concurrency. While the symposium is not a mandatory part of the course, it will be very beneficial to attend, and we warmly invite you to do so.
Exercises
Schedule
| Day | Time | Location |
|---|---|---|
| Wednesday (Exercise) | 14:15-15:00 | RZ F 21 |
Assignments
| Date | Title | Material |
|---|---|---|
| Wednesday 19.2.2014 | (no exercise class) | (use the time for paper selection) |
| Wednesday 26.2.2014 | Introduction and challenges of concurrency | assignment solution Haiku |
| Wednesday 5.3.2014 | Synchronization algorithms | assignment solution TBMU |
| Wednesday 12.3.2014 | Semaphores | assignment solution code sources |
| Wednesday 19.3.2014 | Monitors | assignment solution code sources |
| Wednesday 26.3.2014 | SCOOP principles | assignment solution |
| Wednesday 2.4.2014 | SCOOP type system | assignment solution |
| Wednesday 9.4.2014 | Lock-free approaches | assignment solution |
| Wednesday 16.4.2014 | Languages for concurrency and parallelism | assignment code sources |
| Wednesday 30.4.2014 | CSP | assignment solution |
| Wednesday 7.5.2014 | Petri nets | assignment solution |
| Wednesday 14.5.2014 | CCS | assignment solution |
| Wednesday 21.5.2014 | CCS advanced concepts | assignment solution |
Assistants
Project
Please read the project assignment. Make sure that you are subscribed to the mailing list se-ccc@lists.inf.ethz.ch. Send an message to the list if you want to be added.