Distributed Systems Course (fall 2015/2016)

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 30 points and a given number of points per each assignment. The detailed breakdown of the scores and deadlines is as follows:

What	When	How many points	Min. required points
Colloquium	October 14, 2015, 16:00 CEST	5	0
Assignment 1	October 30, 2015, 23:59 CET	10	6
Assignment 2	January 8, 2016, 23:59 CET	30	16
Oral Presentation	Individually set date (schedule)	15	8

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.

Assignment solutions have to be handed in on time by submitting e-mails with topic “[DS2015] Solution X” to the lecturer (where X can be 1 or 2). Since the lecturer receives 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 multiplying the scores received for the solution by 0.9. 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 (in this day, the points are not multiplied by 0.9). 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.

A presentation is in turn prepared individually and normally given in Polish 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 PowerPoint/PDF 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.

Tips:

• 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 as well as the students' presentations. It consists of a series of questions. 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 2012/2013).

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: Principles and Paradigms,” Second Edition, Prentice Hall, 2007, 702 pages, ISBN 9780132392273. 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 7, 2015	Introduction: goals of distributed systems, common types of distributed systems	lecture 01
October 14, 2015	Architectures: architectural styles, system architectures, self-management	lecture 02
October 21, 2015	Processes: threads, virtualization, clients & servers, server clusters, code migration	lecture 03
October 28, 2015	Communication: fundamentals, remote procedure call, message-oriented communication, stream-oriented communication, multicast communication	lecture 04-05
November 4, 2015
November 18, 2015	Naming: basic terms and definitions, flat naming, structured naming, attribute-based naming	lecture 06 and supplement
November 25, 2015	Synchronization: clock synchronization, logical clocks, totally-ordered multicast, causally-ordered multicast mutual exclusion, global positioning of nodes, leader election	lecture 07-08 and supplement
December 2, 2015
December 9, 2015	Replication and Consistency (Part I): replica management, continuous consistency, data-centric consistency models, consistency protocols	lecture 09 (selected slides)
December 16, 2015	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	lecture 10 (selected slides)
January 13, 2016	Fault Tolerance (Part II): agreement in faulty systems (continued), Paxos	lecture 11
January 20, 2016	Replication and Consistency (Part I): CAP theorem, PACELC, eventual consistency, conflict-free replicated data types, client-centric consistency models	lecture 12
January 27, 2016	FINAL EXAM

Lab Topics and Schedule

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

Date	Materials
October 7, 2015	Scenario 01
October 14, 2015	Scenario 02
October 21, 2015	Scenario 03
October 28, 2015	Scenario 04
November 4, 2015	Scenario 05
November 18, 2015	Scenario 06
November 25, 2015	Scenario 07
December 2, 2015	Scenario 08
December 9, 2015	Individual work, assignment grading in spare time
December 16, 2015
January 13, 2016
January 20, 2016
January 27, 2016	Entire lab dedicated to assignment grading

Student Presentation Topics and Schedule

The schedule of the students' presentations is as follows:

Date	Presenter	Topic
October 7, 2015	Konrad Iwanicki	Lab organization and rules. Assignment presentation.
October 14, 2015	Juliusz Straszynski	Kay Ousterhout, Patrick Wendell, Matei Zaharia, Ion Stoica: “Sparrow: Distributed, Low Latency Scheduling”
October 21, 2015	Jan Wroblewski	Piyus Kedia, Sorav Bansal: “Fast Dynamic Binary Translation for the Kernel”
October 28, 2015	Jakub Luczynski	Eno Thereska, Hitesh Ballani, Greg O'Shea, Thomas Karagiannis, Antony Rowstron, Tom Talpey, Richard Black, Timothy Zhu: “IOFlow: A Software-Defined Storage Architecture”
November 4, 2015	Krzysztof Pachacz	Matei Zaharia, Tathagata Das, Haoyuan Li, Timothy Hunter, Scott Shenker, Ion Stoica: “Discretized Streams: Fault-Tolerant Streaming Computation at Scale”
November 18, 2015	Pawel Kaminski	Sameer Agarwal, Aurojit Panda, Barzan Mozafari, Samuel Madden, Ion Stoica: “BlinkDB: Queries with Bounded Errors and Bounded Response Times on Very Large Data”
November 25, 2015	Georgia Brikis	Lenin Ravindranath, Jitendra Padhye, Ratul Mahajan, Hari Balakrishnan: “Timecard: Controlling User-Perceived Delays in Server-Based Mobile Applications”
December 2, 2015	Pawel Walczak	Derek G. Murray, Frank McSherry, Rebecca Isaacs, Michael Isard, Paul Barham, Martin Abadi: “Naiad: A Timely Dataflow System”
December 9, 2015	Jakub Zakrzewski	Qi Huang, Ken Birman, Robbert van Renesse, Wyatt Lloyd, Sanjeev Kumar, Harry C. Li: “An Analysis of Facebook Photo Caching”
	Tomasz Dziopa	Liang Zhang, Fangfei Zhou, Alan Mislove, Ravi Sundaram: “Maygh: Building a CDN from client web browsers”
December 16, 2015	Piotr Podolski	Zhengping Qian, Yong He, Chunzhi Su, Zhuojie Wu, and Hongyu Zhu, Taizhi Zhang, Lidong Zhou, Yuan Yu, Zheng Zhang: “TimeStream: Reliable Stream Computation in the Cloud”
	Lukasz Kryston	Harry C. Li, Allen Clement, Edmund L. Wong, Jeff Napper, Indrajit Roy, Lorenzo Alvisi, Michael Dahlin: “BAR Gossip”
January 13, 2016	Michal Niewiadomski	Tudor David, Rachid Guerraoui, Vasileios Trigonakis: “Everything You Always Wanted to Know about Synchronization but Were Afraid to Ask”
	Pawel Banaszewski	Stephen Tu, Wenting Zheng, Eddie Kohler, Barbara Liskov, Samuel Madden: “Speedy Transactions in Multicore In-Memory Databases”
January 20, 2016	Patryk Hes	Douglas B. Terry, Vijayan Prabhakaran, Ramakrishna Kotla, Mahesh Balakrishnan, Marcos K. Aguilera, Hussam Abu-Libdeh: “Consistency-Based Service Level Agreements for Cloud Storage”
	Agnieszka Paszkowska	Mahesh Balakrishnan, Dahlia Malkhi, Ted Wobber, Ming Wu, Vijayan Prabhakaran, Michael Wei, John D. Davis, Sriram Rao, Tao Zou, Aviad Zuck: “Tango: Distributed Data Structures over a Shared Log”
January 27, 2016	No presentations: grading Assignment 2

Past Exams

Below, you can find the questions from past exams:

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