Algorithmen für Verteilte Systeme

24. June 2011 Informatik
  • Titel: Algorithmen für Verteilte Systeme
  • Autor: reiser
  • Organisation: UNI ULM
  • Seitenzahl: 8

Skript herunterladen (PDF)

Inhalt

  • Montag Mittwoch vorrangig Vorlesung vorrangig Übung
  • jeweils im Raum O
  • Algorithmen für Verteilte Systeme
  • Algorithmen für Verteilte Systeme AVS WS
  • Übungen normalerweise mittwochs
  • Ausführliches Skript zur Vorlesung verfügbar
  • Verkauf am Anfang des Semesters Euro
  • Originalpublikationen zu einzelnen Themen
  • Originalpublikationen sind zu vielen Algorithmen die beste Literatur
  • Allgemeine Bücher Forts
  • Inhalte der Vorlesung
  • Inhalte der Vorlesung A
  • Grundlagen Verteilte Koordinierung Fehlertoleranz PeertoPeerSysteme
  • Beispiel Unsicherheit in lose gekoppelten Systemen
  • Inhalte der Vorlesung B
  • Inhalte der Vorlesung C
  • Uhren Wahlen gegenseitiger Ausschluss
  • Replikationstechniken Gruppenkommunikation Verteilte Einigungsalgorithmen
  • Beispiel zu Uhren
  • Automatische Uhrensynchronisation im Internet
  • Beispiel zu Wahlen Automatische Konfiguration
  • Inhalte der Vorlesung D
  • Inhalte der Vorlesung E
  • Grundlagen etablierter Systeme
  • Klassische File SharingSysteme Strukturierte PPSysteme
  • Verteilte konsistente Sicherungspunkte Schnappschuss
  • Vision Weltweites verteiltes Dateisystem
  • Inhalte der Vorlesung
  • Problematik bei verteilten Beobachtungen
  • Grundlagen Verteilte Koordinierung Fehlertoleranz PeertoPeerSysteme Verteilte Zustandserfassung
  • Beobachtungen zu verschiedenen Zeitpunkten
  • Grundlagen Überblick
  • Verteilte Systeme Definition
  • Definition und Grundbegriffe
  • Definition von Leslie Lamport
  • Modellierung von Systemeigenschaften
  • PunktzuPunktVerbindungen MulticastKommunikation Synchrone und asynchrone Systeme
  • Fehler und Ausfälle
  • Begriffe und Fehlerarten Ausfallerkennung
  • Definition von Andrew Tanenbaum
  • Analyse von Algorithmen
  • Definition von Peter Schulthess
  • Korrektheit und Komplexität
  • Verteilte Systeme Merkmale
  • Verteilte Systeme Definition V Garg
  • Mehrere unabhängige Rechner
  • Keine gemeinsame Uhr
  • können unabhängig voneinander ausfallen
  • Verbunden durch ein Netzwerk
  • Interaktion nur durch Nachrichtenaustausch möglich
  • Kein gemeinsamer Speicher
  • Kooperation der Knoten
  • Keine akkurate Ausfallerkennung
  • Unterschied zu einem Rechnernetz
  • Verteilte Systeme Bezeichnungen
  • Verteilte Systeme Bezeichnungen
  • Knoten Rechner Prozessor Prozess
  • Konvention für Bezeichner
  • Synchrone und asynchrone Systeme
  • Modellierung von unzuverlässigen Verbindungen
  • Keinerlei Aussage über Empfangsreihenfolge von Nachrichten
  • FIFOOrdnung Sequentielle Ordnung Senderordnung
  • Wie bei PunktzuPunktVerbindungen
  • Mit knotenübergreifenden Aussagen
  • Kausale Ordnung logische Ordnung Präzedenzordnung
  • Konsistente totale Ordnung
  • Kausale totale Ordnung
  • Konsistente totale Ordnung Kausale Ordnung
  • Physikalische Ordnung Ordnung nach Realzeit
  • Oft sind hier unterschiedliche Dinge damit gemeint
  • Im Kontext von verteilten Algorithmen übliche Bedeutung
  • Entfernte Methodenaufrufe sendreceive bzw requestreplyInteraktion
  • Ausführung von verteilten Aktivitäten
  • Systemeigenschaften eines synchronen Systems
  • Eigenschaften und Vorteile synchroner Systeme
  • Versuch eines Ausweg Partielle Synchronität
  • Nachteil eines synchronen Systemmodells
  • In vielen Situation zB internetbasierte verteilte Systeme realitätsfern

