Distributed Computing Group Distributed Computing Group
ETH Zurich Distributed Computing Group
ETH ZurichITETTIKDistributed Computing Group Lectures – Fs16 – Ti2

HOME
MEMBERS  
PUBLICATIONS  
COURSES  
THESES  
WIKI  
CONTACT  
     
SOFTWARE & APPS  
benG  
BitThief  
Conference Search  
DiscoMark  
jukefox  
Kännsch  
Smart Cloud Storage  
Newspaper 2.0  
Sinalgo  
sound mate  
TinyOS IDE  
     
SPIN-OFFs  
BitSplitters  
     
FORMER  
Spamato  
StreamForge  
Wuala  

Computer Engineering 2 (Technische Informatik 2) (FS 2016)

This page is no longer maintained. Check the current lecture here.

Computers come in all shapes and sizes: servers, laptops, tablets, smartphones, smartwatches, all the way down to that tiny microcontroller in a washing machine. People buy a computer because (i) it gives them access to the Internet, (ii) it provides storage, and probably also because (iii) it computes. While having network access seems to be vital, advanced storage and computing capabilities more and more move to designated servers ("the cloud"). In this lecture, we learn how computers provide networking, storage, and computation by means of an operating system.

We start out with networking, and discuss the internet protocol, addressing, routing, transport layer protocols, flows, some representative application layer protocols, and how to implement these with sockets. We also discuss the link and physical layer, Markov chains and PageRank, and selected topics in security. Regarding storage, we talk about file systems, the memory hierarchy, caching, efficient data structures such as hashing, and data base principles. Concerning computation, we discuss the virtualization of the processing units with processes and threads. We focus on concurrency and examine scheduling, locking, synchronization, mutual exclusion, deadlocks, and consistency.

The lecture will use various teaching paradigms. The majority of the lecture will be based on blackboard discussions, supported by a script. Where appropriate we will also use slides or demonstrations. A few lectures will be flipped classroom style. The lecture will feature weekly paper exercises.

However, some of the course material is best learned in front of an actual computer. In addition to the lecture we offer exciting hands-on exercises in a lab environment. Please check the lab website for details.

Course languages: German (lecture), English (materials).

Lecture by Roger Wattenhofer, Thursday 10-12 @ ETF C 1

Exercises organized by Georg Bachmeier, Friday 15-17 or Tuesday 10-12 @ ETF C 1. You can pick freely which one to attend - the two slots offer identical content.


Exam The exam will take place on Wednesday, 24th of August 2016, 15:00-16:30 in Hönggerberg, building HIL, room F 15. The exam will be in German. You are allowed to bring any written material you like (script, books, personal notes,...), but no electronic devices whatsoever (no calculator, phone, laptop,...).
Exam with solutions

Q&A session There will be Q&A session on Thursday, 18th of August 2016 from 14:00 to 17:00, in CAB G 11. For a question to be answered, it has to be precise and answerable without recapulating a significant portion of a chapter/exercise session. Please submit your questions on EduApp by Tuesday, 16th of August 2016 at 23:59.

Exam review (Klausureinsicht) There will be an exam review in G88 (ETZ building) on Thursday, September 15, from 9:00am to 12:30pm and on Tuesday, September 20, from 11:30am to 3pm. Please take note of the following fine print:
* We will post a sample solution by noon on Wednesday, September 14.
* No registration is necessary. Just show up.
* At most two students can look at their exam at the same time. Thus, there might be a queue.
* In order to minimize the time your fellow students have to wait, we kindly ask you to limit your exam review to 20 minutes.
* Please bring your legi for identification; you will not be allowed to see your exam without this.


Second exam The second exam will take place on Saturday, 11th of February 2017, 09:00-10:30 in Hönggerberg, building HIL, room F 61. The exam will be in German. You are allowed to bring any written material you like (script, books, personal notes,...), but no electronic devices whatsoever (no calculator, phone, laptop,...).

Q&A session second exam There will be Q&A session on Thursday, 26th of January 2017 from 13:00 to 15:00, in ETZ E 7. For a question to be answered, it has to be precise and answerable without recapulating a significant portion of a chapter/exercise session. Please submit your questions to the google doc you've been sent a link to via email by Tuesday, 24th of January 2017 at 23:59.

Second exam review (Klausureinsicht) There will be an exam review for the second exam in G88 (ETZ building) on Thursday, March 09, from 9:00am to 12:00pm and on Tuesday, March 14, from 13:00pm to 16:00pm. Please take note of the following fine print:
* No registration is necessary. Just show up.
* At most two students can look at their exam at the same time. Thus, there might be a queue.
* In order to minimize the time your fellow students have to wait, we kindly ask you to limit your exam review to 20 minutes.
* Please bring your legi for identification; you will not be allowed to see your exam without this.


