Distributed Computing Laboratory DCL

Distributed Algorithms

Master course, Fall 2018

Prerequisites: none.

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


News

  • Added slides and exercices for Monday 15th.
  • Added information on the testing machine.
  • Updated project files (at least one update will follow soon).
  • Added solutions to the exercices on Reliable Broadcast.
  • Added the slides for the lecture and exercises of October 1st (Basics). Added the slides for the lecture of October 8th (Reliable broadcast).
  • Published project submision deadlines (see “Dates and schedule”)
  • Uploaded solutions to the Logic 101 exercices.
  • Uploaded project description (v1) and basic template.
  • Updated the slides (introduction) for the class on Monday 24/09.
  • Tuesday, September 18th is the first project consultation. This will be an introductory session with practical information, but no effective work on the project will be done.
  • DA 2018 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, 8h-11h in PO01 Polydomes.
  • Partial project submission deadline (until FIFO Broadcast): Tuesday, November 6th 2018
  • Full project submission deadline: Tuesday, December 16th 2018

Endterm

  • Final exam date: TBD

Project

  • Project description: da18_project_v2.pdf
  • Template: Template files
  • Test machine:
    • Your code will be tested this (or equivalent) machine. It is your responsability to make it work there. Additional software (build tools or libraries) might be installed on request (no guarantees on this, however).
    • Accessible over SSH.
    • IP address: 52.212.14.105
    • User name: da-user (Shared among everybody, create your own working folder and don't mess with other teams' files. Each team can have a separate user account too. Write an email to matej.pavlovic@epfl.ch if you want one.)
    • Password: Announced during the project session. Write an email if you missed it.
    • To login, run the following command in the shell: ssh da-user@52.212.14.105
  • FAQ:
    • Can we use multi-threading? Yes. However, only spawn threads (don't spawn child processes) from your process.
    • You can assume that a majority of processes are correct (e.g., we will not crash more than 2 out of 5 processes)
    • Code resemblance will not be tolerated for both ends. Please keep your code private.

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 logic101.pdf
Logic101Solution.pdf
Basics proofs18.pdf
Reliable Broadcast rb.pdf ex02.pdf sol02.pdf
Causal Broadcast cb.pdf ex03.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.