Replication and Consistency


Instructor: Dr. Annette Bieniusa

Lecture: Wednesday, 10:00 - 11:30, Room 48-379

Exercises: tba

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 (date tba)
  • Please register with our secretary Judith Stengel for a time slot (and ofc with the examination office)!


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
    • Compositionality
  • 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
    • Robustness
    Week Date Topic
    1 06.11. Introduction
    2 13.11.
    3 20.11.
    4 27.11.
    5 04.12.
    6 11.12.
    7 18.12.
    8 09.01.
    9 15.01.
    10 22.01.
    11 29.01.
    12 05.02.
    13 12.02.


Details on Exercises will be announced in the first lecture on 06 November.