Distributed Algorithms

Master course, Fall 2014

Prerequisites: none.

Note: this course is independent from the course Concurrent Algorithms.

Last updated: February 20, 2015, 10:05

• Published grade distributions and project winners.
• Added final exam for download.
• Added information on the final exam and on the Q&A session.
• Added final exam from 2012 with solution.
• Added tenth week's solutions.
• Bonus project assignment updated! 2 modifications: 1) removed the the single-threaded constraint and 2) added assumption of a correct majority of processes.
• New slides uploaded.
• Deadline for the bonus project extended until Sunday, January 11, 2015.
• Added section “Bonus project”
• Added ninth week's solutions and tenth week's exercises.
• Added slides for Byzantine fault tolerance.
• Added eight week's solutions and ninth week's exercises.
• Added seventh week's solutions and eight week's exercises.
• Added sixth week's solutions and seventh week's exercises.
• Updated slides for group membership and terminating reliable broadcast
• Exceptionally, on Wednesday, November 5th, office hours of Matej Pavlovic and Cheng Wang will take place between 13:00 and 14:00.
• Exercise sheet 6 updated to clarify exercise 1.
• Updated results for the midterm
• Added fifth week's solutions and sixth week's exercises.
• Updated slides for non-blocking atomic commit.
• Corrected a mistake in the midterm solution. (Question 2, property TOB5)
• Solution to midterm 2014 available.
• Short video lecture: Consensus in an unreliable network of processors
• Published results for the midterm
• Added Fifth week's exercises
• Midterm from 2012 with solution is available. Note, however, that the grading scheme changed since 2012 and so did the form of the midterm.
• Added fourth week's solutions
• Added fourth week's exercises and third week's solutions.
• Published midterm organization
• Added two additional problems to third week's exercises.
• Added third week's exercises and second week's solutions.
• Updated slides for causal and total order broadcast.
• Fixed midterm date: 20.10.2014
• Corrected solutions to first exercise session.
• Added second week's exercises and first week's solutions.
• Updated slides for second lecture
• Created page for DA 2014.

• The course is given on Mondays, 15:15−17:00, in ELA01.
• The exercises are given on Mondays, 17:15-18:00, in BC01 & BC03.
• The midterm will take place on Monday, October 20th 2014, 15:15-17:00, in ELA01 and PO01 (see below).
• A Q&A session for students preparing for the exam will take place on Monday, January 12th 2015, at 15:15 in BC 01 (room of the exercises).
• The final exam will take place on Friday, 16.01.2015, from 14:00 to 17:00

To help students prepare for the final exam, there will be a Q&A session on Monday, January 12th 2015, at 15:15 in BC 01 (room of the exercises). Any course-related questions will be answered by the assistants.

When

The final exam will take place on Friday, 16.01.2015, from 14:00 to 17:00

Where

The final exam will take place in three rooms concurrently: CO1, CO2, and CO3. The assignment is based on your last name:

• If your last name starts with A-G, you are in CO1.
• If your last name starts with H-P, you are in CO2.
• If your last name starts with R-Z, you are in CO3.

What

The questions of the exam will cover all topics covered by the lectures, except the lecture on BFT (Byzantine generals, PBFT).

Grade distributions

The bonus project is optional. The task is to implement Uniform Reliable Broadcast using message passing. 5 best solutions will be awarded a bonus of 0.5 grade point on top of the final course grade. Further details are provided in the Project description.

Downloads

Project description

Template files

Deadline and submission

All project files (as required by the project description) need to be submitted by e-mail to matej.pavlovic@epfl.ch before the start of the Christmas break until Sunday, January 11, 2015, 23:59.

Winners

Five best submissions, the authors of which were awarded a final grade improvement of 0.5:

• 244269
• 203447
• 244587
• 233424
• 245651

When

The midterm will take place on Monday, October 20th 2014 between 15:15 and 17:00.

Where

The midterm will take place in two rooms concurrently: ELA01 (where the weekly lectures take place) and PO01 (Polydome). The assignment is based on your last name:

• If your last name starts with A-G, you are in ELA01.
• If your last name starts with H-Z, you are in PO01.

Results

You can find your midterm grade here: 2014 midterm grades.

The distribution of grades is the following (only people who did not show up received 0 points):

• Lecturers:
  • Prof. Rachid Guerraoui, office INR 310, web page
• Teaching Assistants:
  • Cheng Wang, office INR 313, web page, office hours: Wednesdays 10:00 - 11:00 or any time by appointment
  • Matthaios Olma, office BC 240, web page, office hours: Thursday 10:00 - 11:00 or any time by appointment
  • Matej Pavlovic, office INR 314, web page, office hours: Wednesdays 10:00 - 11:00 or any time by appointment

• Rachid Guerraoui and Luis Rodrigues - Introduction to Reliable Distributed Programming, available at 'La Fontaine' (with a student discount) or at amazon.de.

• Christian Cachin, Rachid Guerraoui and Luis Rodrigues - Introduction to Reliable and Secure Distributed Programming

• We prepared a document describing the language used for module specification and implementation, the notion of layering, and the notion of process. (odt pdf)

• Short video lecture: Consensus in an unreliable network of processors

Note that the slides will most likely be edited as the semester progresses, so make sure you have the latest version.

• Exercises are made available on the course webpage each Monday.

• Exercises are not graded and do not count towards the final grade. However, solving them helps you better understand the course material and prepare for the final exam.

• Solutions to exercises will be given during the exercise sessions one week later after the exercises were given. Also, solutions will be available on the course webpage one week later after the exercises were given.

• There will be a midterm in the second half of the semester. It is not mandatory, but it may improve the final grade (see below).

• The final grade will be calculated using the formula max( 1/3*<midterm> + 2/3*<final> , <final> ), where <midterm> and <final> are the results of the midterm and the final exam, respectively. The final exam and the midterm will be written and closed-book.