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

  • 10/12: Important: today there will be no exercise session! We have graded your midterms. In case you want to look at your midterm, contact one of the teaching assistants.
  • 05/12: Added notes from Alex's class concerning Byzantine failures.
  • 26/11: Updated Section 1 in the project description to state clearly that we only grade the two submissions of FIFO and Localized Causal Broadcast.
  • 15/11: Important: Each team should register for the projects evaluation session. Please read: Project Evaluation.
    • Added slides for the Shared Memory class of Monday 19th of November
  • 14/11: The project description PDF has been updated. Please download the new one (link below). Main change: The output format for localized causal broadcast stays the same.
  • 07/11: The test machine is meant for you to test whether you code compiles and runs there (libraries / dependencies / etc…). It is not meant for development or performance tests. To avoid overloading the machine with orphan processes left by some students, if a process runs for more than 2 minutes, it will be killed.
  • 06/11: Deadline extension with a penalty of 25% for every 24 hours of delay. For instance, if you submit after midnight 06/11/2018 but before midnight 07/11/2018, you will lose 25% of the grade for this submission. After midnight 09/11/2018, we don't consider submissions for this application anymore.
  • 06/11: Updated templates to fix RTNETLINK issues (the same files can be downloaded from here: Template files).
  • 06/11: additional office hours announced for theory TAs.
  • 05/11: added exercice for NBAC, note that we will use this session to address recurring questions on previous exercices.
  • 31/10: We have updated on the test scripts inside ~/project_template on the test machine to fix some minor bugs. You can download the new version here too: Template files
  • 30/10: We have uploaded on the test machine inside ~/project_template some sample scripts showing how we expect to compile and test your code (the same files can be downloaded from here: Template files). Note that we don't provide a Makefile for Java implementations.
    • Submission are described here.
    • Also, please read the FAQ carefully!
  • Added slides for the class on NBAC and TRB (Monday, November 5th)
  • Solutions to exercices on consensus are posted.
  • 29/10 Uploaded a new project description (v3), specifying that FIFO broadcast should build on top of URB, and that only 1-hop dependencies need to be logged for the Localized Causal Broadcast application.
  • Added slides for Consensus lecture (Monday, October 29th).
  • Exam date (set by Service Académique of EPFL): 23.01 Wednesday 16h15 - 19h15 INM 202 SG1
  • Added slides and exercices for Monday 22th.
  • 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: Sunday, December 16th 2018
  • Final Exam: 23.01 Wednesday 16h15 - 19h15 INM 202 SG1

Endterm

  • Final exam date: TBD

Project

  • Project description: da18_project_v4.pdf
  • Template: Template files
  • Test machine:
    • Your code will be tested this (or equivalent) machine. It is your responsibility 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
    • This machine is meant for you to test whether you code compiles and runs there. It is not meant for development or performance tests. To avoid overloading the machine with orphan processes left by some students, if a process runs for more than 2 minutes, it will be killed.
  • 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.
    • 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 much does each submission count? The whole project counts as 40% of your final grade. The first application (FIFO) is 40% of the total grade of your project, while the second submission (Localized Causal) is 60% of the project grade.

Project submissions

  • Use the following link to submit your first (FIFO broadcast) application before the deadline (November 6th before midnight): Submission website
    • Please identify yourself in the submission form using the name of one of your team members.
  • Guidelines: please respect the format below, otherwise your submission will be ignored!
    • Submit only once (avoid test or junk submissions) a single .zip archive.
    • The name of the archive should correspond to your team ID that you can findhere. If your name is not in that document, you should register your team by mail to matej.pavlovic@epfl.ch.
    • The archive should contain a single directory. All your source code – including the Makefile – should be inside that directory. The name of the directory should correspond to 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”.
    • For validating your submission, we will upload your submitted directory to the test machine (52.212.14.105) and only run the original (i.e., modifications are prohibited) test_correctness.sh (or test_correctness_java.sh). These scripts execute make to obtain the executable da_proc (or Da_proc.class). Any submissions that fail to pass the test_correctness.sh will be completely ignored!
  • Please respect the others. Don't develop on the testing machine; only use it for verifying that the script runs properly (i.e., input and output is correct). Monitor the resources your tests require and make sure you don't forget any running processes.

Project Evaluation

  • The project evaluation consists of two parts:
    • correctness and performance tests for your two projects
    • an informal discussion with the whole team about your code, the challenges and issues faced, etc.
  • Room & date: DIA 004, 20th of December 2018
  • Please register your team (by writing simply the team ID) in one of the unoccupied slots from this document
    • Note that each slot is 15 minutes
    • The whole team should try to arrive in the room DIA 004 at least 5 minutes before your chosen time slot. If you arrive late or miss your slot you will be reassigned to the closest free slot.
  • Best of luck!

Teaching team

  • Lecturers:
    • Prof. Rachid Guerraoui, office INR 310, web page
  • Teaching Assistants:
    • Marjan Shahpaski marjan.shahpaski@epfl.ch, office BC 316, web page, office hours: Wednesdays 10:00 - 11:00 or any time by appointment
    • El Mahdi EL MHAMDI elmahdi.elmhamdi@epfl.ch, office INR 315 (not INR 211 as in epfl directory), web page, office hours: Wednesdays 11:00 - 12:00 and Friday 16:00 - 18:00, please come directly to office hours as much as possible, it is way simpler for us than to answer individual emails. Send an email when none of the slots is possible for you.
  • Project assistants:

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.

—-

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.