Mohsen Ghaffari: Katalogdaten im Frühjahrssemester 2021

NameHerr Dr. Mohsen Ghaffari
LehrgebietInformatik
E-Mailghaffari@inf.ethz.ch
URLhttps://people.inf.ethz.ch/gmohsen/
DepartementInformatik
BeziehungAssistenzprofessor (Tenure Track)

NummerTitelECTSUmfangDozierende
227-0558-00LPrinciples of Distributed Computing Information 7 KP2V + 2U + 2AR. Wattenhofer, M. Ghaffari
KurzbeschreibungWe 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.
LernzielDistributed 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.
InhaltDistributed 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
SkriptAvailable. Our course script is used at dozens of other universities around the world.
LiteraturLecture 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 / BesonderesCourse pre-requisites: Interest in algorithmic problems. (No particular course needed.)
252-4202-00LSeminar in Theoretical Computer Science Information 2 KP2SE. Welzl, B. Gärtner, M. Ghaffari, M. Hoffmann, J. Lengler, D. Steurer, B. Sudakov
KurzbeschreibungPresentation of recent publications in theoretical computer science, including results by diploma, masters and doctoral candidates.
LernzielTo get an overview of current research in the areas covered by the involved research groups. To present results from the literature.
Voraussetzungen / BesonderesThis 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-00LPresenting Theoretical Computer Science Belegung eingeschränkt - Details anzeigen
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 KP2SB. Gärtner, M. Ghaffari, R. Kyng, D. Steurer, E. Welzl
KurzbeschreibungStudents present current or classical results from theoretical computer science.
LernzielStudents 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.
InhaltStudents present current or classical results from theoretical computer science.
Voraussetzungen / BesonderesThe 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-00LAlgorithms for Large-Scale Graph Processing Information Belegung eingeschränkt - Details anzeigen
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 KP2SM. Ghaffari
KurzbeschreibungThis 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.
LernzielThis 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.
InhaltThe 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.
LiteraturThe papers will be presented in the first session of the seminar.
Voraussetzungen / BesonderesPrerequisite: Having passed at least one master's level course in theoretical computer science (ideally Advanced Algorithms and/or Randomized Algorithms).