Distributed Systems Course (fall 2022/2023)

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 difficulty 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 26th, 2022	November 8th, 2022, 23:59 CET	8	4
Large Assignment 2	November 23rd, 2022	December 20th, 2022, 23:59 CET	32	9
Large Assignment 3	December 21st, 2022	January 20th, 2023, 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 current situation, 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. There may be some legacy slides, whenever the lecturer was too short on time to prepare new ones.

Date	Topics	Slides
October 5, 2022	Introduction: definition of “distributed system”, properties of distributed systems, common types of distributed systems	T01
October 12, 2022	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, available building blocks	T02
October 19, 2022	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	T03
October 26, 2022
November 2, 2022	No class (virtual Monday)
November 9, 2022	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	T04
November 16, 2022	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	T05
November 23, 2022
November 30, 2022	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)	T06
December 7, 2022
December 14, 2022	CAP Theorem and Eventual Consistency CAP theorem, PACELC, eventual consistency, conflict-free replicated data types, client-centric consistency models	T07
December 21, 2022	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	T08
January 11, 2023	Time and Clock Synchronization: measuring time, clock synchronization principles and techniques, applications of synchronized clocks, external consistency, Spanner and TrueTime	T09
January 18, 2023	Byzantine Fault Tolerance: instances of the three fundamental abstractions in the fail-arbitrary model (reliable broadcast, wait-free distributed register, consensus)	T10
January 25, 2023

Lab Topics and Schedule

The schedule of the lab classes is as follows:

Date	Materials
October 5, 2022	Passing rules, organization, and Scenario 01
October 12, 2022	Scenario 02
October 19, 2022	Scenario 03
October 26, 2022	Scenario 04 and Large Assignment 1
November 2, 2022	No class (virtual Monday)
November 9, 2022	Scenario 05
November 16, 2022	Scenario 06
November 23, 2022	Scenario 07 and Large Assignment 2
November 30, 2022	Scenario 08
December 7, 2022	Scenario 09
December 14, 2022	Scenario 10
December 21, 2022	Scenario 11 and Large Assignment 3
January 11, 2023	Scenario 12
January 18, 2023	Scenario 13
January 25, 2023	Scenario 14

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