Distributed Algorithms
Master course, Fall 2017
Prerequisites: none.
Note: this course is independent from the course Concurrent Algorithms.
News
The final exam will encompass all (and only) what Prof. Guerraoui presented, minus the class on Bitcoin/Blockchain (18 December).
- [New] Endterm details published.
- Midterm grades and distribution published.
- The class of 18 December will be in EL1 and will be a brief (distributed computing based) tutorial on Blockchain from 3:15 to 4:15, followed by a talk of Prof. Herlihy (Brown University)
- Added midterm '17 solutions.
- See the midterm details below.
- Lecture room changed to CM 1.
- Links to Wandida short lectures on broadcast.
- DA 2017 page is online.
Dates and schedule
- The course is given on Mondays, 15:15−17:00, in CM 1.
- The exercises are given on Mondays, 17:15-18:00, in BC01 and BC03.
Midterm (bonus exam)
- December 4, 3:15-5:00 pm.
- Rooms CM 1 and CO 3.
- See rooms distribution to know which room you are assigned to.
- There will be no exercises session after the exam.
Endterm
- Final exam date: Monday, 15th of January 2018, 08h15 to 11h15
- Room distribution list:
- A to H : SG 0211
- I to Z : SG 1
Teaching team
- Lecturers:
- Prof. Rachid Guerraoui, office INR 310, web page
- Teaching Assistants:
- Mahsa Taziki mahsa.taziki@epfl.ch, office INR 327, web page, office hours: Wednesdays 10:00 - 11:00 or any time by appointment
- Marjan Shahpaski marjan.shahpaski@epfl.ch, office BC 316, web page, office hours: Wednesdays 10:00 - 11:00 or any time by appointment
- Adrian Seredinschi dragos-adrian.seredinschi@epfl.ch, office INR 314, web page, office hours: Wednesdays 10:00 - 11:00 or any time by appointment
- El Mahdi EL MHAMDI elmahdi.elmhamdi@epfl.ch, office INR 210, web page, office hours: Wednesdays 10:00 - 11:00 or any time by appointment
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
Additional Material
- A Latex sample for algorithm implementation can be found here: alg-sample.tex
- Wandida video lecture: Consensus in an unreliable network of processors
- Wandida video lecture: Best Effort Broadcast
- Wandida video lecture: Broadcasts: Best effort vs Regular Reliable vs Uniform Reliable
- Wandida video lecture: Total Order Broadcast
Slides and exercises
Note that the slides will most likely be edited as the semester progresses, so make sure you have the latest version.
Lecture | Slides | Exercises |
---|---|---|
Introduction | intro.pdf | ex01.pdf logic101.pdf sol01.pdf Logic101Solution.pdf |
Reliable Broadcast | rb.pdf | ex02.pdf sol02.pdf |
Causal Broadcast | cb.pdf | ex03.pdf sol03.pdf |
Channels in Practice + Gossip | channels-gossip.pdf | ex04.pdfsol04.pdf |
Total Order Broadcast | tob.pdf | ex05.pdf sol05.pdf |
Consensus | consensus.pdf | ex06.pdf sol06.pdf |
Shared Memory | shared-memory.pdf | ex07.pdf ex07-2.pdf sol07.pdf sol07-2.pdf |
TRB GM & VSC | TRB.pdf GM-VSC.pdf | ex08.pdf sol08.pdf |
Atomic Commit | nbac.pdf | ex09.pdf sol09.pdf |
Midterm | midterm_2014.pdf midterm_2015.pdf mt2016_sol.pdf da17-midterm-solutions.pdf |
|
PBFT Byzantine Generals problem | pdf | Midterm & previous year exams discussion |
Information on exercises, grading, and exam
- 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 first week of december. It will be only counted as a bonus. Your grade = max{final, (final+midterm)/2}
- Both the midterm and final exams are closed book: no materials are allowed.