Distributed Programming Laboratory LPD

Distributed Algorithms

Master course, Fall 2010

Prerequisites: none.

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

News

Last updated: Dec 21, 2010

  • Solutions of the exam are now online.
  • The final exam will take place in CO1, on January 22, 2011, from 8:15 until 11:15: the exam is closed book, no cheat-sheets/slides. The final includes all material taught in the course, and only first 10 slides from Byzantine Fault Tolerance lectures.
  • Solutions of the midterm are now online.
  • Solutions of the old exam (2008) are online.
  • Midterm will be on December 6, 2010: midterm is closed book, no cheat-sheets/slides. Midterm starts at 15:15, and end at 17:00, in the room ELA1. Midterm material includes everything taught up to November 22.
  • Add: Old exam text
  • Change: office hours, now on Tuesdays
  • You are invited to the following event, http://ic.epfl.ch/l-inaugurales. Please register as soon as possible
  • Exam will be on January 22, 2011
  • Add: new master/semester projects
  • Add: Link to the draft of the book
  • Updated for the year 2010.

Dates and schedule

  • The course is given on Mondays, 15:15−17:00, in ELA01.
  • The exercises are given on Mondays, 17:15-18:00, in BC03.

Teaching team

  • Lecturers:
    • Prof. Rachid Guerraoui, office INR 310, web page
  • Teaching Assistants:
    • Nikola Knežević, office INR 312, web page
      • Office hours: Tuesdays, 10:15 – 11:00.
    • Mihai Letia, office INR 314, web page

Textbook

  • 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 cover draft

Slides and exercises

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

Date Lecture Slides Exercises
September 27th Introduction pdf —
October 4th Reliable broadcast pdf the problem set
the solution
October 11th Causal Broadcast pdfthe problem set
the solution
October 18th Total Order Broadcast pdfthe problem set
the solution
October 25th
November 1st 		Consensus pdf the problem set
the solution
November 8th Non-Blocking Atomic Commit NBAC the problem set
the solution
November 15th Group Membership
Terminating Reliable Broadcast 		GMP
TRB 		the problem set
the solution
November 22th Group Membership/View Synchronous Communication the problem set
the solution
November 29th Shared Memory (regular registers) Shared Memory #1
Shared Memory #2 		the problem set
the solution
December 6th Midterm
December 13th Shared Memory (atomic registers)
BFT 		Shared Memory #3
Shared Memory #4
BFT 		the problem set
the solution
December 20th No lectures.
We will use the lecture time slots to explain the midterm solutions. 		Abortable Consensus (Problem 1)
NBAC (Problem 2)

Grades and Exam

The final exam will be written and closed-book. More information about grading and the final exam will be available in class.

Old Exams

The text of the 2008 exam is here. Solutions are here.

Exam (Solution)

A solution of the exam is here. PDF on Lucky Registers is here.

Midterm

A solution for the first problem is here.

A solution for the second problem is a combination of the algorithm in Figure 6 of Chandra & Toueg’s “Unreliable Failure Detectors for Reliable Distributed Systems” and Figure 2 of Guerraoui’s “Non-Blocking Atomic Commit in asynchronous distributed systems with failure detectors”). Pseudo code implementation is described in Solution 5.10 and Algorithm 6.6 of “Introduction to Reliable and Secure Distributed Programming”, 2ed. These implementations use much stronger failure detectors, but work even if the failure detector is weakened, as it was the case in the given problem.

The midterm is much harder than the exam, as the midterm carries bonus point.