Distributed Systems Course (fall 2021/2022)

Lecturer: Konrad Iwanicki
Assistants: Wojciech Ciszewski
Lectures: Wednesday, 2:15 PM - 3:45 PM, Room 4420
Lab classes: Wednesday, 4:15 PM - 5:45 PM, Rooms 2042 (IK's group), 2043 (CW's group)

This (twelth) edition of the course consists of two components: lectures and labs. The lectures cover principles, algorithms, and technologies of distributed systems. The objective of the labs, in turn, is to give students a chance to design, implement, and evaluate their own distributed systems addressing selected real-world problems. Compared to earlier years, the course was totally remodeled last year and is still in the process of adaptation: the new lectures focus more on fundamental knowledge that should remain valid for many years to come; the new labs utilize a popular, modern programming language for distributed systems, Rust. The course is recommended for graduate students attending the distributed systems seminar and following the DOS Master's track, as well as for other students interested in computer systems. The course may be given in English.

Passing Rules

To pass the course, a student has to pass the lab and score a sufficient number of points in total. The points can be scored for:

  • lab assignments,
  • a written exam at the end of the semester.

The details are explained in subsequent sections.

Lab Rules

The main objective of the lab is exercising in practice the knowledge covered in the lectures. To this end, almost each lab concludes with a small programming assignment connected directly with the topic of the lab and worth 1 or 2 points, depending on the envisioned intricacy of the solution. Moreover, there are three larger programming assignments that require the students to apply the accumulated knowledge in order to solve practical problems. In addition, since virtually all lab assignments are expected to be handed in Rust, the students have a plenty of opportunities to learn this programming language.

To pass the lab, each student has to score a total of at least 30 points and a given number of points for each part of the lab. The detailed breakdown of the scores and deadlines (Warsaw time) is as follows:

What When (tentative) Points
Announcement Deadline Available Required
Small Assignments Almost at each lab following Wednesday, 13:59 15 8
Large Assignment 1 October 27th, 2021 November 9th, 2021, 23:59 CET 8 4
Large Assignment 2 November 17th, 2021 December 14th, 2021, 23:59 CET 32 9
Large Assignment 3 December 22nd, 2021 January 21st, 2022, 23:59 CET 25 0

Solutions for the assignments (both small and large) have to be handed in through our teaching-support system: Moodle. To this end, one has to be registered in Moodle and assigned to the course group of the right lab tutor (as appearing in USOS); otherwise, the submitted solutions may not be graded.

Small assignments aim to stimulate the students' activity during the labs and promote systematic work. They must be solved by individual students. For solving any such assignment, the author receievs either zero, a half, or all out of the available points (i.e., 1 or 2, depending on the assignment). In order to score any points for a solution of an assignment, all of the following criteria have to be met:

  • the author of the solution has to actively participate in the lab during which the assignment is announced;
  • the solution has to be submitted on time;
  • subject to the tutors' interpretation and depending on the assignment: to receive all points, the solution has to be good (which typically means passing all tests) or, to receive half of the points, be good enough (which typically implies just a tiny error, subject to the tutors' interpretation).

In other words, it is not possible to hand in a solution of a small assignment without active participation in the corresponding lab. There are no deadline extensions for the small assigments. Nor is it possible to correct a solution and resubmit. All in all, failling to score the minimal required number of points for the small assignments implies a lack of engagement in the course and precludes passing it.

Large assignments aim in turn to check the students' knowledge and ability to apply it in practice. They have to be done individually by each student.

Small delays in submitting solutions to the first two large assignments are tolerated, but each begun day of such a delay results in subtracting 2 points from the scores received for the solution. Furthermore, the total delay must not exceed 14 days, after which the assignment is considered as failed (the student receives 0 points). There is, however, an exception: each day a student participates in the lecture gives them one extra day of delay (for this day, the points are not subtracted). Nevertheless, the 14-day limit for the maximal extension still holds. What is more, unlike for small assignments, for the first two large assignments there is a second-chance submission deadline: the last day of the regular exam session (just before the break between the semesters). No delays are tolerated for that deadline, even if one has some points left for attended lectures. A second-chance solution of an assignment is graded as if submitted within the regular deadline with no delay but the received score is capped at the half of the number of points available for the assignment and any received grade is a second-term grade.

The third large assignment is somewhat special. It is optional: there is no minimal number of points required for this assignment. Its only goal is to increase the number of total points available for the lab, and hence to allow for obtaining a better grade. For these reasons, no submission delays are tolerated and there is no second-chance submission deadline for this assignment.

For both small and large assignments:

  • it is allowed to talk about your ideas on solving the assignments with your colleagues;
  • it is FORBIDDEN to show, share, exchange code (in any form) without a prior permission from the lecturer.

Exam Rules

The exam covers the lecture topics. It is expected to be stationary but, given the pandemic, the Faculty authorities may change this decision. In any case, note that the exams in the previous years were really demanding (cf. the scores for 2019/2020).

Passing Strategies

Two main strategies of passing the course are possible. As a reminder, they both require passing the lab first.

The first strategy simply involves passing the lab and then taking the exam. In such a case, the total number of points scored for the lab is capped at 50, and the resulting number is increased by the points obtained during the exam, scaled as if the maximal number of points available for the exam was 50. In other words, the maximal number of points a student can obtain in this strategy is 100: 50 for the labs and 50 for the exam. The final grade is then calculated as follows:

Points [0-60) [60-68) [68-76) [76-84) [84-92) [92-100]
Grade 2 (fail) 3 3.5 4 4.5 5

The second strategy allows for passing the course without taking the exam, that is, based solely on the scores for the labs. This is referred to as the zeroth-term exam in the rules and regulations for our studies. In this strategy, the total number of points scored for the lab is not capped at any number, but translated directly to the final grade as follows:

Points [0-30) [30-40) [40-50) [50-60) [60-70) [70-80]
Grade 2 (fail) 3 3.5 4 4.5 5

Important note: Taking the exam implies choosing the first strategy. In particular, even if one could pass the course by following the second strategy, if they take the exam and fail to score a suffient number of points, they fail the entire course.

Lecture Topics and Schedule

The lectures will be given mostly based on the lecturer's private slides. Each slide deck involves information on the relevant literature, if it exists. As this is the second edition of the course after remodeling, there may be some legacy slides, whenever the lecturer was too short on time to prepare new ones.

Date Topics Slides Videos*
October 6, 2021 Introduction:
definition of “distributed system”, properties of distributed systems, common types of distributed systems
T01 T01
(2020 edition)
October 13, 2021 System Design:
common problems and phenomena in systems, different perspectives on system analysis, complexity and means of coping with it in general systems and (distributed) computer systems specifically, three fundamental abstractions
T02 T02
(2020 edition)
October 20, 2021 Building Blocks:
processes, threads, containers, VMs, socket-based communication, communication middleware, stable storage
T03 T03
(2020 edition)
October 27, 2021 Algorithmic Prerequisites:
models of processes, storage, (secure) communication, and distributed algorithms, algorithm analysis for correctness and performance, abstracting failures and timing, common distributed system models, failure detection and leader election algorithms
T04 T04A
T04B
(2020 edition both)
November 3, 2021
November 10, 2021 Reliable Broadcast:
defining and implementing reliability (best-effort, consistent, regular, uniform) under different failure models (fail-stop, fail-silent, fail-recovery), message ordering in broadcast
T05 T05A
T05B
November 17, 2021 Fault-tolerant Registers
defining and implementing various semantics (safe, regular, atomic) under different failure models (fail-stop, fail-silent, fail-recovery), handling concurrent writes, the notion of linearizability and quiescence
T06 T06A
T06B
November 24, 2021
December 1, 2021 State Machine Replication and Consensus:
formulation of the state machine replication problem, formulation of the consensus problem in various system models, algorithms implementing consensus (Paxos, Raft), discussion of side issues, distributed commit (labs)
T07 T07A
T07B
December 8, 2021
December 15, 2021 CAP Theorem and Eventual Consistency
CAP theorem, PACELC, eventual consistency, conflict-free replicated data types, client-centric consistency models
T08 T08
December 22, 2021 Division of Data and Computations
logical and physical placement, local load balancing problems, the power of two choices, consistent hashing, distributed hash tables, global load balancing problems, stable allocations
T09 T09
January 12, 2022 Time and Clock Synchronization:
measuring time, clock synchronization principles and techniques, applications of synchronized clocks, external consistency, Spanner and TrueTime
T10 T10
(2020 edition)
January 19, 2022 Byzantine Fault Tolerance:
instances of the three fundamental abstractions in the fail-arbitrary model (reliable broadcast, wait-free distributed register, consensus)
T11 no video was recorded
January 26, 2022

* For the videos from the 2020 edition, the contents may differ compared to this edition's slides.

Lab Topics and Schedule

The schedule of the lab classes is as follows:

Date Materials
October 6, 2021 Passing rules, organization, and Scenario 01
October 13, 2021 Scenario 02
October 20, 2021 Scenario 03
October 27, 2021 Scenario 04 and Large Assignment 1
November 3, 2021 Scenario 05
November 10, 2021 Scenario 06
November 17, 2021 Scenario 07 and Large Assignment 2
November 24, 2021 Scenario 08
December 1, 2021 discussion of the solutions for Large Assignment 1
December 8, 2021 Scenario 09
December 15, 2021 Scenario 10
December 22, 2021 Scenario 11 and Large Assignment 3
January 12, 2022 discussion of the solutions for Large Assignment 2
January 19, 2022 Scenario 12
January 26, 2022 Scenario 13

Past Exams

Below, you can find the aggregated scores and some questions from past exams:

Year Exam Set Participants Points
Course Exam % Available Min Avg Med Max
2019/2020 Final (test) 29 20 69.0 25 1 9.4 9 17
2018/2019 Final (test) 28 22 78.6 25 2 11.52 11 18
2017/2018 Final (test) 33 24 72.7 25 2 10.38 11 19
2016/2017 Final (test) 20 15 75.0 25 7 13.13 13 20
2015/2016 Final (test) 16 13 81.3 25 4 10.08 10 22
2014/2015 Final (test) 17 17 100 25 5 12.76 13 20
2013/2014 Final (test) 16 16 100 25 11 14.69 13 21
2012/2013 Final (test) 34 34 100 25 3 10.33 10 22
2011/2012 Final 36 34 94.4 50 10 29.85 30.5 49
2010/2011 Part II 26 21 80.8 25 3.75 16.27 13.5 24.25
2010/2011 Late Part I 26 11 42.3 25 13.75 21.6 21.25 24.75
2010/2011 Early Part I 26 17 65.4 25 9.25 14.9 13.5 22