Vorschau

Organisatorisches

■

Vorlesungszeiten (2V+2Ü)

Montag, Mittwoch, 10:15 – 11:45 8:30 – 10:00 (vorrangig Vorlesung) (vorrangig Übung)

jeweils im Raum O27-3211

■

Kontakt

Hans P. Reiser, hans.reiser@uni-ulm.de, O-27/3402 Franz J. Hauck, franz.hauck@uni-ulm.de, O-27/348 Abteilung Verteilte Systeme

Algorithmen für Verteilte Systeme

Wintersemester 2005/06

Grundlagen.fm: 17.10.05 12:52 Grundlagen.fm: 17.10.05 12:52

■

Web-Seite

http://www-vs.informatik.uni-ulm.de/teach/ws05/avs/

Algorithmen für Verteilte Systeme (AVS), WS 2005/06

(C) 2005 Hans P. Reiser, Franz J. Hauck, Abteilung Verteilte Systeme, Universität Ulm

1

Algorithmen für Verteilte Systeme (AVS), WS 2005/06

(C) 2005 Hans P. Reiser, Franz J. Hauck, Abteilung Verteilte Systeme, Universität Ulm

Organisatorisches

■

Literatur

■

Übungen (normalerweise mittwochs)

●

Vorlesungsskript

●

Aufgabenblätter werden i.d.R. montags in der Vorlesung ausgeteilt (bzw. sind im Web verfügbar) iel: Vertiefung und Aufbereitung des Vorlesungsstoffs

– theoretische Aufgaben zur Wiederholung und Vertiefung des Vorlesungsstoffes – Programmieraufgaben bei geeigneten Themen – jeweils eine Woche Bearbeitungszeit

Ausführliches Skript zur Vorlesung verfügbar:

– Verkauf am Anfang des Semesters (4 Euro)

●

●

Vorlesungsfolien auf der AVS-Webseite verfügbar Das Skript kann den Besuch der Vorlesung nicht ersetzen!

●

●

Abgabe der Aufgaben über AVS-Webseite Aufgabeninhalte und Übung sind prüfungsrelevant!

Grundlagen.fm: 17.10.05 12:52

●

Grundlagen.fm: 17.10.05 12:52

Algorithmen für Verteilte Systeme (AVS), WS 2005/06

(C) 2005 Hans P. Reiser, Franz J. Hauck, Abteilung Verteilte Systeme, Universität Ulm

Algorithmen für Verteilte Systeme (AVS), WS 2005/06

(C) 2005 Hans P. Reiser, Franz J. Hauck, Abteilung Verteilte Systeme, Universität Ulm

Literatur

■

Literatur

■

Vorlesungsskript

●

Originalpublikationen zu einzelnen Themen

●

Ausführliches Skript zur Vorlesung verfügbar:

– Verkauf am Anfang des Semesters (4 Euro)

Originalpublikationen sind zu vielen Algorithmen die beste Literatur

– Am Ende von jedem Kapitel sind im Skript die jeweils relevanten Literaturangaben aufgeführt – Insbesondere zum Nachlesen für ein tieferes Verständnis wird das Lesen der Originalpublikationen empfohlen

●

Vorlesungsfolien auf der AVS-Webseite verfügbar Das Skript kann den Besuch der Vorlesung nicht ersetzen!

●

■

Ergänzende Literatur

● ●

Publikationen… Bücher…

●

Kopien der wichtigsten Publikationen auf Webseite verfügbar (Kennwort siehe Vorlesung): http://www-vs.informatik.uni-ulm.de/teach/ws05/avs/doc/

Grundlagen.fm: 17.10.05 12:52

Algorithmen für Verteilte Systeme (AVS), WS 2005/06

(C) 2005 Hans P. Reiser, Franz J. Hauck, Abteilung Verteilte Systeme, Universität Ulm

Grundlagen.fm: 17.10.05 12:52

Algorithmen für Verteilte Systeme (AVS), WS 2005/06

