Distributed Systems Part 2 (HS 2009)

Note: Only second part, visit the first part of this course held by Prof. Mattern.

Lecture by Roger Wattenhofer, Monday 8-11 @ IFW A36.

Exercises by Benjamin Sigg, Thomas Locher, Remo Meier Friday 8-10 @ IFW A36.

Exam review

From 1.3.2010 until 18.3.2010 you can review your exams.

• Time: Monday 14-17, Wednesday 9-12.
• Place: Monica Fricker, office room ETZ G 88

In case, none of the dates is suitable for you please contact fricker@tik.ee.ethz.ch.

News

Unfortunately this is the first time Prof. Wattenhofer teaches a significant part of the lecture. Here are a few general exam guidelines:

• Typical systems (Chapters 7 and 8 mostly) will include question such as “How does system X work?”, or “What are the advantages of A over B?”, or “Why does system A do something like this, or what would be an alternative?”, or “Here a protocol that solves problem P, why is it [not] correct?”, or “What does this piece of pseudo-code do, and why does it [not] work?”
• Typical theory questions (Chapter 6 mostly) revolve around bounds and [im]possibility results. Below some exam questions on consensus:
  
  Shared Memory Consensus (20 Punkte)
  a) (7 Punkte) Ihr Arbeitskollege möchte in einem asynchronen shared memory Mehrprozessor-System, welches nur Lese- oder Schreib-Operationen unterstützt, eine “fetch-and-inc”-Operation implementieren. Diese Operation soll es einem Prozess erlauben, den Wert einer Speicherzelle zu lesen, und diese gleichzeitig (atomar) um 1 zu erhöhen. Was halten Sie davon? Unter welchen Umständen ist das möglich, unter welchen Umständen unmöglich? Begründen Sie Ihre Antworten kurz.
  b) (13 Punkte) Ein Hardware-Hersteller bietet ein neues asynchrones shared memory System an, das neben den üblichen Lese- oder Schreib-Operationen zwecks Mehrprozessor-Synchronisation auch eine “RoWa” Operation unterstützt. Die RoWa Operation erlaubt einem Prozess ein beliebiges Register zu lesen, und gleichzeitig (atomar) in ein beliebiges Register zu schreiben. Die RoWa Operation ist aber keine Read-Modify-Write Operation; d.h. der Wert des geschriebenen Registers darf nicht vom Wert des gelesenen Registers abhängen. Was ist die Consensus-Nummer dieses Systems?
  (Hinweis: Um zu zeigen, dass die Consensus-Nummer höchstens X ist, reicht eine Skizze ihres Beweises: erklären Sie Ihre generelle Beweisidee, und erklären Sie einen interessanten Teil des Beweises detailliert.)

Also, some exercise questions could had been possible exam questions. In particular:

• Ex 1:
• 1: Explaining concepts.
• 3: Analyzing protocols.
• Ex 2:
• 2: Proof consensus can/cannot be reached.
• Ex 3:
• 1: Modification of a protocol.
• Ex 4:
• 2a-c: Reasoning and explanation of protocols.
• Ex 5:
• 1: Inventing simple new protocols.
• 2.c: Explanations.

What to learn?

You have to learn everything that ca be found in the slides. The one exception are the hash-sets (chapter 8, from page 121 to the end of the chapter) which were not discussed in the lectures.

Exam

The exam is scheduled for Friday, 5. February 2010, from 9:00 to 12:00. You are not allowed to use the slides.
Both parts of the course have an equal weight on the final grade, the practical exercises of the first part have a weight of 15% to the final grade.

Question Session

We will hold a question session in which we (try to) answer your questions about this lecture. The session is on Thursday, 21. January 2010, 10:00 - 11:00 at ETZ F78.1 Please send us your questions ahead of time, at the latest until Wednesday, 20. January 2010 at 12:00 by email to the assistants.
The slides are now available: Download

Lecture material

Exercise material

© 2024 DISCO, TIK, ETH Zurich | Imprint | Last updated: Mon, 31 Aug 2020 21:06.