Verteilte Systeme

Dozenten

Dipl.Inf. Philipp Schmidt
Prof. Dr.-Ing. Volker Roth

Inhalt

Einführung und Übersicht: Wozu verteilte Systeme? Problemfelder und Lösungsansätze.
Kommunikationssysteme: Klassifizierung von Kommunikationsdiensten, Kommunikationsdienste des Betriebssystems (Pipes, Message Queues, Sockets, Shared Memory)
Netzdienste im Internet: Kommunikationsdienste (TCP, UDP, SCTP, RTP), Standarddienste, Fernerzeugung von Prozessen.

Architektur verteilter Systeme: Datenfluss-Architektur versus Client/Server-Architektur versus verteilte Algorithmen.
Verteilungsabstraktion: Message passing vs. Fernaufrufe, mobiler Code, mobile Objekte, replizierte Objekte, Verteilte Dateisysteme.

Verteilte Algorithmen: Zeit und Kausalität, CAP-Theorem, Gruppenkommunikation, Auswahlalgorithmen, Sperrsynchronisation, Sondieren mit Echos, Vektoruhren.
Sicherheit und Fehlertoleranz: Terminologie und Fehlerklassifikation, Replikation mit Abstimmung (voting), Verteilte Übereinkunft, Byzantinische Fehler.

Verteilung von Berechnungen (z.B. Map-Reduce).

Termine

Vorlesung:

• Dienstag, 12.4. - 21.6.2011, 8:30 s.t. - 10:00, T9/005, Philipp Schmidt
• Dienstag, 21.6. - 05.7.2011,.8:30 s.t. - 10:00, T9/006, Philipp Schmidt

Tutorien:

• Donerstag, 8:30 s.t. - 10:00, T9/006, Philipp Schmidt <philipp (dot) schmidt (äth) fu (minus) berlin (punkt) de>
• Freitag, 14:00 c.t. - 16:00, T9/046, Andreas Nüßlein <nutz (äth) inf (punkt) fu (minus) berlin (dot) de>

Klausur:

• Dienstag, 12.7.2011, 8:00 - 10:00, ZIB-Hörsaal

Nachklausur:

• Dienstag, 4.10.2011, 10:00 - 12:00, T9/005

Aufgaben

Alle Aufgaben sind bis auf Weiteres in Zweiergruppen zu bearbeiten. Die Abgabe besteht in der Regel aus zwei Teilen

• Schriftliche Ausarbeitung auf Papier, in der die Lösung erklärt und kommentiert wird und besonders wichtige Code-Stücke präsentiert werden. Die Abgabe dieses Teils erfolgt in der Vorlesung am Dienstag.
• Quellcode ist per e-mail an den Tutor zeitgleich mit der Papierabgabe als jar oder tar zu schicken.

Aufgabe 1 - Alternating Bit Protocol.

Abgabe: 26. April 2011

• Implementieren Sie das Alternating Bit Protocol als Sender- und Empfänger-Proxy auf den Kanälen, so dass das Hello-World-Beispiel aus dem Framework auch zuverässig "Hello World!" ausgibt, und nicht z.B. "lor!Hel W".
  
• Das Enfernen der Simulatoren für Paketverlust und Verzögerung ist keine akzeptierte Lösung.

Material: Framework

Aufgabe 2 - Socket-Kommunikation.

Abgabe: 10. Mai 2011

• Lesen Sie Sich in die Java Socket API (java.nio) ein
• Implementieren Sie ein Channel-Interface für UDP. Benutzen Sie die Klassen "UdpChannel" und "UdpChannelFactory" als Vorlage. Ein Paket-Dispatcher wird als Teil der "UdpChannelFactory" nötig sein.
• Beschreiben Sie die Limitierungen Ihrer Implementierung z.B. im Bezug auf Paketgrößen und skizzieren Sie Lösungsansätze zur Überwindung der Limitierungen.
• Die Methoden newUdpChannel(int port) und newUdpChannel(int local_port, InetAddress remote, int remote_port) müssen sich Sockets teilen können. [Update im Tutorium]

Material: Framework, Musterlösung [Updated 2011-05-19, Nebenläufigkeitsproblem gefixt]
Implementierungen, die nicht in der Lage sind sich Sockets zu teilen, werden als nicht bestanden gewertet, können aber bis 14. Mai nachgereicht werden. [Update 2011-05-19]

Literaturaufgabe 1 - Zeit

Diskussion im Tutorium am 5./6. Mai 2011

• Lesen Sie [ 1 ] und [ 2 ].
• Wie verhalten sich Skalare Zeit und Vektorzeit, wenn das Medium nicht FIFO garantiert?
• In welchen Fällen ist es sinnvoll unabhängige Ereignisse zu erkennen.
• Diskutieren Sie die Bedeutung von diskreter vs. dichter Zeit. [ 3 ]

Aufgabe 3 - syncrone verteilte Algorithmen.

Abgabe: 24. Mai 2011

