Distributed Computing Group Distributed Computing Group
ETH Zurich Distributed Computing Group
ETH ZurichITETTIKDistributed Computing Group LecturesDistsys

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  

Distributed Systems Part 2 (HS 2016)

Course Catalogue · Previous Year

Note: This page covers only the second part of the course. Visit the first part held by Prof. Mattern here.

We present the characteristics and concepts of distributed systems, and discuss distributed control algorithms (flooding, mutual exclusion, logical clocks), communications models (remote procedure call, client-server models, synchronous and asynchronous communication), abstract communication principles (broadcast, events, tupel spaces), name services, communication middleware for open systems, infrastructure for ad hoc networking (JINI), cloud computing, and mechanisms for security and safety. Having a distributed system may permit getting away with failures and malfunctions of parts of the system. We discuss fault-tolerance issues (models, consensus, agreement) as well as replication issues (primary copy, 2PC, 3PC, Paxos, quorum systems).

Topics: Distributed control algorithms (mutual exclusion, logical clocks), communication models (RPC, client-server, synchronous and asynchronous communication), abstract communication principles (broadcast, events, tuple spaces), communication middleware, security mechanisms, fault-tolerance (failure models, consensus, agreement), replication (primary copy, 2PC, 3PC, Paxos, quorum systems).

Course pre-requisites: None.

Course language: German and English.

Lecture by Prof. Roger Wattenhofer, Monday 9.15-11.00@ CAB G 11, Friday 9.15-11.00@ CAB G 61.
Exercises by Michael König, Monday 11.10-11.55@ CAB G 11, Friday 11.10-11.55@ CAB G 61.

Bonus: You can earn 10 bonus points ahead of the exam. Your task is to create an exam question for one of the topics covered in part 2 of the lecture. Click here for details. Update: Round 2.

News

  • 2016-09-21: Due to the exceptionally high attendance the lecture and exercises have moved to a larger room.
  • 2016-11-08: Details for the bonus point task have been released.
  • 2016-12-05: The chapter numbers on the slides for chapters 9 and 10 have been corrected.
  • 2016-12-12: Bonus round 2 has been announced.
  • 2016-12-16: Exam preparation section added: a list of material not relevant for the exam plus an array of old exams for practice.
  • 2016-12-21: The lecture on Friday, December 23rd, is cancelled. Happy holidays!
  • 2017-01-24: A Q&A session will be held on Friday, February 3rd, at 13.15 in CAB G 11. Please submit your questions at the latest 24 hours prior to Michael with subject line [DistSys Q&A].
  • 2017-03-09: This year's exam and a sample solution have been uploaded.

Lecture Material

Lecture material and exercise sheets will be uploaded here as the lecture progresses.

Title Lecture Notes Exercises Assistants Additional Material
Introduction
2016-11-07 (Monday)
PDF
PDF 2-on-1
--- --- ---
Chapter 1
Fault Tolerance & Paxos
2016-11-07 (Monday)
PDF
PDF 2-on-1
Exercises
Solutions
Georg
Pascal
Thomas
---
Chapter 2
Consensus
2016-11-11 (Friday)
PDF
PDF 2-on-1
Exercises
Solutions
Simon
Yuyi
---
Chapter 3
Byzantine Agreement
2016-11-14 (Monday)
PDF
PDF 2-on-1
Exercises
Solutions
Darya
Yuyi
---
Chapter 4
Authenticated Agreement
2016-11-18 (Friday)
PDF
PDF 2-on-1
Exercises
Solutions
Pascal
Pankaj
---
Chapter 5
Quorum Systems
2016-11-21 (Monday)
PDF
PDF 2-on-1
Exercises
Solutions
Georg
Simon
---
Chapter 6
Eventual Consistency & Bitcoin
2016-11-25 (Friday)
PDF
PDF 2-on-1
Exercises
Solutions
Michael
Pankaj
---
Chapter 7
Distributed Storage
2016-11-28 (Monday)
PDF
PDF 2-on-1
Exercises
Solutions
Gino
Pascal
---
Chapter 8
Game Theory
2016-12-02 (Friday)
PDF
PDF 2-on-1
Exercises
Solutions
Manuel
Yuyi
---
Chapter 9
Locking
2016-12-05 (Monday)
PDF
PDF 2-on-1
Exercises
Solutions
Manuel
Michael
Slides
[AMP Chapter 7]
Chapter 10
Concurrency
2016-12-09 (Friday)
PDF
PDF 2-on-1
Exercises
Solutions
Manuel
Michael
Slides
[AMP Chapter 9]
[AMP Chapter 13]
Chapter 11
Clock Synchronization
2016-12-12 (Monday)
PDF
PDF 2-on-1
Exercises
Solutions
Gino
Simon
---
Chapter 12
Consistency & Transactional Memory
2016-12-16 (Friday)
PDF
PDF 2-on-1
--- --- [AMP Chapter 3]
[AMP Chapter 18]
Android Project
Presentations & Demos
2016-12-19 (Monday)
(see Part 1 of the lecture)
(No Lecture)
2016-12-23 (Friday)
--- --- --- ---

References

All references are accessible from within the ETH network.

[AMP] The Art of Multiprocessor Programming
Maurice Herlihy, Nir Shavit.
Elsevier/Morgan Kaufmann, 2008, ISBN 978-0-12-370591-4

Exam Preparation

The written exam will take place on Friday, February 10th, in HIL G 61. It will last 180 minutes and include questions from both parts of the lecture (90 points for each part). No written or electronic aids are permitted.

Concerning part 2 of the lecture, generally speaking, all material covered by the lectures and the exercises may be tested in the exam. The lecture notes (accessible above) include some additional material, which is not relevant for the exam.

The following is a list of the material not relevant for the exam:

  • Chapter 5: definition 5.33 and everything after
  • Chapter 6: section 6.4
  • Chapter 7: definitions 7.11 – 7.15 (including pictures and remarks)
  • Chapter 9: [AMP book] sections 7.1, 7.5.2, 7.6, 7.7 and 7.8
  • Chapter 10: [AMP book] details of section 13.2.2, all of section 13.2.3
  • Chapter 11: slide 11/36 and everything after slide 11/38
  • Chapter 12: [AMP book] in general any code except for the “atomic” examples in section 18.2, details of section 3.1, all of sections 3.2, 3.6 and 3.8, details of section 18.3, in particular anything related to the extensive “SkipList” example, all of sections 18.3.2 and 18.3.4, subsection “In Detail” of section 18.3.7, all of section 18.3.8.

For practice and to get a feel for the style of questions in the exam you may consult exams from previous years provided here: HS09, HS10, HS11, HS12, HS13, HS15. Beware that the topics covered have shifted around a little over the years (for example, network updates were not part of this year's course).

A Q&A session will be held on Friday, February 3rd, at 13.15 in CAB G 11.

Important: You need to submit your questions no later than 24 hours prior to the session to give the responsible assistants enough time to find satisfying answers to your questions. That is, the deadline for submitting questions is Thursday, February 2nd, 13:00. Send your questions to Michael by mail using the subject line [DistSys Q&A]. If you only bring up your questions in the Q&A session, we cannot guarantee having answers for you.

Please keep in mind that this Q&A session will cover only part 2 of the lecture.

This Year's Exam

For your nostalgic and enlightening pleasure, we have made this year's exam available here. We are also providing a sample solution. Please note, that the sample solution merely contains a single correct solution for each task which would have netted full points, but other solutions may also have received partial or full points.