Distributed Algorithms (CS-451)

Master course, Fall 2023

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

Moodle

The course page is 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.

Introduction: PDF
Reliable Broadcast: PDF
Causal Broadcast: PDF
Total Order Broadcast: PDF
Consensus: PDF
Consensus with Byzantine failures and asynchrony (by Pierre Civit): PDF
Terminating Reliable Broadcast: PDF
Distributed Systems Non-Blocking Atomic Commit: PDF
Group Membership and View Synchronous Communication: PDF
Byzantine-Robustness in Federated Learning (by Rafael Pinot & Nirupam Gupta): PDF
Proof-of-Work Blockchain Systems (by Matej Pavlovic): PDF
Old Algorithms for New Problems (by Adi Seredinschi) : PDF

• 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

Warning! Some of those videos might be outdated! Following them instead of the actual lectures is at your own risk.