Distributed Algorithms

Master course, Fall 2020

Prerequisites: none.

Distributed algorithms are fundamental and ubiquitous in the modern computing landscape. In essence, these algorithms enable computing over several machines, in a local IP-like network, a cloud or in a P2P network. Failures are common and computations need to proceed despite partial failures of machines or communication links. This course will cover the foundations of reliable distributed computing with an emphasis on broadcast and agreement algorithms. The following video discusses the main topics investigated in the course.

Main topics of the course

Reliable channels, Failure detectors, Reliable broadcast, Causal broadcast, Total order broadcast, Consensus, Terminating reliable broadcast, Atomic commit, Virtual synchrony, Byzantine agreement, Blockchain, Distributed machine learning

Structure of the course

The course comprises of 3 parts:

• Theory lecture: Held by Prof. Rachid Guerraoui every Monday from 15:00 to 17:00 in room CM1.
• Exercise session: Held every Monday from 17:00 to 18:00 in rooms BC01/BC02/BC03.
• Project Q&A: Held every Tuesday from 08:00 to 11:00 in room PO01 Polydome.

You can watch the lectures, exercise sessions and Project Q&A on Zoom. To access the link, please login to Moodle.

Grading Please look at the section Information on exercises, grading, and exam

Moodle

A course page is also available on Moodle. We encourage students to register on Moodle, in order to get all the course announcements by email. Furthermore, students can use Moodle to ask questions about the exercise sessions and/or the project.

• 02/12: The final exam will take place on January 16 from 08:15am to 11:15am at CE1515.
• 12/10: Today's lecture by Professor Rachid Guerraoui will be given in person, as usual.
• 03/10: On Monday (05/10), lecture given by Professor Rachid Guerraoui will be given exclusively online (no in-person lecture session).
• 02/10: Project deadlines are announced: FIFO broadcast should be delivered by Nov. 13th, LCausal broadcast should be delivered by Dec. 11th, and the final oral exam will be held on Dec. 15th.
• 21/09: There is a project session tomorrow (22/09) at 8am in PO01. The first theory exercise session will take place on next Monday (28/09) at 5pm.
• 10/09: There is no exercise session (14/09) in the first week. However, project presentation will take place on Tuesday (15/09) at 8am in PO01.
• 02/09: DA 2020 page is online.

• It is about the implementation of broadcast algorithms,
• It accounts for 30% of the final grade,
• It is to be completed individualy by each student,
• It consists of two deliverables, namely FIFO Broadcast and Localized Causal Broadcast. More details can be found in the repository of the project.
• Deadlines: Nov. 13th (FIFO Broadcast), Dec. 11th (Localized Causal Broadcast), Dec. 15th (Oral exam).
• Late submission policy: a late submission will lose 25% of the final grade per day. For example, a 2-day late submission will lose 50% of the final grade and 4 (or more)-day late submissions are not accepted.
• Project submission instructions (please respect the format below; otherwise your submission will be ignored!): Submit only once (avoid test or junk submissions) a single ​.zip​ archive. ​The archive should contain a single root directory, which should have the contents of `template_java` or `template_cpp` (as they were provided in the latest commit of the github repository), along with your source-code contribution. The name of the root directory should be your SCIPER number. For example, a student with SCIPER 12345 should submit the archive 12345.zip​ containing a single directory 12345/​. ​(Reminder: Make sure you zip the project after running cleanup.sh, in order to avoid including build artifacts inside the zip.)
• Please submit here phase 1 of the project by Nov. 13th, 2020.

• Lecturers:
  • Prof. Rachid Guerraoui, Office INR 310, web page
• Teaching Assistants:
  • Theory & exercises:
    • Matteo Monti, Office INR 210, Email: matteo.monti@epfl.ch
    • Jovan Komatovic, Office INR 314, Email: jovan.komatovic@epfl.ch
  • Project:
    • Arsany Guirguis, Office INR 313, Email: arsany.guirguis@epfl.ch (office hours: Wednesdays 11h to 12h)
    • Athanasios Xygkis, Office INR 314, Email: athanasios.xygkis@epfl.ch (office hours: Tuesdays 14h to 15h)

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

• Your final grade is a combination of the final (written) theoretical exam and the project:
  • The theoretical exam accounts for 70% of the final grade,
  • The project accounts for 30% of the final grade.

• The final exam is closed book: no materials are allowed.

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