Programming Distributed Systems

Organization

Instructor: Dr. Annette Bieniusa

Lecture: Monday, 10:00 - 11:30, Room 48-453

Exercises: Thursday, 15:30 - 17:00, Room 42-110 (first session on April 12th)

The lecture and course material will be in English.

Registration:

Please register via mail to Peter Zeller (subject: “Registration Progdist”).

Prerequisites:

  • Good programming knowledge, including usage of code repositories (git)

As this is a 4CP lecture, you will spend on average around 120 hours on the lecture and the exercises, plus exam preparation. If you do not have much experience with programming systems of medium size, 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), you should also incorporate this into your planning.

Exam:

  • Oral exams on August 07, August 16/17, September 21
  • Please register with our secretary Judith Stengel for a time slot (and ofc with the examination office)!

Objectives

You will be able to

  • explain the challenges regarding time and faults in a distributed system
  • provide formal definitions for time models, fault models and consistency models
  • comprehend and develop models of some distributed system in a process calculus
  • describe the algorithms for essential abstractions in programming distributed systems
  • implement basic abstractions for distributed programming
  • explain the virtues and limitations of major distributed programming paradigms

Topics of the Lecture

  • Basic primitives in programming distributed systems
    • Broadcast
    • Consistent snapshots
    • Consensus
    • Distributed state machine replication
    • Quorums
  • Theoretical foundation
    • Failure modes
    • Time in Distributed systems
    • Process calculi (e.g. CSP, CCS, pi calculus, TLA)
    • Consistency models
  • Programming paradigms for Distributed Systems
    • RPC
    • Futures and promises
    • Message passing and Actors
    • CRDTs
    • Streaming / Data-Flow

Exercises

To solve the practical exercises, you need to install some software: Required software for the exercises

Please submit your solution to the practical exercises via your Git repository (which you get after registration). If you want feedback on the theoretical exercises, please send your solution to Peter Zeller.

Solving the exercise sheets is not mandatory, but highly recommended. In the second half of the semester, you will have to implement a bigger project in Erlang. Successfully implementing this project is a requirement for being admitted to the exams.

Sheet Material
Exercise 1 (Hints) ex1_tests.erl
Exercise 2 (Hints) template (Update 24.04.: Added tests for vector clocks)
Exercise 3 (Hints) template (Update 04.05.: Changes and instructions for Running on Windows; Update 09.05.: Added some test cases)
Exercise 4 (Hints)
Final Project template
Exercise 5 (Hints) See also: Principles of Eventual Consistency page 53
Date Topic
12.04. Introduction to Erlang (Slides)
19.04. Discussing sheet 1, introduction to concurrency in Erlang (Slides)
26.04. Discussing sheet 2 (part 1) (code is available in Gitlab)
03.05. Discussing sheet 2 (part 2), Introduction to sheet 3 and replicated state machines
10.05. (No exercise)
17.05. Discussing sheet 3
24.05. Discussing sheet 4, Introduction to next practical part
31.05. (No exercise)
07.06. Introduction to Final exercise, CRDT library
14.06. In-class exercises on consistency and CRDTs, support with practical exercises
21.06. Support with practical exercises and other questions (no new exercise sheet will be discussed)
28.06. Guest lecture: Thomas Fuhrmann, Head of Technology, AWS Professional Services EMEA

Time Table

Week Date Topic
1 09.04. Introduction
2 16.04. Message Broadcast (updated 07.07.)
3 23.04. Causality, Erlang OTP
4 30.04. Replication, FLP
5 07.05. Quorums
6 14.05. Consensus
7 21.05. — (Pentecost)
8 28.05. Consistency
9 04.06. Conflict-Free Replicated Datatypes (updated, 11.06.)
10 11.06. Conflict-Free Replicated Datatypes
11 18.06. Transactions
12 25.06. Testing and Verification
13 02.07. Blockchain Technology
14 09.07. Programming Models

Please report errors and give feedback via our issue tracker or by mail.