Distributed Algorithms

Master course, Fall 2019

Prerequisites: none.

Note: this class includes a project which accounts for 40% of the final grade.

News

  • 29/10: Project submission instructions are online.
  • 16/10: The date for the midterm exam is set to December 2nd 2019.
  • 01/10: Registered teams are here. If you have any complaints/comments, or you missed the deadline of registration, please contact us by email.
  • 23/09: Project description is online.
  • 02/09: There is no session in on the first Tuesday of the semester (September 17th 2019)
  • 02/09: DA 2019 page is online.

Dates and schedule

  • The course is given on Mondays, 15h-17h in CM1.
  • The exercise session are given on Mondays, 17h-18h BC01, BC2, BC3.
  • We present and discuss practical aspects for the projects on Tuesdays, 8:15h-11h in PO01 Polydome.
  • The midterm exam will take place on December 2nd 2019.
  • The final exam will take place on January 17th 2020.

Project

  • Team registration: Project should be done in teams of 2 or 3. Registered teams and their IDs are here. If you have any complaints/comments, or you missed the deadline of registration, please contact us by email.
  • Project description:​ da19_project.pdf
  • Template: ​ Template files
  • Code testing:
    • Your code must compile and run in this VM (exactly this one, not a similar one); you can import with Virtualbox >= 5.0.
    • Please do not modify this VM (e.g., change Java version, install a package with sudo) as your code will compile in the VM but will fail to compile in our test machine and thus your submission will be invalid.
    • This VM is meant for you to test whether your code compiles and runs. It is not meant for development or performance tests.
    • VM password: epflda
  • Project submission:
    • Instructions (please respect the format below, otherwise your submission will be ignored!):
      • Identify yourself in the submission form using the name of one of your team members.
      • Submit only once (avoid test or junk submissions) a single ​.zip​ archive. ​
      • The archive should contain a single root directory. Your Makefile and all your source code must be inside the root directory. The name of the root directory should be your team ID.
      • For example, team with ID 31 should submit the archive ​31.zip​ containing a single directory ​31/​ and should identify themselves in the submission form as “​Arsany Guirguis”​. ​
    • 1st submission (FIFO broadcast):
    • 2nd submission (LCausal broadcast): 13/12 @ 23:59
    • Project oral exam: 17/12 @ 08:00 – 13:00
  • Project evaluation:
    • Code resemblance will not be tolerated for both ends. Please keep your code private.
    • The project evaluation consists of three parts: (1) correctness, (2) performance tests, and (3) a discussion with the whole team about your code, the challenges and issues faced, etc.
    • The whole project counts as 40% of your final grade. The first submission (FIFO) is 40% of the total grade of your project, while the second submission (LCausal) is 60% of the project grade.
    • Deadline extension with a penalty of 25% for every 24 hours of delay. For instance, if you submit after midnight 08/11/2019 but before midnight 09/11/2019, you will lose 25% of the grade for this submission. After midnight 11/11/2019, we don't consider submissions for this part anymore. The same goes for the second submission.
  • FAQ:
    • Can we use multi-threading?​ Yes. However, only spawn threads (don't spawn child ​processes​) from your process.
    • How many processes can crash during tests? You can assume that a majority of processes are correct (e.g., we will not crash more than 2 out of 5 processes)
    • Should we build FIFO broadcast on top of RB or URB? It has to be on top of URB. The same goes for Localized Causal Broadcast.
    • How do we handle signals in Java? This could be helpful.

Teaching team

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

  • We prepared a document describing the language used for module specification and implementation, the notion of layering, and the notion of process. (odt pdf)
  • A Latex sample for algorithm implementation can be found here: alg-sample.tex

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 Logic101Solutions.pdf
Reliable Broadcast ReliableBroadcast.pdf GraphsSolutions.pdf
Causal Broadcast CausalBroadcast.pdf ReliableAndCausalBroadcastSolutions.pdf
Total Order Broadcast TO-Broadcast.pdf TO-BroadcastAndConsensusSolutions.pdf
Consensus Consensus.pdf ConsensusSolutions.pdf ConsensusExtraSolutions.pdf
Bitcoin Bitcoin.pdf
NBAC & TRB nbac.pdf trb.pdf NBAC-TRB-Exercises.pdf
Group Membership & View Synchronous Communication GM, VSC
Shared Memory Shared Memory
Byzantine Fault Tolerance Notes from Alexandre Maurer
Distributed Machine Learning dml.pdf
---------------------------------------------------------------------------------------------------------

Invited lectures

Lecture Slides
Blockchain blockchain.pptx
Tendermint tendermint.pdf
----------------------------------------------------------------------

Information on exercises, grading, and exam

  • Usually, 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.
  • The final exam is closed book: no materials are allowed.