227-0558-00L Principles of Distributed Computing
Semester | Frühjahrssemester 2021 |
Dozierende | R. Wattenhofer, M. Ghaffari |
Periodizität | jährlich wiederkehrende Veranstaltung |
Lehrsprache | Englisch |
Lehrveranstaltungen
Nummer | Titel | Umfang | Dozierende | |||||||
---|---|---|---|---|---|---|---|---|---|---|
227-0558-00 V | Principles of Distributed Computing | 2 Std. |
| R. Wattenhofer, M. Ghaffari | ||||||
227-0558-00 U | Principles of Distributed Computing In Gruppen | 2 Std. |
| R. Wattenhofer, M. Ghaffari | ||||||
227-0558-00 A | Principles of Distributed Computing No presence required. Creative task outside the regular weekly exercises. | 2 Std. | R. Wattenhofer, M. Ghaffari |
Katalogdaten
Kurzbeschreibung | We study the fundamental issues underlying the design of distributed systems: communication, coordination, fault-tolerance, locality, parallelism, self-organization, symmetry breaking, synchronization, uncertainty. We explore essential algorithmic ideas and lower bound techniques. |
Lernziel | Distributed computing is essential in modern computing and communications systems. Examples are on the one hand large-scale networks such as the Internet, and on the other hand multiprocessors such as your new multi-core laptop. This course introduces the principles of distributed computing, emphasizing the fundamental issues underlying the design of distributed systems and networks: communication, coordination, fault-tolerance, locality, parallelism, self-organization, symmetry breaking, synchronization, uncertainty. We explore essential algorithmic ideas and lower bound techniques, basically the "pearls" of distributed computing. We will cover a fresh topic every week. |
Inhalt | Distributed computing models and paradigms, e.g. message passing, shared memory, synchronous vs. asynchronous systems, time and message complexity, peer-to-peer systems, small-world networks, social networks, sorting networks, wireless communication, and self-organizing systems. Distributed algorithms, e.g. leader election, coloring, covering, packing, decomposition, spanning trees, mutual exclusion, store and collect, arrow, ivy, synchronizers, diameter, all-pairs-shortest-path, wake-up, and lower bounds |
Skript | Available. Our course script is used at dozens of other universities around the world. |
Literatur | Lecture Notes By Roger Wattenhofer. These lecture notes are taught at about a dozen different universities through the world. Distributed Computing: Fundamentals, Simulations and Advanced Topics Hagit Attiya, Jennifer Welch. McGraw-Hill Publishing, 1998, ISBN 0-07-709352 6 Introduction to Algorithms Thomas Cormen, Charles Leiserson, Ronald Rivest. The MIT Press, 1998, ISBN 0-262-53091-0 oder 0-262-03141-8 Disseminatin of Information in Communication Networks Juraj Hromkovic, Ralf Klasing, Andrzej Pelc, Peter Ruzicka, Walter Unger. Springer-Verlag, Berlin Heidelberg, 2005, ISBN 3-540-00846-2 Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes Frank Thomson Leighton. Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991, ISBN 1-55860-117-1 Distributed Computing: A Locality-Sensitive Approach David Peleg. Society for Industrial and Applied Mathematics (SIAM), 2000, ISBN 0-89871-464-8 |
Voraussetzungen / Besonderes | Course pre-requisites: Interest in algorithmic problems. (No particular course needed.) |
Leistungskontrolle
Information zur Leistungskontrolle (gültig bis die Lerneinheit neu gelesen wird) | |
Leistungskontrolle als Semesterkurs | |
ECTS Kreditpunkte | 7 KP |
Prüfende | R. Wattenhofer, M. Ghaffari |
Form | Sessionsprüfung |
Prüfungssprache | Englisch |
Repetition | Die Leistungskontrolle wird in jeder Session angeboten. Die Repetition ist ohne erneute Belegung der Lerneinheit möglich. |
Prüfungsmodus | schriftlich 180 Minuten |
Zusatzinformation zum Prüfungsmodus | We will have two graded homework assignments (compulsory continuous performance assessment). Each graded homework assignment will account for 10% of the final grade, the main exam will be 80% of the final grade. Missing the submission deadline for a homework assignment will result in grade of 1 for that assignment. |
Hilfsmittel schriftlich | All written documents (scripts, own notes, exercises, books, etc...) are allowed. All electronic devices (own calculator, mobile phone, laptop, etc...) are NOT allowed! |
Diese Angaben können noch zu Semesterbeginn aktualisiert werden; verbindlich sind die Angaben auf dem Prüfungsplan. |
Lernmaterialien
Hauptlink | Information |
Es werden nur die öffentlichen Lernmaterialien aufgeführt. |
Gruppen
Keine Informationen zu Gruppen vorhanden. |
Einschränkungen
Keine zusätzlichen Belegungseinschränkungen vorhanden. |