Distributed Systems Course (fall 2018/2019)

Lecturer: Konrad Iwanicki
Assistants: Inga Rüb
Lectures: Wednesday, 2:15 PM - 3:45 PM, Room 4420
Lab classes: Wednesday, 4:15 PM - 5:45 PM, Rooms 3042 (group 1), 3045 (group 2)
Final exam: Wednesday, January 23, 2:15 PM - 3:45 PM (may be shorter), Room 4420

This (ninth) edition of the course consists of two components: lectures and lab classes. The lectures cover the principles, advanced concepts, and technologies of distributed systems, including communication, replication, fault tolerance, and security. The objective of the lab, in turn, is to give every student a chance to design, implement, and evaluate his own distributed system in the area of cloud computing, as well as to broaden the students' knowledge on the state of the art in distributed systems. 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 goals of the lab are twofold. First, the lab allows each student to build her own simple distributed system. The building process will consist of two assignments and one colloquium. Second, the lab creates an opportunity for the student to update other students with a piece of recent work in the area of distributed systems. This will have the form of an oral presentation.

To pass the lab, each student has to score a total of at least 31.5 points and a given number of points per each assignment. The detailed breakdown of the scores and deadlines is as follows:

Group #1
What When How many points Min. required points
Entry Assignment October 9, 2018, 23:59 CEST 2.5 5 1.5 3
Colloquium October 24, 2018, 16:00 CEST 2.5 0
Assignment 1 November 28, 2018, 23:59 CET 15 8
Assignment 2 January 8, 2019, 23:59 CET 25 14
Oral Presentation Individually set date (schedule) 15 8
Group #2
What When How many points Min. required points
Entry Assignment October 3 - October 9, 2018, 23:59 CEST 2.5 1.5
Lab Activity 1 October 24, 2018, 18:00 CEST 2.5 1.5
Assignment 1 November 7 - November 27, 2018, 23:59 CEST 15 8
Lab Activity 2 November 28, 2018, 18:00 CEST 2.5 1.5
Assignment 2 December 12 - January 8, 2018, 23:59 CEST 15 8
Assignment 3 January 9 - January 22, 2018, 23:59 CEST 12.5 6
Oral Presentation Individually set date (schedule) 10 5

Assignment solutions have to be handed in on time by submitting e-mails with topic “[DS2018] Solution X” (where X can be 1 or 2) to the tutor of your group (respectively, Konrad Iwanicki for group 1 and Inga Rüb for group 2). Since the tutors receive an excessive number of e-mails, e-mails with different topics may be ignored. Moreover, each day of delay in submitting a solution results in subtracting 2 points from the scores received for the solution. Normally, the delay must not be more than 7 days, after which an assignment is considered as failed (the student receives 0 points). However, each day a student participates in both a lecture and a lab gives the student one extra day of delay (for this day, the points are not subtracted). No future days during which the student intends to participate will be counted toward the reduction. For students working in pairs, the reduction will be counted as the average of the lectures attended by each of the participants (rounded down if necessary).

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

Additional rules for Group 1

At the beginning of the course, students may decide if they want to work on the assignments individually or in pairs. No larger groups will be allowed. The decision cannot be changed during the semester (after the colloquium). The lecturer will not regard any conflicts within pairs as circumstances affecting grades. In other words, if you work in a pair, choose your partner well.

A presentation is in turn prepared individually and normally given in English (unless your tutor agrees to a different language) with slides in English. However, if foregin students enroll for the course, all presentations will be required to be given in English. The strict time limit of a single talk is 60 minutes, in case of one presentation per class, or 45 minutes, if there are two presentations during a single class. The presenting student will be interrupted after this period. During the talk, other students are discouraged from asking questions. After the talk, there is a questions-and-answers session, during which the presenter answers question posed by the lecturer and other students. The objective of the questions could be, for instance, to clarify some aspects of the paper or to learn the presenter's opinion on a problem related to the paper.

During her presentation of a paper, a student is obliged to display slides for the paper. As a reminder, they have to be in English. The student has to prepare the slides on her own. If some slides for the paper already exist on the Internet, the concents of those slides can be re-used by the student preparing her own slides only if re-using the contents does not violate any copyrights, especially when the student's presentation is made available online. Moreover, the student has to acknowledge using somebody else's slides. Finally, note that conference slides are typically meant for 20-30 minutes, whereas a lab presentation is 45 or 60 minutes, depending on the available time, as explained above.

Additional rules for Group 2

Lab activities need to be performed during the determined labs (see the table for dates). They require access to the devices, which are provided by the tutor.

A presentation is supposed to last no more than 15 minutes. It should give the audience an overview of the tackled problem, explain the solution proposed by the researchers as well as discuss strong and weak points of the presented idea. While own slides for the presentation are required and must be in English, it is preferrable that a whole talk is given in English. For a talk given in Polish the number of points received for the presentation is decreased by 3 points. If the audience wants to clarify certain aspects of the presented subject, the presentation can be followed by a quick questions-and-answers session.

