Roger Wattenhofer: Catalogue data in Autumn Semester 2020
|Name||Prof. Dr. Roger Wattenhofer|
Inst. f. Techn. Informatik u. K.
ETH Zürich, ETZ G 96
|Telephone||+41 44 632 63 12|
|Department||Information Technology and Electrical Engineering|
|227-0014-20L||Computational Thinking||4 credits||2V + 1U||R. Wattenhofer|
|Abstract||We learn: algorithmic principles, dynamic and linear programming, complexity, electronic circuits, P vs. NP, Turing machines, reductions, cryptography, zero-knowledge proofs, data organization, dictionaries, hashing, databases, SQL, machine learning, regression, clustering, deep neural networks. We will use Python as a programming language. There will be paper and programming exercises every week.|
|Objective||Computation is everywhere, but what is computation actually? In this lecture we will discuss the power and limitations of computation. Computational thinking is about understanding machine intelligence: What is computable, and how efficiently?|
Understanding computation lies at the heart of many exciting scientific, social and even philosophical developments. Computational thinking is more than programming a computer, it means thinking in abstractions. Consequently, computational thinking has become a fundamental skill for everyone, not just computer scientists. For example, functions which can easily be computed but not inverted are at the heart of understanding data security and privacy. Machine learning on the other hand has given us fascinating new tools to teach machines how to estimate functions. Thanks to clever heuristics, machines now appear to be capable of solving complex cognitive tasks. To give just one more example: How can we design the best electronic circuit for a given problem? In this class, we study various problems together with the fundamental theory of computation.
The weekly lectures will be based on blackboard discussions and coding demos, supported by a script and coding examples. The course uses Python as a programming language. Python is popular and intuitive, a programming language that looks and feels a bit like human instructions. The lecture will feature weekly exercises, on paper and in Python.
|227-0102-00L||Discrete Event Systems||6 credits||4G||L. Thiele, L. Vanbever, R. Wattenhofer|
|Abstract||Introduction to discrete event systems. We start out by studying popular models of discrete event systems. In the second part of the course we analyze discrete event systems from an average-case and from a worst-case perspective. Topics include: Automata and Languages, Specification Models, Stochastic Discrete Event Systems, Worst-Case Event Systems, Verification, Network Calculus.|
|Objective||Over the past few decades the rapid evolution of computing, communication, and information technologies has brought about the proliferation of new dynamic systems. A significant part of activity in these systems is governed by operational rules designed by humans. The dynamics of these systems are characterized by asynchronous occurrences of discrete events, some controlled (e.g. hitting a keyboard key, sending a message), some not (e.g. spontaneous failure, packet loss). |
The mathematical arsenal centered around differential equations that has been employed in systems engineering to model and study processes governed by the laws of nature is often inadequate or inappropriate for discrete event systems. The challenge is to develop new modeling frameworks, analysis techniques, design tools, testing methods, and optimization processes for this new generation of systems.
In this lecture we give an introduction to discrete event systems. We start out the course by studying popular models of discrete event systems, such as automata and Petri nets. In the second part of the course we analyze discrete event systems. We first examine discrete event systems from an average-case perspective: we model discrete events as stochastic processes, and then apply Markov chains and queuing theory for an understanding of the typical behavior of a system. In the last part of the course we analyze discrete event systems from a worst-case perspective using the theory of online algorithms and adversarial queuing.
2. Automata and Languages
3. Smarter Automata
4. Specification Models
5. Stochastic Discrete Event Systems
6. Worst-Case Event Systems
7. Network Calculus
|Literature||[bertsekas] Data Networks |
Dimitri Bersekas, Robert Gallager
Prentice Hall, 1991, ISBN: 0132009161
[borodin] Online Computation and Competitive Analysis
Allan Borodin, Ran El-Yaniv.
Cambridge University Press, 1998
[boudec] Network Calculus
J.-Y. Le Boudec, P. Thiran
[cassandras] Introduction to Discrete Event Systems
Christos Cassandras, Stéphane Lafortune.
Kluwer Academic Publishers, 1999, ISBN 0-7923-8609-4
[fiat] Online Algorithms: The State of the Art
A. Fiat and G. Woeginger
[hochbaum] Approximation Algorithms for NP-hard Problems (Chapter 13 by S. Irani, A. Karlin)
[schickinger] Diskrete Strukturen (Band 2: Wahrscheinlichkeitstheorie und Statistik)
T. Schickinger, A. Steger
Springer, Berlin, 2001
[sipser] Introduction to the Theory of Computation
PWS Publishing Company, 1996, ISBN 053494728X
|227-0555-00L||Distributed Systems |
Enrolled students will be notified by e-mail about the lecture start.
|4 credits||3G + 1A||R. Wattenhofer|
|Abstract||This course introduces the fundamentals of distributed systems. We study different protocols and algorithms that allow for fault-tolerant operation, and discuss practical systems that implement these techniques.|
|Objective||The objective of the course is for students to understand the theoretical principles and practical considerations of distributed systems. This includes the main models of fault-tolerant distributed systems (crash failures, byzantine failures, and selfishness), and the most important algorithms, protocols and impossibility results. By the end of the course, students should be able to reason about various concepts such as consistency, durability, availability, fault tolerance, and replication.|
|Content||We discuss the following concepts related to fault-tolerant distributed systems: client-server, serialization, two-phase protocols, three-phase protocols, paxos, two generals problem, crash failures, impossibility of consensus, byzantine failures, agreement, termination, validity, byzantine agreement, king algorithm, asynchronous byzantine agreement, authentication, signatures, reliable and atomic broadcast, eventual consistency, blockchain, cryptocurrencies such as bitcoin and ethereum, proof-of-work, proof-of-*, smart contracts, quorum systems, fault-tolerant protocols such as piChain or pbft, distributed storage, distributed hash tables, physical and logical clocks, causality, selfishness, game theoretic models, mechanism design.|
|Lecture notes||A script is available on the web page.|
|Literature||The script is self-contained, but links to additional material are available on the web page.|
|Prerequisites / Notice||This lecture takes place in roughly the second half of the semester, as the lecture is the second part of the lecture "Computer Systems" (252-0217-00). Students may attend at most one of the two lectures, NOT both.|
|252-0217-00L||Computer Systems||8 credits||4V + 2U + 1A||T. Roscoe, R. Wattenhofer|
|Abstract||This course is about real computer systems, and the principles on which they are designed and built. We cover both modern OSes and the large-scale distributed systems that power today's online services. We illustrate the ideas with real-world examples, but emphasize common theoretical results, practical tradeoffs, and design principles that apply across many different scales and technologies.|
|Objective||The objective of the course is for students to understand the theoretical principles, practical considerations, performance tradeoffs, and engineering techniques on which the software underpinning almost all modern computer systems is based, ranging from single embedded systems-on-chip in mobile phones to large-scale geo-replicated groups of datacenters.|
By the end of the course, students should be able to reason about highly complex, real, operational software systems, applying concepts such as hierarchy, modularity, consistency, durability, availability, fault-tolerance, and replication.
|Content||This course subsumes the topics of both "operating systems" and "distributed systems" into a single coherent picture (reflecting the reality that these disciplines are highly converged). The focus is system software: the foundations of modern computer systems from mobile phones to the large-scale geo-replicated data centers on which Internet companies like Amazon, Facebook, Google, and Microsoft are based.|
We will cover a range of topics, such as: scheduling, network protocol stacks, multiplexing and demultiplexing, operating system structure, inter-process communication, memory managment, file systems, naming, dataflow, data storage, persistence, and durability, computer systems performance, remove procedure call, consensus and agreement, fault tolerance, physical and logical clocks, virtualization, and blockchains.
The format of the course is a set of about 25 topics, each covered in a lecture. A script will be published online ahead of each lecture, and the latter will consist of an interactive elaboration of the material in the script. There is no book for the course, but we will refer to books and research papers throughout to provide additional background and explanation.
|Prerequisites / Notice||We will assume knowlege of the "Systems Programming" and "Computer Networks" courses (or equivalent), and their prerequisites, and build upon them.|
|252-0817-00L||Distributed Systems Laboratory|
This only applies to Study Regulations 09: In the Master Programme max.10 credits can be accounted by Labs on top of the Interfocus Courses. These Labs will only count towards the Master Programme. Additional Labs will be listed on the Addendum.
|10 credits||9P||G. Alonso, T. Hoefler, A. Klimovic, T. Roscoe, A. Singla, R. Wattenhofer, C. Zhang|
|Abstract||This course involves the participation in a substantial development and/or evaluation project involving distributed systems technology. There are projects available in a wide range of areas: from web services to ubiquitous computing including wireless networks, ad-hoc networks, RFID, and distributed applications on smartphones.|
|Objective||Gain hands-on-experience with real products and the latest technology in distributed systems.|
|Content||This course involves the participation in a substantial development and/or evaluation project involving distributed systems technology. There are projects available in a wide range of areas: from web services to ubiquitous computing including as well wireless networks, ad-hoc networks, and distributed application on smartphones. The goal of the project is for the students to gain hands-on-experience with real products and the latest technology in distributed systems. There is no lecture associated to the course.|