Distributed Systems Course (fall 2020/2021)

Lecturer: Konrad Iwanicki
Assistants: Mateusz Banaszek
Lectures: Wednesday, 2:15 PM - 3:45 PM, Room 4420
Lab classes: Wednesday, 4:15 PM - 5:45 PM, Rooms 3042 (KI's group), 3045 (MB's group)
NOTICE: Due to the COVID-19 pandemic, all classes will be given online.

This (eleventh) 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 previous years, the course has been totally remodeled: 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 score at least 60 out of a total of 100 points and pass the lab (see below). The points can be scored for:

  • lab assignments: up to 50 points
  • a written exam at the end of the semester: up to 50 points

The final grade is calculated as follows:

Points 0-51 52-59 60-67 68-75 76-83 84-91 92-...
Grade 2 (fail) 2+ (fail) 3 3+ 4 4.5 5

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 one point. Moreover, there are two large 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 11 6
Large Assignment 1 November 25, 2020 December 14, 2020, 23:59 15 8
Large Assignment 2 December 16, 2020 January 20, 2021, 23:59 30(+3) 16

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 can be solved by individual students or in pairs, formed ad hoc during the lab when a given assignment is announced. In the latter case, each pair member receives the same score. For solving any such assignment, a student or a pair may receive either 0 points or 1 point: no partial scores are possible. In order to score 1 point for a solution of an assignment, all of the following criteria have to be met:

  • the author(s) of the solution has to (both have to) actively participate in the lab during which the assignment is announced;
  • the solution has to be submitted on time;
  • the solution has to be good enough (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. Neither 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 their solutions 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). What is more, unlike for small assignments, for 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 minimal required number of points for the solution and any received grade is a second-term grade.

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 (except for small assignments solved in pairs where both pair members have to share code).

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).

However, because of the fact that this is the first edition of the course after remodeling, and hence may be more difficult and require more work than in the past years, it is possible to pass the course without taking the exam (so-called zeroth term) but only if one performs well in the labs. More specifically, to be allowed to pass the course in the zeroth term, one has to score at least 38 points from the lab. In such a case, the total score, F, is computed from the lab score capped at 50 points, L, as follows F = 1.6 x L.

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 first 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 21, 2020 Introduction:
definition of “distributed system”, properties of distributed systems, common types of distributed systems
T01 T01
October 28, 2020 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
(moved to the next lecture due to Rector's hours)
T02 T02
November 4, 2020 Building Blocks:
processes, threads, containers, VMs, socket-based communication, communication middleware, stable storage
T03 T03
November 12, 2020 (Thursday) 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
November 18, 2020 Reliable Broadcast:
defining and implementing reliability (best-effort, consistent, regular, uniform) under different failure models (fail-stop, fail-silent, fail-recovery, fail-arbitrary), message ordering in broadcast
T05 T05A
T05B
November 25, 2020
December 2, 2020 Fault-tolerant Registers
defining and implementing various semantics (safe, regular, atomic) under different failure models (fail-stop, fail-silent, fail-recovery, fail-arbitrary), handling concurrent writes, the notion of linearizability and quiescence
T06 T06A
T06B
T06C
December 9, 2020
December 16, 2020
January 8, 2021 (Friday) 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
January 13, 2021
January 20, 2021 CAP Theorem and Eventual Consistency
CAP theorem, PACELC, eventual consistency, conflict-free replicated data types, client-centric consistency models
T08 T08
January 27, 2021 Time and Clock Synchronization:
measuring time, clock synchronization principles and techniques, applications of synchronized clocks, external consistency, Spanner and TrueTime
T09 T09

Lab Topics and Schedule

The schedule of the lab classes is as follows:

Date Materials
October 21, 2020 Scenario 01
October 28, 2020 Scenario 02 (to be done individually due to Rector's hours)
November 4, 2020 another lecture instead of labs due to Rector's hours in the previous week
November 12, 2020
(Thursday)
Scenario 03
November 18, 2020 Scenario 04
November 25, 2020 Scenario 05 and Large Assignment 1
December 2, 2020 Scenario 06
December 9, 2020 Scenario 07
December 16, 2020 Scenario 08
January 8, 2021
(Friday)
(moved to December 16, 2020, so as to give more time for Large Assignment 2)
Scenario 09 and Large Assignment 2
Today, in turn, a discussion of the Assignment 1 results.
January 13, 2021 Scenario 10
January 20, 2021 Scenario 11
January 27, 2021 Scenario 12

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