Tips for giving a presentation

  • Read your paper well in advance to understand it and to later be able to answer other students' questions.
  • Practice your talk to fit in the time limit.
  • Try to briefly go over the related work cited in the paper as this can give you some valuable input on the problem the paper is solving.
  • Try to find any follow-ups on the paper because this can be rewarding as well. Skimming through follow-up papers will help you better understand the topic.
  • Ask the presenter questions that, rather than proving the presenter doesn't know something, lead to interesting discussions. You are not awarded points for mean or stupid questions.
  • If you have read and understood the presented paper, and if you have practiced your talk, relax during your presentation: you will surely be able to answer all questions.

Exam Rules

The exam covers the lecture topics. Each question has three subquestions with binary (TRUE/FALSE) answers. A students scores a point for a question only if the answers to all subquestions of the question are correct. Conversely, if an answer to any subquestion of the question is incorrect, no point is given for the entire question. Note that these scoring rules are really demanding (cf. the scores for 2017/2018).

Lecture Topics and Schedule

Since this is still a developing course, this year's lectures will be given mostly based on a book by my PhD adviser and the head of my former research group: Maarten van Steen and Andrew S. Tanenbaum, “Distributed Systems,” CreateSpace Independent Publishing Platform, 3.01 edition (February 1, 2017), 596 pages, ISBN 978-1543057386. Purchasing the book is not mandatory as the lecture slides will be available here. There will be a few lectures with an extra material, though.

Date Topics Slides
October 3, 2018 Introduction:
definition of distributed system, properties of distributed systems, common types of distributed systems
lecture 01
October 10, 2018 Architectures:
architectural styles, system architectures
lecture 02
October 17, 2018 Processes:
threads, virtualization, clients & servers, server clusters, code migration
lecture 03
October 24, 2018 Communication:
fundamentals, remote procedure call, message-oriented communication, stream-oriented communication, multicast communication
lectures 04-05 (part A and B)
October 31, 2018
November 7, 2018 Naming:
basic terms and definitions, flat naming, structured naming, attribute-based naming
lecture 06 (part A and B)
November 14, 2018 Synchronization and Coordination:
clock synchronization, logical clocks, total-ordered multicast, causal-ordered multicast, mutual exclusion, positioning of nodes, leader election
lectures 07-08 (part A and B)
November 21, 2018
November 28, 2018 No lecture because of the lecturer's PC meeting
December 5, 2018 Replication and Consistency (Part I):
replica management, continuous consistency, data-centric consistency models, consistency protocols
lecture 09
December 12, 2018 Fault Tolerance (Part I):
failure models, failure masking, failure detection, reliable client-server communication, atomic multicast, two-phase commit, three-phase commit, checkpointing, logging, recovery, agreement in faulty systems
lectures 10-11
December 19, 2018
January 9, 2019 Fault Tolerance (Part II):
agreement in faulty systems (continued), Paxos
lecture 12
January 16, 2019 Replication and Consistency (Part II):
CAP theorem, PACELC, eventual consistency, conflict-free replicated data types, client-centric consistency models
lecture 13
January 23, 2019 FINAL EXAM

Lab Topics and Schedule

The schedule of the lab classes for Group 1 with material relevant to building the distributed system is as follows:

Date Materials
October 3, 2018 Passing rules and Entry Assignment
October 10, 2018 Scenario 01
October 17, 2018 Talk by Microsoft
October 24, 2018 Scenario 02
October 31, 2018 Scenario 03
November 7, 2018 Scenario 04 and Assignment 01
November 14, 2018 Individual work and questions about Assignment 01
November 21, 2018 Scenario 05
November 28, 2018 Scenario 06
December 5, 2018 Scenario 07
December 12, 2018 Scenario 08 and Assignment 02
December 19, 2018 Individual work, questions about Assignment 02, Assignment 01 grading in spare time
January 9, 2019 Assignment 02 grading
January 16, 2019
January 23, 2019

The schedule of the lab classes for Group 2:

Date Materials
October 3, 2018 Scenario 01
October 10, 2018 Scenario 02
October 17, 2018 Scenario 03
October 24, 2018 Scenario 04
October 31, 2018 Scenario 05
November 7, 2018 Scenario 06
November 14, 2018 Scenario 07
November 21, 2018 Scenario 08
November 28, 2018 Scenario 09
December 5, 2018 Scenario 10
December 12, 2018 Scenario 11
December 19, 2018 Scenario 12
January 9, 2019 Scenario 13
January 16, 2019 Scenario 14
January 23, 2019 Scenario 15

Student Presentation Topics and Schedule

The schedule of the students' presentations for is as follows:

Group 1 (K. Iwanicki)

