Mohsen Ghaffari: Katalogdaten im Frühjahrssemester 2021 |
| Name | Herr Dr. Mohsen Ghaffari |
| Lehrgebiet | Informatik |
| URL | https://people.inf.ethz.ch/gmohsen/ |
| Departement | Informatik |
| Beziehung | Assistenzprofessor (Tenure Track) |
| Nummer | Titel | ECTS | Umfang | Dozierende | |
|---|---|---|---|---|---|
| 227-0558-00L | Principles of Distributed Computing  | 7 KP | 2V + 2U + 2A | R. Wattenhofer, M. Ghaffari | |
| 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.) | ||||
| 252-4202-00L | Seminar in Theoretical Computer Science | 2 KP | 2S | E. Welzl, B. Gärtner, M. Ghaffari, M. Hoffmann, J. Lengler, D. Steurer, B. Sudakov | |
| Kurzbeschreibung | Presentation of recent publications in theoretical computer science, including results by diploma, masters and doctoral candidates. | ||||
| Lernziel | To get an overview of current research in the areas covered by the involved research groups. To present results from the literature. | ||||
| Voraussetzungen / Besonderes | This seminar takes place as part of the joint research seminar of several theory groups. Intended participation is for students with excellent performance only. Formal restriction is: prior successful participation in a master level seminar in theoretical computer science. | ||||
| 252-4225-00L | Presenting Theoretical Computer Science  Number of participants limited to 24. The deadline for deregistering expires at the end of the second week of the semester. Students who are still registered after that date, but do not attend the seminar, will officially fail the seminar. | 2 KP | 2S | B. Gärtner, M. Ghaffari, R. Kyng, D. Steurer, E. Welzl | |
| Kurzbeschreibung | Students present current or classical results from theoretical computer science. | ||||
| Lernziel | Students learn to read, understand and present results from theoretical computer science. The main focus and deliverable is a good presentation of 45 minutes that can easily be followed and understood by the audience. | ||||
| Inhalt | Students present current or classical results from theoretical computer science. | ||||
| Voraussetzungen / Besonderes | The seminar takes place as a block seminar on two Saturdays in April and/or May. Each presentation is jointly prepared and given by two students (procedure according to the seminar's Moodle page). All students must attend all presentations. Participation requires successful completion of the first year, or instructor approval. | ||||
| 263-4505-00L | Algorithms for Large-Scale Graph Processing Number of participants limited to 12. The deadline for deregistering expires at the end of the second week of the semester. Students who are still registered after that date, but do not attend the seminar, will officially fail the seminar. | 2 KP | 2S | M. Ghaffari | |
| Kurzbeschreibung | This is a theory seminar, where we present and discuss recent algorithmic developments for processing large-scale graphs. In particular, we focus on Massively Parallel Computation (MPC) algorithms. MPC is a clean and general theoretical framework that captures the essential aspects of computational problems in large-scale processing settings such as MapReduce, Hadoop, Spark, Dryad, etc. | ||||
| Lernziel | This seminar familiarizes students with foundational aspects of large-scale graph processing, and especially the related algorithmic tools and techniques. In particular, we discuss recent developments in the area of Massively Parallel Computation. This is a mathematical abstraction of practical large-scale processing settings such as MapReduce, and it has been receiving significant attention over the past few years. The seminar assumes no particular familiarity with parallel computation. However, we expect that all the students are comfortable with basics of algorithms design and analysis, as well as probability theory. In the course of the seminar, the students learn how to structure a scientific presentation (in English) which covers the key ideas of a paper, while omitting the less significant details. | ||||
| Inhalt | The seminar will cover a number of the recent papers on Massively Parallel Computation. As mentioned above, no familiarity with parallel computation is needed and all the relevant background information will be explain by the instructor in the first lecture. | ||||
| Literatur | The papers will be presented in the first session of the seminar. | ||||
| Voraussetzungen / Besonderes | Prerequisite: Having passed at least one master's level course in theoretical computer science (ideally Advanced Algorithms and/or Randomized Algorithms). | ||||