Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Previous revision
education:da_2023 [2019/01/22 20:41]
education:da_2023 [2023/12/04 10:15] (current)
fablpd
Line 1: Line 1:
 +====== Distributed Algorithms ======
 +
 +**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 [[https://​www.youtube.com/​watch?​v=38cCqfz7KiI&​ab_channel=ZettaBytes%2CEPFL|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 [[https://​moodle.epfl.ch/​course/​view.php?​id=14333|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.
 +
 +
 +===== Textbook =====
 +
 +  * **Rachid Guerraoui and Luis Rodrigues** - //​Introduction to Reliable Distributed Programming//,​ available at 'La Fontaine'​ (with a student discount) or at [[http://​www.amazon.de/​Introduction-to-Reliable-Distributed-Programming/​dp/​3540288457/​ref=sr_1_1?​ie=UTF8&​s=books-intl-de&​qid=1220959274&​sr=8-1|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. ({{:​education:​protocol-language.odt|odt}} ​ {{:​education:​protocol-language.pdf|pdf}})
 +  * A Latex sample for algorithm implementation can be found here: [[https://​gist.github.com/​adizere/​bf7423045e05aa53c4f3|alg-sample.tex]]
 +
 +
 +----
 +
 +===== Previous year recordings (2020) =====
 +
 +**Warning! Some of those videos might be outdated! Following them instead of the actual lectures is at your own risk.**
 +
 +^ Lecture^  ^ Slides^  ^ Exercises ^
 +| Introduction | | {{:​education:​da21-introduction.pdf|Intro.pdf}},​ [[https://​tube.switch.ch/​videos/​01c1a2e5|video]] | |  {{:​education:​intro_da21.pdf|Logic101.pdf}},​ {{:​education:​gossip_da21.pdf|Gossip.pdf}},​ [[https://​tube.switch.ch/​videos/​d82a7150|video]] ​ |
 +| Reliable Broadcast | | {{:​education:​da21-reliablebroadcast.pdf|Reliable Broadcast.pdf}},​ [[https://​tube.switch.ch/​videos/​a08cc3b1|video]] ​ | | {{:​education:​reliable_broadcast_da21.pdf|Reliable Broadcast.pdf}},​ [[https://​tube.switch.ch/​videos/​838b82a0|video]] |
 +| Causal Broadcast | | {{:​education:​da20-causalbroadcast.pdf|Causal Broadcast.pdf}},​ [[https://​tube.switch.ch/​videos/​a4e1f62b|video]] | | {{:​education:​reliable_broadcast_da21.pdf|Causal Broadcast.pdf}},​ [[https://​tube.switch.ch/​videos/​838b82a0|video]] |
 +| Total Order Broadcast | | {{:​education:​da20-totalorderbroadcast.pdf|Total Order Broadcast.pdf}},​ [[https://​tube.switch.ch/​videos/​2b9b6fef|video]] | | {{:​education:​da20-exercise-totalorder.pdf|Total Order Broadcast.pdf}},​ [[https://​tube.switch.ch/​videos/​a31fc8ba|video]] |
 +| Consensus | | {{:​education:​consensus_da21.pdf|Consensus.pdf}},​ [[https://​tube.switch.ch/​videos/​c8551119|video]] | | {{:​education:​ consensus_20_exercises.pdf |Consensus.pdf}},​ {{:​education:​consensus_part_2_.pdf|Consensus (part 2).pdf}}, [[https://​tube.switch.ch/​videos/​e7101d7d|video]]|
 +| NBAC & TRB | | {{:​education:​da21-nbac.pdf|NBAC.pdf}},​ {{:​education:​da21-trb.pdf|TRB.pdf}},​ [[https://​tube.switch.ch/​videos/​7648c781|video]] | | {{education:​nbactrb.pdf|NBAC&​TRB.pdf}},​ [[https://​tube.switch.ch/​videos/​09f80a39|video]] |
 +| Group Membership & View Synchronous Communication | | {{:​education:​da20-groupmembershipvsc.pdf |Group Membership&​View Synchronous Communication.pdf}},​ [[https://​tube.switch.ch/​videos/​8d3cc2cb|video]]| | {{education:​gm_vsc.pdf|GM&​VSC.pdf}},​ [[https://​tube.switch.ch/​videos/​6833ee9b|video]] |
 +| Shared Memory | | {{:​education:​da20-sharedmemory.pdf |Shared Memory.pdf}},​ [[https://​tube.switch.ch/​videos/​96a6abae|video]] | | {{education:​shared_memory.pdf|Shared Memory.pdf}},​ [[https://​tube.switch.ch/​videos/​52da4fff|video]],​ |
 +| Demystifying Bitcoin | | {{:​education:​bitcoin2020.pdf |Demystifying Bitcoin.pdf}},​ [[https://​tube.switch.ch/​videos/​c351fde9|video]] | | //No exercises yet// |
 +| Planetary Scale Systems | | {{:​education:​matteo.pdf |Planetary Scale Systems.pdf}} | | //No exercises yet// |
 +| Distributed Machine Learning | | {{:​education:​le.pdf |Distributed Machien Learning.pdf}}| | //No exercises yet// |
 +| Byzantine Fault Tolerance | | //No lecture slides yet// | | //No exercises yet// |
 +
 +
 +===== Invited lectures (2020) =====
 +
 +^ Lecture ​  ​^ ​  ​Slides ​  ​^ ​
 +|Byzantine Fault Tolerance and Blockchains (By Dr. Marko Vukolić, IBM Research Zurich) | {{ :​education:​lecture_-_epfl_-_nov_16_2020.pptx |BFT-and-Blockchains.pptx}}, ​ [[https://​tube.switch.ch/​videos/​9fc77c55|video]]| |
 +|Building the Internet Computer: A glimpse into an ambitious adventure (by Yvonne-Anne Pignolet, DFINITY) | {{:​education:​Pignolet_Guest-Lecture_2020-11-23.pdf| pdf}}, [[https://​tube.switch.ch/​videos/​411d8ec8|video]]| |
 +|Beyond Blockchains (by Adi Seredinschi,​ Informal Systems) | {{:​education:​seredinschi_guest-lecture_2020-11-23.pdf| pdf}}, [[https://​tube.switch.ch/​videos/​411d8ec8|video (start at 0:47:40)]]| |
 +|Real-Time Distributed Algorithms (by David Kozhaya, ABB) | {{:​education:​david.pptx| pptx}}| ​
 +|Architecture trade-offs in a planet-scale queueing system (by Manos Karpathiotakis,​ Facebook) | {{:​education:​manos.pdf| pdf}}|
 +|
 +