Distributed Algorithms

Master course, Fall 2019

Prerequisites: none.

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

• 01/12: Clarification: The midterm exam will take place tomorrow (02/12), 15:15-17:00 in the usual lecture hall (CM1). The exam will be closed books (no materials are allowed). The exam will not be graded.
• 27/11: Project oral exam registration is online.
• 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.

• 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.

• 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):
    • Deadline: 8/11 @ 23:59
    • Submission link
  • 2nd submission (LCausal broadcast):
    • Deadline: 13/12 @ 23:59
    • Submission link
  • Project oral exam:
    • Date: 17/12 @ 08:00 – 13:00
    • Location: PO01 Polydome
    • Please choose the time that suits you by putting your team ID in the preferred slot in this spreadsheet. Please do not change any filled slot; only fill empty slots.
• 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.
  • Register year team for the oral exam (which will be held on December 17th, 2019) here.
• 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.

• Lecturers:
  • Prof. Rachid Guerraoui, office INR 310, web page
• Teaching Assistants:
  • Theory & exercises:
    • Matteo Monti matteo.monti@epfl.ch, INR 312 Thursday 4pm-5pm
    • Athanasios Xygkis athanasios.xygkis@epfl.ch, INR 314 Wednesday 4pm-5pm
  • Project:
    • Arsany Guirguis arsany.guirguis@epfl.ch, INR 313 Monday 3pm-4pm
    • Georgios Damaskinos georgios.damaskinos@epfl.ch, INR 313 Wednesday 3pm-4pm
    • El Abridi Ali ali.elabridi@epfl.ch

• 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

• 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

• 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
• ''Everything You Always Wanted to Know About the PhD But Were Afraid to Ask''

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

• 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.