Differences

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

Link to this comparison view

education:da_2014 [2015/08/17 14:54]
 education:da_2014 [2015/08/17 14:54] (current)
Line 1: Line 1:
 +====== Distributed Algorithms ======
  
 +**Master course, Fall 2014**
 +
 +**Prerequisites:​ none.**
 +
 +**Note: this course is independent from the course Concurrent Algorithms.**
 +
 +----
 +
 +===== News =====
 +
 +** Last updated: February 20, 2015, 10:05 **
 +
 +  * Published grade distributions and project winners.
 +  * Added {{:​education:​da14_final.pdf|final exam}} for download.
 +  * Added information on the final exam and on the Q&A session.
 +  * Added {{:​education:​da12_final.pdf|final exam from 2012}} with {{:​education:​da12_final_sol.pdf|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 {{:​education:​da14_midterm_grades_new.pdf|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)
 +  * {{:​education:​da14_midterm.pdf|Solution to midterm 2014}} available.
 +  * Short video lecture: [[http://​wandida.com/​en/​archives/​1743|Consensus in an unreliable network of processors]]
 +  * Published ​ {{:​education:​da14_midterm_grades_new.pdf|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.
 +
 +----
 +
 +
 +===== 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.
 +  * 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
 +
 +----
 +
 +===== Q&A Session =====
 +
 +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.
 +
 +----
 +
 +===== Final exam =====
 +
 + ** 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 **
 +
 + ​{{:​education:​da14_exam_grade_distribution.png|Exam grade distribution}}
 + ​{{:​education:​da14_final_grade_distribution.png|Final grade distribution}}
 +
 +----
 +
 +===== Bonus project =====
 +
 +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 {{:​education:​da14_project.pdf|Project description}}.
 +
 + ** Downloads **
 +
 + ​{{:​education:​da14_project.pdf|Project description}}
 +
 + ​{{:​education:​da14_project_template.tar.gz|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|matej.pavlovic@epfl.ch]] <​del>​before the start of the Christmas break</​del>​ 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
 +
 +----
 +
 +===== Midterm =====
 + 
 + ** 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: {{:​education:​da14_midterm_grades.pdf|2014 midterm grades}}.
 +
 + The distribution of grades is the following (only people who did not show up received 0 points):
 + ​{{:​education:​da14_midterm_grades.png|2014 grade distribution}}
 +
 +----
 +
 +===== Teaching team =====
 +
 +  * **Lecturers:​** ​
 +                  * Prof. Rachid Guerraoui, office INR 310, [[http://​lpd.epfl.ch/​rachid|web page]]
 +  * **Teaching Assistants:​** ​
 +                 * Cheng Wang, office INR 313, [[http://​people.epfl.ch/​cheng.wang|web page]], office hours: Wednesdays 10:00 - 11:00 or any time by appointment
 +                 * Matthaios Olma, office BC 240, [[http://​people.epfl.ch/​matthaios.olma|web page]], office hours: Thursday 10:00 - 11:00 or any time by appointment
 +                 * Matej Pavlovic, office INR 314, [[http://​people.epfl.ch/​matej.pavlovic|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 [[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}})
 +
 +  * Short video lecture: [[http://​wandida.com/​en/​archives/​1743|Consensus in an unreliable network of processors]]
 +
 +----
 +
 +
 +
 +===== 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 ​             | {{:​education:​da14-introduction.pdf|pdf}} (new) | {{:​education:​da14_ex01.pdf|ex01}} {{:​education:​da14_sol01.pdf|sol01}} |
 +| Introduction / Reliable broadcast ​       | {{:​education:​da14-reliableBroadcast.pdf|pdf}} (new) | {{:​education:​da14_ex02.pdf|ex02}} {{:​education:​da14_sol02.pdf|sol02}} |
 +| Reliable broadcast ​         |  |  |
 +| Causal Broadcast ​         | {{:​education:​da14-causalbroadcast.pdf|pdf}} (new) | {{:​education:​da14_ex03.pdf|ex03}} (new) {{:​education:​da14_sol03.pdf|sol03}} |
 +| Total Order Broadcast ​         | {{:​education:​da14-totalorderbroadcast.pdf|pdf}} (new) | {{:​education:​da14_ex04.pdf|ex04}} {{:​education:​da14_sol04.pdf|sol04}} |
 +| Consensus | {{:​education:​da12-consensus.pdf|pdf}} | {{:​education:​da14_ex05.pdf|ex05}} {{:​education:​da14_sol05.pdf|sol05}} |
 +| Non-Blocking Atomic Commit | {{:​education:​da14-NBAC-1.pdf|pdf}} (new) | {{:​education:​da14_ex06.pdf|ex06}} (new) {{:​education:​da14_sol06.pdf|sol06}} |
 +| Group Membership, View Synchrony\\ Terminating Reliable Broadcast | {{:​education:​da14-GroupMembershipVSC.pdf|pdf}} (new) \\ {{:​education:​da14-TerminatingReliableBroadcast.pdf|pdf}} (new) | {{:​education:​da14_ex07.pdf|ex07}} {{:​education:​da14_sol07.pdf|sol07}} |
 +| Shared Memory (regular registers) ​     | {{:​education:​da12-sharedmemory1.pdf|pdf#​1}} \\ {{:​education:​da12-sharedmemory2.pdf|pdf#​2}} | {{:​education:​da14_ex08.pdf|ex08}} {{:​education:​da14_sol08_1.pdf|sol08_1}} {{:​education:​da14_sol08_2.pdf|sol08_2}} |
 +| Shared Memory (atomic registers) | {{:​education:​da12-sharedmemory3.pdf|pdf#​3}} \\ {{:​education:​da12-sharedmemory4.pdf|pdf#​4}} | {{:​education:​da14_ex09.pdf|ex09}} {{:​education:​da14_sol09.pdf|sol09}} |
 +| Byzantine fault tolerance | {{:​education:​da14-ByzantineGenerals.pdf|pdf#​1}} \\ {{:​education:​da14-PBFT.pdf|pdf#​2}} | |
 +| Self-stabilization (intro) | {{:​education:​self_stabilization_01.pdf|pdf}} | {{:​education:​da14_ex10.pdf|ex10}} {{:​education:​da14_sol10.pdf|sol10}}|
 +| Self-stabilization (spanning tree) | {{:​education:​self_stabilization_02.pdf|pdf}} | {{:​education:​ex11.pdf|ex11}} {{:​education:​ex11_corr.pdf|sol11}}|
 +| Population protocols | {{:​education:​da14-pop.pdf|pdf}} |  |
 +| Population protocols (Presburger) | {{:​education:​pp_presburger.pdf|pdf}} | {{:​education:​ex12.pdf|ex12}} {{:​education:​sol12_bis.pdf|sol12 (question 3 corrected)}}|
 +|Midterm ​  | | {{:​education:​da12_midterm.pdf|midterm 2012}} {{:​education:​da14_midterm.pdf|midterm 2014}} |
 +|Final exam | | {{:​education:​da12_final.pdf|da12_final}} {{:​education:​da12_final_sol.pdf|da12_final_solution}} \\ {{:​education:​da14_final.pdf|da14_final}}|
 +
 +----
 +
 +=====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 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.
 +
 +----