**25.06.2018**: Registration for the final exam is now available. If you want to participate in the final exam, please sign up until 16. July 2018 in the KVV.**04.06.2018**: The eighth problem set is available.**28.05.2018**: The seventh problem set is available.**21.05.2018**: The sixth problem set is available.**14.05.2018**: The fifth problem set is available.**07.05.2018**: The fourth problem set is available.**30.04.2018**: The third problem set is available.**26.04.2018**: The exam will take place on**Wednesday, 18. July 2018, 16:00–18:00**in großer HS Informatik, Takustr. 9, and HS 1a and 1b, Habelschwerdter Allee 45.**23.04.2018**: The second problem set is available.**11.04.2018**: The first problem set is available.**01.04.2018**: The website is online.

**The problem sets will only be published online**,
on this website.

- Foundations:
- Machine model: atomic instructions, arbitrary interleaving, scheduler
- State diagrams
- Saftey and liveness
- Weak fairness

- Critical sections:
- Goals: mutual exclusion, freedom from deadlock, freedom from starvation
- Dekker's algorithm and Peterson's algorithm
- critical sections using special instructions
- advanced algorithms: bakery algorithm, etc.

- Formal verification of concurrent programs
- proving invariants
- linear temporal logic

- Concurrent Programming in Java
- Higher level synchronization: Processes and States
- Semaphores:
- Basic definition and variants
- Applications: critical sections, producer-consumer, dining philosophers
- Reductions: Barz's algorithm, Udding's algorithm

- Monitors:
- Basic definition and variants
- Condition variables
- Applications: implementing semaphores with monitors, producer-consumer with monitors, the reader-writer problem

**Monday, 16.04.2018 (K. Wolter)**- Administrativa
- Introduction: motivation and goals of concurrent and distributed programming

**Wednesday, 18.04.2018 (K. Wolter)**- Machine model: atomicity, interleaving, scheduling, scenario
- state diagrams

**Monday, 23.04.2018 (W. Mulzer)**- Safety and liveness
- Weak fairness
- Concurrency issues
- Critical sections

**Wednesday, 25.04.2018 (W. Mulzer)**- Critical section problem: abstract definition and assumptions
- First attempt:
- processes take turns using a global variable
- Analysis using a state diagram
- issue: one process can starve while waiting for the other process to take its turn

- Second attempt:
- processes use global flags that indicate whether they are inside their critical sections
- issue: mutual exclusion is not guaranteed

**Monday, 30.04.2018 (W. Mulzer)**- Dekker's algorithm for the critical section problem
- Critical sections using dedicated instructions

**Wednesday, 02.05.2018 (W. Mulzer)**- Formal verification of concurrent programs with propositional logic: proving safety properties through induction.
- linear temporal logic: motivation and syntax

**Monday, 07.05.2018 (W. Mulzer)**- linear temporal logic: semantics and some properties
- formal verification of Dekker's algorithm
- more algorithms for critical sections

**Wednesday, 09.05.2018 (W. Mulzer)**- formal verification of Dekker's algorithm (continued)
- more algorithms for critical sections
- Concurrent Programming and Critical Sections in Java (example)

**Monday, 14.05.2018 (W. Mulzer)**- Higher level synchronization: scheduling and process states
- Semaphores: motivation and definition
- Critical sections with Semaphores

**Wednesday, 16.05.2018 (W. Mulzer)**- Critical sections with semaphores: correctness
- Semaphore variants
- The semaphore invariant and its use in correctness proofs

**Monday, 21.05.2018**- No class (Pentecost)

**Wednesday, 23.05.2018 (W. Mulzer)**- The producer-consumer problem: semaphore solution with correctness proof
- Simulating a weak semaphore with a binary semaphore: Barz's algorithm

**Monday, 28.05.2018 (W. Mulzer)**- Monitors: basic definition and variants
- Implementing semaphores with montiors

**Wednesday, 30.05.2018 (K. Wolter)**- Monitors: producer-consumer example
- reader-writer example with monitors

**Monday, 04.06.2018 (K. Wolter)**- safety of reader-writer with monitors

**Wednesday, 06.06.2018 (K. Wolter)**- Monitor starvation-free for readers
- Distributed systems: communication

