Distributed Systems Course (fall 2020/2021)

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