Distributed Algorithms
Master course, Fall 2022
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 13:15 to 15:00 in room BCH2201.
- Exercise session: Held every Monday from 15:00 to 16:00 in room INF1.
- Project Q&A: Held every Tuesday from 08:15 to 11:00 in room CE2.
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. All course updates will be posted exclusively on Moodle.
News
- 18.09.2022. No sessions will be given in the first week.
Project
- It is about the implementation of broadcast algorithms,
- It accounts for 30% of the final grade,
- It is to be completed individually by each student,
- It consists of three deliverables, namely Perfect links, FIFO Broadcast, and a yet-to-be-announced deliverable. More details can be found in the repository of the project.
- For updates regarding the project, please use Moodle!
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
- 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
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, video | Logic101.pdf, Gossip.pdf, video | ||
Reliable Broadcast | Reliable Broadcast.pdf, video | Reliable Broadcast.pdf, video | ||
Causal Broadcast | Causal Broadcast.pdf, video | Causal Broadcast.pdf, video | ||
Total Order Broadcast | Total Order Broadcast.pdf, video | Total Order Broadcast.pdf, video | ||
Consensus | Consensus.pdf, video | Consensus.pdf, Consensus (part 2).pdf, video | ||
NBAC & TRB | NBAC.pdf, TRB.pdf, video | NBAC&TRB.pdf, video | ||
Group Membership & View Synchronous Communication | Group Membership&View Synchronous Communication.pdf, video | GM&VSC.pdf, video | ||
Shared Memory | Shared Memory.pdf, video | Shared Memory.pdf, video, | ||
Demystifying Bitcoin | Demystifying Bitcoin.pdf, video | No exercises yet | ||
Planetary Scale Systems | Planetary Scale Systems.pdf | No exercises yet | ||
Distributed Machine Learning | Distributed Machien Learning.pdf | No exercises yet | ||
Byzantine Fault Tolerance | No lecture slides yet | No exercises yet |
Invited lectures
Lecture | Slides | |
---|---|---|
Byzantine Fault Tolerance and Blockchains (By Dr. Marko Vukolić, IBM Research Zurich) | BFT-and-Blockchains.pptx, video | |
Building the Internet Computer: A glimpse into an ambitious adventure (by Yvonne-Anne Pignolet, DFINITY) | pdf, video | |
Beyond Blockchains (by Adi Seredinschi, Informal Systems) | pdf, video (start at 0:47:40) | |
Real-Time Distributed Algorithms (by David Kozhaya, ABB) | pptx | |
Architecture trade-offs in a planet-scale queueing system (by Manos Karpathiotakis, Facebook) | ||
Information on exercises, grading, and exam
- 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.