News

  • 29. April: As there will be no lecture on 05. May, there will be no exercise sessions on 06. May and 10. May.
  • 27. July: There is a mistake in chapter 11. The second remark after definition 11.7 defines the expected hitting time in terms of an infinite series, but that series isn't correct. Please cross out the sentence that starts with "By definition, h_{i,j} is the sum..." and refer to the way the expected hitting time is described via a system of equations in Lemma 11.8.
  • 02. August: There is a mistake in chapter 12. In Algorithm 12.26, point 2 the sum is missing a "k", i.e. it should read "k_n = k XOR k_1 XOR ..."
  • 18. August: There is a mistake in chapter 11. In the remarks after Lemma 11.24, the bullet point that starts with "One could use the following Markov chain to compute the cover time..." models the desired Markov chain wrong; you can ignore that bullet point.

We were offered to put the material for the Prüfungsvorbereitungskurs by Michael Wolf on here.
Disclaimer: this is not official material and has not been checked by us.
PVK material slide set 1 animated and print version.
PVK material slide set 2 animated and print version.


All script chapters in one file

In single page and double page format.

Lecture material single chapters


Title Lecture Notes Exercises Responsible Assistant Additional Material

Chapter 0
Introduction
2016/02/25
PDF 1:1
PDF 2:1

Chapter 1
Network Layer
2016/02/25
PDF 1:1
PDF 2:1
Exercises, Quiz
Solutions
David Stolz

Chapter 2
Transport Layer
2016/03/03
PDF 1:1
PDF 2:1
Exercises, Quiz
Solutions
Sebastian Brandt

Chapter 3
Application Layer
2016/03/10
PDF 1:1
PDF 2:1
Exercises, Quiz
Solutions
Christian Decker

Chapter 4
Locks
2016/03/17
PDF 1:1
PDF 2:1
Script
Exercises, Quiz
Solutions
Pascal Bissig
[AMP Chapter 7] source of the Script

Chapter 5
Concurrency
2016/03/24
PDF 1:1
PDF 2:1
Exercises, Quiz
Solutions
Christian Decker
[OSYS] chapter numbers in the PDFs refer to this book
[Q&A session]

Chapter 6
Dictionaries
2016/04/07
PDF 1:1
PDF 2:1
Exercises, Quiz
Solutions
Georg Bachmeier
[Alternative proof] of Theorem 6.9, as presented in the lecture

Chapter 7
Databases
2016/04/14
PDF 1:1
PDF 2:1
Exercises, Quiz
Solutions
Laura Peer

Chapter 8
Concurrent Data Structures
2016/04/21
PDF 1:1
PDF 2:1
Script
Exercises, Quiz
Solutions
Philipp Brandes
[AMP Chapter 9] part 1 of the Script
[AMP Chapter 13] part 2 of the Script

Chapter 9
Storage
2016/04/28
PDF 1:1
PDF 2:1
Exercises
Solutions
Georg Bachmeier
[OSTEP] the assigned reading consists of chapters 36, 37, 39, 40, and the appendix on Flash-based SSDs
[Quiz 1] I/O
[Quiz 2] Hard Disks
[Quiz 3] Files and Directories
[Quiz 4] File System Implementation
[Quiz 5] SSDs
[Answers to quizzes]

Chapter 10
Link Layer
2016/05/12
PDF 1:1
PDF 2:1
Exercises
Solutions
Michael König

Chapter 11
Markov Chains & PageRank
2016/05/19
PDF 1:1
PDF 2:1
Exercises, Quiz
Solutions
Sebastian Brandt

Chapter 12
Security
2016/05/26
PDF 1:1
PDF 2:1
Exercises, Quiz
Solutions
Klaus-Tycho Förster

Mock exam
2016/06/02
PDF 1:1
PDF 2:1
Georg Bachmeier

Final exam with solutions
2016/09/15
PDF 1:1
PDF 2:1
Georg Bachmeier

Second exam with solutions
2017/02/11
PDF 1:1
PDF 2:1
Georg Bachmeier

References

All references are accessible from within the ETH-network; OSTEP is accessible from everywhere.


[OSTEP] Operating Systems: Three Easy Pieces
Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau
Arpaci-Dusseau Books
[OSYS] Operating System Concepts, 8th Edition
Abraham Silberschatz, Peter Baer Galvin, Greg Gagne.
John Wiley & Sons, 2008, ISBN 978-0-470-12872-5
[APUE] Advanced Programming in the UNIX® Environment, Third Edition
W. Richard Stevens, Stephen A. Rago.
Addison-Wesley Professional, 2013, ISBN 978-0-321-63773-4
[AMP] The Art of Multiprocessor Programming
Maurice Herlihy, Nir Shavit.
Elsevier/Morgan Kaufmann, 2008, ISBN 978-0-12-370591-4