- 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
- 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)
Recommended Prerequisites
- Basic knowledge in discrete Mathematics and Logic
- Programming in Haskell, Python and Java
Literature
- 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.
The lecture takes place Monday 14:00–16:00,
and Wednesday 16:00–18:00 in the large auditorium, Takustraße 9.
The exercise sessions will be conducted by three teaching
assistants (Johannes Nixdorf, Justus Pfannschmidt, and Alexander
Rademann).
|
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 |
pdf | 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
|