Date Presenter Topic
October 3, 2018 Konrad Iwanicki Lab organization and rules. Entry Assignment.
October 10, 2018 Konrad Iwanicki Assignment presentation.
October 17, 2018 Microsoft External talk (at 16:15 in 4420)
October 24, 2018 Jakub Kuklis Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, Manjunath Kudlur, Josh Levenberg, Rajat Monga, Sherry Moore, Derek G. Murray, Benoit Steiner, Paul Tucker, Vijay Vasudevan, Pete Warden, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng: “TensorFlow: A System for Large-Scale Machine Learning”
October 31, 2018 Milena Wojtczak Khanh Nguyen, Lu Fang, Guoqing Xu, Brian Demsky, Shan Lu, Sanazsadat Alamian, and Onur Mutlu: “Yak: A High-Performance Big-Data-Friendly Garbage Collector”
November 7, 2018 Antoni Rosciszewski Ben Pfaff, Justin Pettit, Teemu Koponen, Ethan Jackson, Andy Zhou, Jarno Rajahalme, Jesse Gross, Alex Wang, Joe Stringer, Pravin Shelar, Keith Amidon, and Martín Casado: “The Design and Implementation of Open vSwitch”
November 14, 2018 Marian Dziubak Bryce Kellogg, Vamsi Talla, Shyamnath Gollakota, and Joshua R. Smith: “Passive Wi-Fi: Bringing Low Power to Wi-Fi Transmissions”
Artur Jamro Xu Zhao, Kirk Rodrigues, Yu Luo, Ding Yuan, and Michael Stumm: “Non-Intrusive Performance Profiling for Entire Software Stacks Based on the Flow Reconstruction Principle”
November 21, 2018 Tadeusz Dudkiewicz Deepak Vasisht, Swarun Kumar, and Dina Katabi: “Decimeter-Level Localization with a Single WiFi Access Point”
November 28, 2018 No presentation
December 5, 2018 Maciej Wachulec Yogeshwer Sharma, Philippe Ajoux, Petchean Ang, David Callies, Abhishek Choudhary, Laurent Demailly, Thomas Fersch, Liat Atsmon Guz, Andrzej Kotulski, Sachin Kulkarni, Sanjeev Kumar, Harry Li, Jun Li, Evgeniy Makeev, Kowshik Prakasam, Robbert van Renesse, Sabyasachi Roy, Pratyush Seth, Yee Jiun Song, Benjamin Wester, Kaushik Veeraraghavan, and Peter Xie: “Wormhole: Reliable Pub-Sub to Support Geo-replicated Internet Services”
December 12, 2018 Gabriela Gierasimiuk Kaushik Veeraraghavan, Justin Meza, David Chou, Wonho Kim, Sonia Margulis, Scott Michelson, Rajesh Nishtala, Daniel Obenshain, Dmitri Perelman, and Yee Jiun Song: “Kraken: Leveraging Live Traffic Tests to Identify and Resolve Resource Utilization Bottlenecks in Large Scale Web Services”
December 19, 2018 Wojciech Kordalski Ashley Flavel, Pradeepkumar Mani, David A. Maltz, Nick Holt, Jie Liu, Yingying Chen, and Oleg Surmachev: “FastRoute: A Scalable Load-Aware Anycast Routing Architecture for Modern CDNs”
Pawel Ziecik Bryan Kate, Eddie Kohler, Michael S. Kester, Neha Narula, Yandong Mao, and Robert Morris: “Easy Freshness with Pequod Cache Joins”
January 9, 2019 Michal Preibisch Junchen Jiang, Vyas Sekar, Henry Milner, Davis Shepherd, Ion Stoica, Hui Zhang: “CFA: A Practical Prediction System for Video QoE Optimization”
Bartosz Stebel Jialin Li, Ellis Michael, Naveen Kr. Sharma, Adriana Szekeres, and Dan R. K. Ports: “Just Say NO to Paxos Overhead: Replacing Consensus with Network Ordering”
January 16, 2019 Tomasz Obuchowski Ramnatthan Alagappan, Aishwarya Ganesan, Yuvraj Patel, Thanumalayan Sankaranarayana Pillai, Andrea C. Arpaci-Dusseau, and Remzi H. Arpaci-Dusseau: “Correlated Crash Vulnerabilities”
Katarzyna Kowalska Rachid Guerraoui, Matej Pavlovic, and Dragos-Adrian Seredinschi: “Incremental Consistency Guarantees for Replicated Objects”
January 23, 2019 No presentations: grading Assignment 2

Group 2 (I. Rüb)

Date Presenter Topic
October 31, 2018 To be announced
To be announced
November 7, 2018 To be announced
To be announced
November 14, 2018 To be announced
To be announced
December 5, 2018 To be announced
To be announced
December 12, 2018 To be announced
To be announced
December 19, 2018 To be announced
To be announced
January 9, 2018 To be announced
To be announced
January 16, 2018 To be announced
To be announced
January 23, 2018 To be announced
To be announced

Past Exams

Below, you can find the questions from past exams:

Year Exam Set Participants Points
Course Exam % Available Min Avg Med Max
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