• Erweitern Sie Ihre UdpChannel Implementierung um die nichtblockierende recv()-Methode "nrecv()".
• Bauen Sie sich ein kleines Framework, dass es ermöglicht synchrone Algorithmen auf unserer Channel-Abstraktion auszuführen (für diese und spätere Aufgaben). Das Framework muss sicherstellen, dass Nachrichten, die in Runde n gesendet wurden, in Runde n+1 empfangen und verarbeitet werden. Sie können Timeingunterschiede zwischen Nachrichten zwischen Prozessen und Nachrichten zwischen ggf. vorhandenem Sequencer und Prozessen vernachlässigen.
• Implementieren Sie den Time-Slice-Algorithmus in Ihrem Framework.
  Die main-Methode der Abgabe in soll in einer Klasse namens TimeSlice.java liegen, und die Anzahl der Prozesse als Parameter nehmen. Die IDs der Prozesse sind zufällig zu vergeben. Die Implementierung soll die einzelnen Nachrichten, die Runden- und Phasen-Nummern und den gewählten Koordinator auf der Standardausgabe ausgeben.
Material: Framework / Musterlösung Übung 2

Aufgabe 4 - GHS-Algorithmus

Abgabe: 7. Juni 2011

• Implementieren Sie den asynchronen GHS-Algorithmus, und gehen Sie dabei wie folgt vor:
• Erweitern Sie die Klassen GHSNode
• Schreiben Sie eine Main-Methode, mit zwei Parametern:

int   n   - Anzahl der Nodes
float p   - Wahrscheinlichkeit für die Existenz einer Kante zwischen zwei beliebige Knoten.

die einen zusammenhängenden Graphen aus n GHSNodes erzeugt und anschließen den Algorithmus startet.
• Die Methoden von GHSNode sollten Meldung über jede Zustandsänderung auf der Standardausgabe machen.

Material: Rumpf für die GHSNode-Klasse

Aufgabe 5 - Verteiltes Spiel die 1.

Abgabe: 14. Juni 2011
Wir werden über die nächsten Übungszettel eine kleine verteilte Peer-to-Peer Wirtschaftssimulation schreiben.
Als erster Schritt soll ein kleines Kommandozeilenprogramm implementiert werden, das in der Lage ist Befehle entgegenzunehmen, wobei für die verarbeitung der Eingabe beliebige Frameworks zugelassen sind.
Jeder Peer hat einen eindeutigen Nickname.
Es sollen zuerst zwei Befehle implementiert werden:

• connect stellt per UDP-Channel eine Verbindung zu einem Peer her.
• peers Zeigt die Nicknames alle Peers und der transitiv über Peers erreichbaren Peers an.
Für letzteren Befehl beitet es sich an über das über connechts erstellte Netzwerk Rekrusiv zu durchsuchen. Das Beispielsprotokoll leitet dabei die Suchanfragen über andere Knoten per Source-Routing weiter.
Optional: Die Implementierungen aller Gruppen sollten interoperabel sein. Das Protikoll werden wir gemeinsam in den Tutorien entwickeln. Material: Kurzbeschreibung des optionalen interoperablen Protokolls Musterlösung von Alexander Dümont und Sascha Gennrich

Aufgabe 6 - Verteiltes Spiel die 2.

Abgabe: 28. Juni 2011
Im zweiten Schritt differenzieren wir die Knoten: Jeder Knoten soll nun entweder einen Planeten, auf dem verschiedene Handelswaren angeboten werden, Auf dem Handelsschiff soll es nun folgende zwei zusätzlichen Kommandos geben:

• goods listet die im Universum gehandelten Waren auf (wobei Planeten die Reichweite der Angebote beschränken können).
• course (good)Listet an und Verkaufskurse einer Handelswaren auf den Planeten im Universum auf (wie bei goods).
Dazu müssen die Planeten Angebot und Nachfrage simulieren und einen Algorithmus zur Suche aller Handelswaren unterstützen. Material: Kurzbeschreibung des optionalen interoperablen Protokolls Musterlösung von Jan-Ole Malchow und Ansgar Schneider

Aufgabe 7 - Verteiltes Spiel die 2.

Abgabe: 5. Juli 2011
Im dritten Schritt erweitern dwir as Raumschiff nun um die letzten fehlenden Kommandos:

• start (ip) (port) legt den Startort fest.
• travell (planet) reist zu einem Nachbarplaneten
• buy (good) (amount) kauft eine Handelsware
• sell (good) (amount) verlauft ein Handelsware
Alle Handelsware werden immer in ganzen Tonnen gehandelt, das Raumschiff hat eine Maximalkapzität
Jede Reise kostet den Absolutbetrag der Portdifferenz an Treibstoff (Gold) Material: Kurzbeschreibung des optionalen interoperablen Protokolls

Vorlesungen

Vorlesung 1, Dienstag April 12

Themen:

• Organisatorisches
• Einführung: Was sind verteilte Systeme? Wozu verteilte Systeme? [ 4 ]
• Klassifizierung von Kommunikationsdiensten.
Folien

