Replication and Consistency
Instructor: Dr. Annette Bieniusa
Lecture: Wednesday, 10:00 - 11:30, Room 13-222(!)
Exercises: Exercises are every two weeks at the following times:
- Monday 10:00 (Room 34-420 - limited space for 15 people!)
- Tuesday 08:15 (Room 48-453)
|Jan 2020||Obligatory Exercise|
The lecture and course material will be in English.
- Good programming knowledge in Java or C/C++
As this is a 4-CP lecture, you will spend on average around 120 hours on the lecture and the exercises, including exam preparation. If you do not have much experience with programming systems of medium size and moderate complexity, you need to plan to spend more time on the practical exercises. If you lack some of the theoretical prerequisites (definition of formal languages, finite-state machines, proof techniques), you should also include revisions for these topics into your planning.
- Oral exams (Week of February 10, 2020)
You will be able to
- understand and explain the underlying mechanisms of classical concurrent and replicated data structures,
- explain and elaborate the limitations of non-blocking synchronization mechanisms, and
- formally describe and compare standard memory and consistency models for concurrent systems.
Topics of the Lecture
- Basic notions
- Happens-Before relation
- Histories and abstract executions
- Sequential consistency and linearizability
- Non-blocking synchronisation in shared-memory architectures
- Primitive synchronization operations
- ABA problem
- Concurrent lists, queues and stacks
- Memory models
- Total-Store-Order (TSO)
- Axiomatic formal models
- Data Race freedom
Week Date Slides Comments 1 06.11. 01 Introduction Check p.20 for link to exercise poll! 2 13.11. 02 Mutual Exclusion 3 20.11. 03 Concurrent Objects 4 27.11. 04 Foundations of Shared Memory 5 04.12. continued 6 11.12. 05 Weak Memory Models, Part I (Guest lecture) The slides contain the material of both lectures 7 18.12. 05 Weak Memory Models, Part II (Guest lecture) 8 08.01. 06 Consensus 9 15.01. 07 Universality of Consensus 10 22.01. 11 29.01. 12 05.02. 13 12.02.