General
News
22.02.2015 — The paper assignment has been completed. Please see the paper assigned to you in the seminar schedule.
18.02.2015 — The project assignment has been posted.
26.11.2014 — the initial version of the course webpage is live. Curious about the project planned for this year? This video might give you a hint!
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: CCS and coalgebra
- 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 Chandrakana Nandi.
Tools
For the development of SCOOP programs, we will provide a virtual machine (the link will be 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
- Dr. Sebastian Nanz (SN)
- Dr. Chris Poskitt (CP)
Lecture
| Date | Lecture | Title (Lecturer) | Slides | Readings |
|---|---|---|---|---|
| Tuesday 17.02.2015 | 1 | Welcome and introduction (SN) |
pdf
|
|
| Tuesday 24.02.2015 | 2 | Challenges of concurrency (SN) |
pdf
|
Chapter 2 |
| Tuesday 03.03.2015 | 3 | Synchronisation algorithms (CP) |
pdf
|
Chapter 3 |
| Tuesday 10.03.2015 | 4 | Semaphores (CP) |
pdf
|
Chapter 4 |
| Tuesday 17.03.2015 | 5 | Monitors (SN) |
pdf
|
Chapter 5 |
| Tuesday 24.03.2015 | 6 | SCOOP (SN) |
pdf
|
Chapter 9 |
| Tuesday 31.03.2015 | 7 | Lock-free approaches (CP) |
pdf
|
Herlihy & Shavit (§10.5-6, 11.1-2, 18) |
| Tuesday 07.04.2015 | no lecture | Easter break | — | |
| Tuesday 14.04.2015 | 8 | Correctness conditions (CP) |
pdf
|
Herlihy & Shavit (Chapter 3) |
| Tuesday 21.04.2015 | 9 | Petri nets (CP) |
pdf
|
Reisig, 2013 (Chapters 1-3) Esparza & Heljanko, 2008 (Chapters 1-3) Furia et al., 2012 (Chapter 8) |
| Tuesday 28.04.2015 | 10 | CCS (SN) |
pdf
|
Chapter 7 |
| Tuesday 05.05.2015 | 11 | Bisimulations (SN) |
pdf
|
Chapter 7 |
| Tuesday 12.05.2015 | 12 | Coalgebra (G. Caltais) |
pdf
|
Jacobs & Rutten, 1997 (tutorial) Silva et al., 2010 (paper) Jacobs, 2012 (book) |
| Tuesday 19.05.2015 | 13 | Languages for concurrency and parallelism (SN) |
pdf
|
|
| Tuesday 26.05.2015 | Exam | — |
= Temporary version
= Final version
Seminar
Exercises
Schedule
| Day | Time | Location |
|---|---|---|
| Wednesday (Exercise) | 14:15-15:00 | RZ F 21 |
Assignments
| Date | Title | Material |
|---|---|---|
| Wednesday 18.02.2015 | Warm up assignment | exercise solution Haiku |
| Wednesday 25.02.2015 | Challenges of concurrency | exercise promela code solution promela solution |
| Wednesday 04.03.2015 | Synchronization algorithms | exercise promela code solution code solutions |
| Wednesday 11.03.2015 | Semaphores | exercise solution code |
| Wednesday 18.03.2015 | Monitors | exercise solution |
| Wednesday 25.03.2015 | SCOOP | exercise solution |
| Wednesday 01.04.2015 | Lock-free approaches | exercise solution |
| Wednesday 15.04.2015 | Correctness conditions | exercise solution |
| Wednesday 22.04.2015 | Petri nets | exercise solution |
| Wednesday 29.04.2015 | CCS | exercise solution |
| Wednesday 06.05.2015 | Project Tournament | |
| Wednesday 13.05.2015 | Bisimulations and Coalgebra | exercise solution |
| Wednesday 20.05.2015 | Questions, answers, and problem discussion session |