Vorlesung 2, Dienstag April 19

Themen:

• Klassifizierung von Kommunikationsdiensten II.
• Fehlertypen in Kommunikationsdiensten [ 4 ],[ 5 Kap. 2.2 ]
• Lokale Kommunikationsdienste (Pipes, Message Queues, Sockets, Shared Memory)
Folien

Vorlesung 3, Dienstag April 26

Themen:

• Disjunktives Warten mit select und poll
• Kommunikationsdienste im Internet (TCP, UDP, SCTP, RTP)
• Verteilungsabstraktion.
• Remote Procedure Calls (RPC)
Folien

Vorlesung 4, Dienstag Mai 03

Themen:

• Definition Verteilte Algorithmen
• Kausalität
• Ordnung von Ereignissen [ 1 ],[ 2 ],[ 3 ]
• Auswahlalgorithmen [ 5 Kap. 2 ]
Folien

Vorlesung 5, Dienstag Mai 10

Themen:

• Synchrone verteilte Algorithmen [ 5 Kap. 2 ]
• Auswahlalgorithmen II [ 5 Kap. 2, 15.1 ]
• Sperrsynchronisation [ 4 ],[ 5 Kap. 20.1 ]
Folien

Vorlesung 6, Dienstag Mai 17

Themen:

• Breitensuche, kürzeste Wege [ 5 ][Kap. 4, 15.3-15.4]
Folien

Vorlesung 7, Dienstag Mai 24

Themen:

• Minimal Aufspannende Bäume (GHS-Algorithmus) [ 5 Kap. 4.4, 15.6 ]
• Minimale unabhängige Menge [ 5 Kap. 4.5 ]
Folien

Vorlesung 8, Dienstag Mai 31

Themen:

• Verteilte Übereinkunft [ 5 ][Kap. 5-6],[ 4 Kap. 12 ]
• Fehlermodelle in verteilten Systeme [ 4 Kap. 2.3.2 ]
Folien

Vorlesung 9, Dienstag Juni 07

Themen:

• Diffusionsalgorithmen, Verteilte Terminierungserkennung [ 5 Kap. 19 ]
• Globaler Zustand, Snapshorts, verteiltes Debugging, verteilte Garbage Collection [ 5 Kap. 19 ],[ 4 Kap. 11 ]
• CAP-Theorem [ 6 ]
Folien

Vorlesung 10, Dienstag Juni 14

Themen:

• Verteilte Verzeichnisdienste (DNS, LDAP)
Folien

Vorlesung 11, Dienstag Juni 21

Themen:

• Peer-to-peer Systeme
• Verteilte Hashtabellen [ 7 ],[ 8 ],[ 9 ]
Folien

Vorlesung 12, Dienstag Juni 28

Themen:

• Map/Reduce [ 10 ]
• Google File System [ 11 ]
• Hadoop
Folien

Vorlesung 13, Dienstag Juli 05

Themen:

• Überblick verteilte Dateisysteme
• Überblick verteilte Betriebsysteme
• Klausurvorbereitung
Folien

Literatur

1. Leslie Lamport,
   Time, clocks, and the ordering of events in a distributed system
   in Communications of the ACM, Volume 21, Pages 558--565, July 1978
2. Colin J. Fidge
   Timestamps in Message-Passing Systems That Preserve the Partial Ordering.
   in Proc. of the 11th Australian Computer Science Conference (ACSC'88)
3. Mattern, Friedemann
   Virtual Time and Global States of Distributed Systems.
   in Proc. Workshop on Parallel and Distributed Algorithms, Chateau de Bonas, France: Elsevier, pp. 215–226
4. George Coulouris, Jean Dollimore, Tim Kindberg
   Distributed Systems - Concepts and Design forth Edition
   Addison Wesley 2005
5. Nancy A. Lynch
   Distributed Algorithms
   Morgan Kaufmann 1997
6. Seth Gilbert and Nancy Lynch,
   Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services
   ACM SIGACT News, Volume 33, Issue 2, June 2002
7. Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek and Hari Balakrishnan
   Chord: A scalable peer-to-peer lookup service for internet applications
   ACM SIGCOMM Comput. Commun. Rev. 2001
8. Author:David Karger and Matthias Ruhl
   Diminished Chord: A Protocol for Heterogeneous Subgroup Formation in Peer-to-Peer Networks
   in Book Title: LNCS: Peer-to-Peer Systems III Springer Berlin / Heidelberg 2005
9. Petar Maymounkov and David Mazières
   Kademlia: A Peer-to-Peer Information System Based on the XOR Metric
   in LNCS Peer-to-Peer Systems
   Springer Berlin / Heidelberg 2002
10. Jeffrey Dean and Sanjay Ghemawat
    MapReduce: Simplified Data Processing on Large Clusters
    OSDI'04: Sixth Symposium on Operating System Design and Implementation, San Francisco, CA, December, 2004.
11. Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung
    The Google File System
    19th ACM Symposium on Operating Systems Principles, Lake George, NY, October, 2003.