COMPUTER SYSTEMS - FALL 2018 - COURSE MATERIAL

Bonus Assignment

Through the bonus assignment, you can earn a quarter grade (0.25) bonus to your grade for
this course. Your task is to create an original "exam question" including a (correct) solution for
one of the topics covered in the lecture. We might use your question as inspiration in the actual
exam. The rules of the submission and further information is described in the following PDF.
 
 
 

Lecture

 The Full script is now available here.

 

Date Lecturer Chapter Exercise
Fri, 21/09 Timothy Roscoe

Introduction [PDF 1:1]

Naming [PDF 1:1PDF 2:1notes]

 -
Mon, 24/09 Timothy Roscoe The Kernel [PDF 1:1, PDF 2:1, notes]  -
Fri, 28/09 - No Lecture  Building a Kernel [PDF, disk.img]
Mon, 01/10 Timothy Roscoe Processes [PDF 1:1, PDF 2:1, notes]  
Fri, 05/10 Timothy Roscoe IPC [PDF 1:1, PDF 2:1, notes]  Threads-package [PDF, main.c, threads.h], solution [PDF, code]
Mon, 08/10 Roger Wattenhofer

Introduction [PDF 1:1, PDF 2:1]

Fault Tolerance & Paxos [PDF 1:1PDF 2:1]

 
Fri, 12/10 Roland Schmid

Consensus [PDF 1:1, PDF 2:1]

Paxos/Consensus [PDF], solution[PDF
Mon, 15/10 Timothy Roscoe

Scheduling [PDF 1:1, PDF 2:1, notes]

 
Fri, 19/10 Timothy Roscoe

I/O [PDF 1:1, PDF 2:1]

 Scheduling and I/O [PDF], solution[PDF]
Mon, 22/10 Roger Wattenhofer

Byzantine Agreement [PDF 1:1, PDF 2:1]

 
Fri, 26/10 Roger Wattenhofer

Broadcast & Shared Coins [PDF 1:1, PDF 2:1]

 Synchronous/Asynchronous Model [PDF], solution [PDF]
Mon, 29/10 Roger Wattenhofer

Consistency & Logical Time [PDF 1:1, PDF 2:1]

 
Fri, 02/11 Roger Wattenhofer

Time, Clocks & GPS [PDF 1:1, PDF 2:1

 Clock Sync & Consistency and Logic Clocks [PDF], solution [PDF]
Mon, 05/11 Roger Wattenhofer

Quorum Systems [PDF 1:1, PDF 2:1

 
Fri, 09/11 Roger Wattenhofer

Eventual Consitency & Bitcoin [PDF 1:1, PDF 2:1

Quorum Systems, Eventual Constency & Bitcoin [PDF], solution [PDF
Mon, 12/11 Timothy Roscoe

Memory Management and Virtual Memory, [PDF 1:1, PDF 2:1, handout

 
Fri, 16/11 Timothy Roscoe

Demand Paging [PDF 1:1, PDF 2:1, handout

Virtual Memory & Demand Paging [PDF] , solution [PDF]
Mon, 19/11 Timothy Roscoe

File System Abstractions [PDF 1:1, PDF 2:1, handout

 
Fri, 23/11 Timothy Roscoe

File System Implementation [PDF 1:1, PDF 2:1, handout

 File Systems [PDF], solution [PDF]
Mon, 26/11 Timothy Roscoe

Network Stack [PDF 1:1, PDF 2:1, handout

 
Fri, 30/11 Timothy Roscoe

Virtualization [PDF 1:1, PDF 2:1, handout

 Virtualization & Network Stack [PDF], solution [PDF
Mon, 03/12 Roger Wattenhofer

Game Theory [PDF 1:1, PDF 2:1

 
Fri, 07/12 Roger Wattenhofer

Distributed Storage[PDF 1:1, PDF 2:1

Game Theory & Distributed Storage [PDF], solution [PDF]
Mon, 10/12 Pankaj Khanchandani

Authenticated Agreement [PDF 1:1, PDF 2:1

 
Fri, 14/12 Roger Wattenhofer

Advanced Blockchain [PDF 1:1, PDF 2:1

PBFT and Advanced Blockchain [PDF], solution [PDF]
Mon, 17/12  

Summary, Research and Q&A [OS, DistSys]

 
Fri, 21/12  

No lecture

 No exercise session

 

Exercise Session Slides

The exercise session slides of the TAs can be found under the following link (Note: the slides are not official material and might contain errors!)

Exercise session slides

Q&A Session

The questions and answers of the Q&A session (pdf)

 

Exam Preparation (Distributed Systems Part)

Generally speaking, all material covered by the lectures and the exercises may be tested in the exam.

In the distributed systems part, we did not discuss Sections 13.4, 13.5, and 26.5. The content of these sections is not part of the exam.

The following are part of the exam, but we do not expect you to memorize them:

  • Paxos Algo (7.3): no need to memorize 100%, but the general idea should be clear.
  • Ben-Or Algos (8.15 & 11.5): no need to memorize 100%, but the general idea should be clear.
  • Theorem 12.11 & 12.12: General idea, not math details.
  • Section 12.5: We only did this shallowly, so you only need to know the basic idea (signatures and secret sharing make it possible to implement a shared coin).
  • Advanced GPS Algos (14.31, 14.33, 14.37): no need to memorize 100%, but the general idea should be clear.
  • f-opaque Quorum System (15.33-15.36): We only did this shallowly, so you only need to know the basic idea (overlap needs to be large, and as such it becomes impractical).
  • Other hypercubic networks (24.12-24.16): We did not discuss these.
  • All PBFT Algos (25.12, 25.15, 25.17, 25.22, 25.23, 25.24): no need to memorize 100%, but the general idea should be clear (in particular, why these parts are needed, and the intuition behind them).

Also, there is no need to memorize any remarks, just passive knowledge of all remarks is enough.

  • For example, nobody will ask you how many uncles Ethereum allows, or how uncle rewards are split, or how often Ethereum produces blocks (see remarks after Definition 26.14), but we might want to know whether at all Ethereum uses a DAG-approach, or if Ethereum produces more or less blocks per hour than Bitcoin.
  • Second example: We don’t want you to know in what years GMT or UTC was established, or how the UTC format looks like, or why UTC is called UTC (see remarks after Definition 14.18), but you should know that UTC exists.
  • These are just two examples, all other remarks follow the same idea.

 

Everything else (Definitions, Algorithms, Proofs) is part of the exam.

For practice of the Distributed Systems part you may consult exams from previous years provided here: HS09HS10HS11HS12,HS13HS15HS16. Beware that the topics covered have shifted around a little over the years. For instance, this year's new chapters are "Broadcast & Shared Coins", "Time, Clocks & GPS" and "Advanced Blockchain Topics". Also, this year's exam will be in English!