- Titel: Algorithmen für Verteilte Systeme
- Autor: reiser
- Organisation: UNI ULM
- Seitenzahl: 8
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