**Monday, 11.06.2018 (K. Wolter)**- Parallel computing with channels
- Multiplication of two matrices

**Wednesday, 13.06.2018 (K. Wolter)**- Communication: Rendezvous and RPC

**Monday, 18.06.2018 (K. Wolter)**- Distributed Mutual Exclusion, Ricart-Agrawala algorithm

**Wednesday, 20.06.2018 (W. Mulzer)**- Consensus in Distributed Systems
- The Byzantine Generals Problem

**Monday, 25.06.2018 (W. Mulzer)**- The Byzantine Generals Algorithm
- Correctness Proof
- Notes

**Monday, 02.07.2018 (W. Mulzer)**- The flooding algorithm for crash failures
- The Phase-King Algorithm for fewer traitors

**Wednesday, 04.07.2018 (K. Wolter)**- Global properties: Distributed Termination detection

**Monday, 09.07.2018 (K. Wolter)**- Distributed Termination detection
- Dijkstra-Scholten algorithm

**Wednesday, 11.07.2018 (K. Wolter)**- Global properties: Snapshot

**Monday, 16.07.2018 (K. Wolter)**

- Basic knowledge in discrete Mathematics and Logic
- Programming in Haskell, Python and Java

*Mordechai Ben-Ari: Principles of Concurrent and Distributed Programming.*Second Edition, Addison-Wesley, 2006.*Maarten van Steen, Andrew S. Tanenbaum: Distributed Systems.*3rd Edition, 2017.*George Coulouris, Jean Dollimore, Tim Kindberg, Gordon Blair: Distributed Systems. Concepts and Design.*Fifth Edition. Pearson, 2011.

There will be an exam at the end of the semester and a make-up exam at the beginning of the next semester. If you are taking the class for the first time, you can use the grade of the second exam to improve your grade from the first exam (Freiversuchsregel).

The exam will take place on **Wednesday, 18. July 2018,
16:00–18:00** in großer HS Informatik, Takustr. 9, and
HS 1a and 1b, Habelschwerdter Allee 45.
The second exam will take place on **Wednesday, 10. October 2018,
10:00–12:00** in großer HS Informatik, SR 049 and
SR 005, Takustr. 9.

To pass the class, you must

- participate regularly in the exercise sessions (at least 80% of all meetings);
- earn at least 60% of the credits on the exercises, where you need at least 20% on at least n-2 problem sets;
- present your solutions for at least two problems in the exercise session; and
- earn at least 50% of the credits in the final exam.

The successful participation in the exercises sessions and in the final exam are independent. The class is graded. The grade depends exclusively on your performance in the final exam.

Monday | ||
---|---|---|

16:00–18:00 | Takustr. 9, SR 046 | Alexander Rademann |

Tuesday | ||

12:00–14:00 | Takustr. 9, SR 049 | Alexander Rademann |

16:00–18:00 | Takustr. 9, SR 046 | Justus Pfannschmidt |

Thursday | ||

08:00–10:00 | Arnimallee 7, SR 031 | Johannes Nixdorf |

10:00–12:00 | Takustr. 9, SR 049 | Johannes Nixdorf |

16:00–18:00 | Takustr. 9, SR 049 | Justus Pfannschmidt |

Instructors' office hours: Tuesday 14:00–15:00 in room 112 (W. Mulzer) and by appointment in room 149 (K. Wolter).

The problem sets will appear each week on this site. The period for the problem sets is from Monday until Friday 11 days later. You need to put your solution into the mailbox of your teaching assistant by Friday, 12:00. You must work in groups of two.

**If you turn in your problem set late, you will not receive any
credit.
**

No. | Out | Due | tex | Remarks | |
---|---|---|---|---|---|

1 | 11.04.2018 | 27.04.2018 | Hint | ||

2 | 23.04.2018 | 04.05.2018 | |||

3 | 30.04.2018 | 11.05.2018 | |||

4 | 07.05.2018 | 18.05.2018 | |||

5 | 14.05.2018 | 25.05.2018 | |||

6 | 21.05.2018 | 01.06.2018 | |||

7 | 28.05.2018 | 08.06.2018 |
Framewok Java FX Hinweise 1 Hinweise 2 |