(C) 2005 Hans P. Reiser, Franz J. Hauck, Abteilung Verteilte Systeme, Universität Ulm

6

Literatur

■

Literatur

■

Allgemeine Bücher

●

Allgemeine Bücher (Forts.)

●

V. Garg: Elements of Distributed Computing. Wiley, 2002; und Concurrent and Distributed Computing in Java, Wiley, 2004 N. Lynch: Distributed Algorithms. Morgan Kauffmann, 1996 P. Veríssimo, L. Rodrigues: Distributed Systems for System Architects. Kluwer Academic Publisher Group, 2000 F. Mattern: Verteilte Basisalgorithmen. Springer-Verlag, 1989 M. Singhal, N. G. Shivaratri: Advanced Concepts in Operating Systems. McGraw-Hill, 1994

Grundlagen.fm: 17.10.05 12:52

K. P. Birman: Building Secure and Reliable Network Applications, 1996; und Reliable Distributed Systems, 2005 R. Guerraoui, L. Rodrigues: Introduction to Reliable Distributed Programming, erscheint Nov. 2005

●

● ●

● ●

Grundlagen.fm: 17.10.05 12:52

Algorithmen für Verteilte Systeme (AVS), WS 2005/06

(C) 2005 Hans P. Reiser, Franz J. Hauck, Abteilung Verteilte Systeme, Universität Ulm

7

Algorithmen für Verteilte Systeme (AVS), WS 2005/06

(C) 2005 Hans P. Reiser, Franz J. Hauck, Abteilung Verteilte Systeme, Universität Ulm

8

Inhalte der Vorlesung

■ ■ ■ ■ ■

Inhalte der Vorlesung (A)

■

Grundlagen Verteilte Koordinierung Fehlertoleranz Peer-to-Peer-Systeme

Grundlagen

● ● ● ●

Was ist ein verteiltes System? Modellierung von Systemeigenschaften Fehlerarten und Fehlererkennung Bewertung von Algorithmen

Verteilte ustandserfassung

■

Beispiel: Unsicherheit in lose gekoppelten Systemen

– Lässt sich ein ausgefallener Knoten überhaupt erkennen? – Netzwerkprobleme können „falsches“ Bild liefern: z.B. A B und B C, aber nicht A C – Kann man Anwendungen so entwickeln, dass man kein genaues Wissen darüber benötigt, welche Teile des Systems verfügbar und welche ausgefallen sind?

Algorithmen für Verteilte Systeme (AVS), WS 2005/06

(C) 2005 Hans P. Reiser, Franz J. Hauck, Abteilung Verteilte Systeme, Universität Ulm

Grundlagen.fm: 17.10.05 12:52

Algorithmen für Verteilte Systeme (AVS), WS 2005/06

(C) 2005 Hans P. Reiser, Franz J. Hauck, Abteilung Verteilte Systeme, Universität Ulm

9

Grundlagen.fm: 17.10.05 12:52

10

Inhalte der Vorlesung (B)

■

Inhalte der Vorlesung (C)

■

Verteilte Koordinierung

●

Fehlertolerante Systeme

● ● ●

Uhren, Wahlen, gegenseitiger Ausschluss

Replikationstechniken Gruppenkommunikation Verteilte Einigungsalgorithmen

– Problem der byzantinischen Generäle: Angriff oder Verteidigung? Gegner versucht, inkonsistentes Verhalten zu seinen Gunsten zu erreichen

■

Beispiel zu Uhren:

●

Automatische Uhrensynchronisation im Internet

■

Beispiel zu Wahlen: Automatische Konfiguration

● ● ●

Token Ring-Netzwerk: Token-Erzeugung Firewire: Bus-Master-Bestimmung bei Rekonfiguration Replizierte Servergruppe: Festlegung des Master-Replikats bei passiver Replikation

Grundlagen.fm: 17.10.05 12:52

Grundlagen.fm: 17.10.05 12:52

Algorithmen für Verteilte Systeme (AVS), WS 2005/06

(C) 2005 Hans P. Reiser, Franz J. Hauck, Abteilung Verteilte Systeme, Universität Ulm

11

Algorithmen für Verteilte Systeme (AVS), WS 2005/06

(C) 2005 Hans P. Reiser, Franz J. Hauck, Abteilung Verteilte Systeme, Universität Ulm

12