Differences

This shows you the differences between two versions of the page.

Link to this comparison view

education:da_2012 [2014/08/26 13:51] (current)
Line 1: Line 1:
 +====== Distributed Algorithms ======
  
 +**Master course, Fall 2012**
 +
 +**Prerequisites:​ none.**
 +
 +**Note: this course is independent from the course Concurrent Algorithms.**
 +
 +----
 +
 +===== News =====
 +
 +**Last updated: Dec 14, 2012 **
 +  * Uploaded the solution to the midterm exam
 +  * Uploaded Ex. 09
 +  * Updated Ex. 08 solution.
 +  * Uploaded Ex. 08 solution.
 +  * Uploaded Ex. 08
 +  * Uploaded course notes on Shared Memory
 +  * Uploaded Ex. 07 solution.
 +  * Uploaded Ex. 07
 +  * Uploaded Ex. 06 solution.
 +  * Uploaded course notes on Group Membership / Terminating Reliable Broadcast (November 12th)
 +  * Uploaded Ex. 06
 +  * Uploaded Ex. 05 solution.
 +  * Uploaded course notes on Non-Blocking Atomic Commit (November 5th)
 +  * Updated the date of the midterm exam (Monday, December 10th 2012, 15h15 and 16h00).
 +  * Updated the date of the final exam (Monday, January 14th 2013, 16h15). ​
 +  * Uploaded Ex. 05.
 +  * Uploaded Ex. 04 solution.
 +  * Uploaded course notes on Consensus (Oct 29th)
 +  * Uploaded Ex. 04.
 +  * Uploaded Ex. 03 solution.
 +  * Uploaded Ex. 03.
 +  * Uploaded Ex. 02 solution.
 +  * Uploaded course notes on Causal Broadcast (Oct 15th)
 +  * Uploaded Ex. 01 solution.
 +  * Uploaded updated slides for reliable broadcast.
 +  * Uploaded Ex. 01.
 +  * Updated for the year 2012.
 +
 +----
 +
 +
 +===== 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 BC01 & BC03.
 +
 +----
 +
 +
 +
 +
 +===== Teaching team =====
 +
 +  * **Lecturers:​** ​
 +                  * Prof. Rachid Guerraoui, office INR 310, [[http://​lpd.epfl.ch/​rachid|web page]]
 +  * **Teaching Assistants:​** ​
 +                 * Vasileios Trigonakis, office INR 312, [[http://​people.epfl.ch/​vasileios.trigonakis|web page]], office hours: Wednesdays, 14:00-15:00
 +                 * Radu Banabic, office INR 313, [[http://​people.epfl.ch/​radu.banabic|web page]], office hours: Thursdays, 14:00-15:00
 +                 * Giuliano Losa, office INR 315, [[http://​people.epfl.ch/​giuliano.losa|web page]], office hours: Tuesdays, 14:00-15:00
 +
 +----
 +
 +
 +
 +
 +===== Textbook =====
 +
 +  * **Rachid Guerraoui and Luis Rodrigues** - //​Introduction to Reliable Distributed Programming//,​ available at 'La Fontaine'​ (with a student discount) or at [[http://​www.amazon.de/​Introduction-to-Reliable-Distributed-Programming/​dp/​3540288457/​ref=sr_1_1?​ie=UTF8&​s=books-intl-de&​qid=1220959274&​sr=8-1|amazon.de]].  ​
 +
 +   * **Christian Cachin, Rachid Guerraoui and Luis Rodrigues** - //​Introduction to Reliable and Secure Distributed Programming//​
 +
 +----
 +
 +===== Additional Material =====
 +
 +  * We prepared a document describing the language used for module specification and implementation,​ the notion of layering, and the notion of process. ({{:​education:​protocol-language.odt|odt}} ​ {{:​education:​protocol-language.pdf|pdf}}) ​
 +
 +----
 +
 +
 +
 +===== 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 24<​sup>​th</​sup> ​ | Introduction ​             | {{:​education:​da12-introduction.pdf|pdf}} {{:​education:​da12-introduction.ppt|ppt}} | — |
 +|   ​October 1<​sup>​st</​sup> ​  | Introduction / Reliable broadcast ​       | {{:​education:​da12-reliablebroadcast.pdf|pdf}} {{:​education:​da12-reliablebroadcast.ppt|ppt}} | {{:​education:​da12_ex01.pdf|the problem set}} {{:​education:​da12_ex01_sol.pdf|solution}}|
 +|   ​October 8<​sup>​th</​sup> ​     | Reliable broadcast ​         | | {{:​education:​da12_ex02.pdf|the problem set}} {{:​education:​da12_ex02-sol.pdf|solution}} |
 +|   ​October 15<​sup>​th</​sup> ​     | Causal Broadcast ​         | {{:​education:​da12-causalbroadcast.pdf|pdf}} {{:​education:​da12-causalbroadcast.ppt|ppt}}| {{:​education:​da12-ex3.pdf|the problem set}} {{:​education:​da12-ex3-sol.pdf| solution}} |
 +|   ​October 22<​sup>​th</​sup> ​     | Total Order Broadcast ​         | {{:​education:​da12-totalorderbroadcast.pdf|pdf}} {{:​education:​da12-totalorderbroadcast.ppt|ppt}}| {{:​education:​da12-ex4.pdf|the problem set}} {{:​education:​da12-ex4-sol.pdf|solution}}|
 +|   ​October 29<​sup>​th</​sup> ​     | Consensus | {{:​education:​da12-consensus.pdf|pdf}} {{:​education:​da12-consensus.ppt|ppt}} | {{:​education:​da12-ex5.pdf|the problem set}} {{:​education:​da12-ex5-sol.pdf|solution}} |
 +|   ​November 5<​sup>​th</​sup> ​     | Non-Blocking Atomic Commit | {{:​education:​da12-nbac.pdf|pdf}} {{:​education:​da12-nbac.ppt|ppt}} | {{:​education:​da12-ex6.pdf|the problem set}} {{:​education:​da12-ex6-sol.pdf|solution}} |
 +|   ​November 12<​sup>​th</​sup> ​     | Group Membership\\ Terminating Reliable Broadcast | {{:​education:​da12-groupmembershipvsc.pdf|pdf}} {{:​education:​da12-groupmembershipvsc.ppt|ppt}} \\ {{:​education:​da12-terminatingreliablebroadcast.pdf|pdf}} {{:​education:​da12-terminatingreliablebroadcast.ppt|ppt}} | {{:​education:​da12-ex7.pdf|the problem set}} {{:​education:​da12-ex7-sol.pdf|solution}} |
 +|   ​November 19<​sup>​th</​sup> ​     | Group Membership\\ View Synchrony ​      ​| ​  | {{:​education:​da12-ex8.pdf|the problem set}} {{:​education:​da12-ex8-sol.pdf|solution}}|
 +|   ​November 26<​sup>​th</​sup> ​     | Shared Memory (regular registers) ​     | {{:​education:​da12-sharedmemory1.pdf|pdf#​1}} {{:​education:​da12-sharedmemory1.ppt|ppt#​1}} \\ {{:​education:​da12-sharedmemory2.pdf|pdf#​2}} {{:​education:​da12-sharedmemory2.ppt|ppt#​2}} | {{:​education:​da12-ex9.pdf|the problem set}} {{:​education:​da12-ex9-sol.pdf|solution}} |
 +|   ​December 3<​sup>​rd</​sup> ​     | Shared Memory (atomic registers) | {{:​education:​da12-sharedmemory3.pdf|pdf#​3}} {{:​education:​da12-sharedmemory3.ppt|ppt#​3}} \\ {{:​education:​da12-sharedmemory4.pdf|pdf#​4}} {{:​education:​da12-sharedmemory4.ppt|ppt#​4}} | |
 +|   ​December 10<​sup>​th</​sup> ​     |     ​Midterm ​  |||
 +|   ​December 17<​sup>​th</​sup> ​     | No lectures.\\ ​ We will use the lecture time slots to explain the midterm solutions. | ||
 +
 +----
 +
 +
 +
 +===== Grades and Exam =====
 +
 +The final exam will be written and closed-book and will take place on Monday, January 14th 2013, at 16h15.
 +
 +===== Old Exams =====
 +
 +The text of the 2008 exam is {{da08-exam.pdf|here}}. Solutions are {{da10-exam-2008-sol.pdf|here}}.
 +
 +===== Midterm =====
 +
 +The midterm exam will take place on Monday, December 10th. The class will be split in two halves, which will take the exam at 15h15 and 16h00, respectively. Students with last name starting with A..L (inclusive),​ should come at 15h15. Students with last name starting with M..Z (inclusive) should come at 16h00.
 +
 +**The solution to the midterm**: {{:​education:​da12-midterm_sol.pdf|miterm_solution}}
 +
 +**The grades from the midterm**: {{:​education:​grades.pdf|da12-grades}}
 +
 +===== Final =====
 +
 +{{:​education:​da12-final.pdf|Final exam}}
 +{{:​education:​da12-final_solution.pdf|Solution to the final exam}}
 +
 +----