1 Einleitung.- 1.1 Verteilte Systeme.- 1.2 Prozesse und Ereignisse.- 1.3 Synchronisation und Kommunikation.- 1.3.1 Synchronisation.- 1.3.2 Kommunikation.- 1.4 Programmiersprachen für verteilte Systeme.- 1.4.1 Verteilte Programmiersprachen.- 1.4.2 Objektorientierte Parallelität, Actor-Modell und Atommodell.- 1.4.3 Die Sprache CSSA.- 1.4.4 Ein verteiltes Beispielprogramm.- 1.5 Verteilte Algorithmen.- 1.5.1 Beobachtungen am ggT-Beispiel.- 1.5.2 Verteilte Kontrollalgorithmen.- 1.5.3 Der Echo-Algorithmus.- 1.6 Ausblick auf die weiteren Kapitel.- 2 Untersuchung von Election-Algorithmen.- 2.1Das Election-Problem.- 2.1.1 Eine Übersicht bekannter Election-Algorithmen.- 2.1.2 Simulationsexperimente: Zufallszahlen und Versuchsmethode.- 2.2 Ringbasierte Election-Verfahren.- 2.2.1Election auf unidirektionalen Ringen.- 2.2.1.1 Eine Anwendung: Das Token-Ring-Protokoll.- 2.2.1.2 Nachrichtenkomplexität des unidirektionalen Verfahrens.- 2.2.2 Election auf bidirektionalen Ringen.- 2.2.2.1 Ein probabilistischer Algorithmus.- 2.2.2.2 Deterministische Varianten.- 2.2.2.3 Eine experimentelle Analyse des Koeffizienten c.- 2.2.3 Der Einfluß nicht-konstanter Nachrichtenlaufzeiten.- 2.3 Election-Algorithmen für andere Topologien.- 2.3.1 Election auf Bäumen.- 2.3.2 Election auf allgemeinen Netzen.- 2.3.2.1 Problematik der Bewertung allgemeiner Election-Algorithmen.- 2.3.2.2 Die allgemeinen Election-Verfahreh.- 2.3.2.3 Repräsentative beliebige Netze.- 2.3.2.4 Experimentelle Untersuchung allgemeiner Election-Verfahren.- 3 Das Schnappschußproblem.- 3.1 Konsistente globale Zustände.- 3.2 Das Schnappschußprinzip.- 3.3 Zwei symmetrische Schnappschußalgorithmen.- 3.4 Basisalgorithmen als Bausteine.- 3.5 Konsistenz durch ´Einfrieren´.- 4 Verteilte Terminierung.- 4.1 Einleitung.- 4.1.1 Das Märchen von der verteilten Terminierung.- 4.2 Ein Beispiel — verteiltes Lösen von krypto-arithmetischen Rätseln.- 4.2.1 Verteiltes Problemlösen.- 4.2.2 Sequentielle und parallele Lösungsansätze.- 4.2.3 Backtracking und Erkennung der Terminierung.- 4.2.4 Weitere Aspekte.- 4.3 Der Terminierungsbegriff.- 4.3.1 Ergebnisorientierte Terminierung.- 4.3.2 Kommunikationsorientierte Terminierung.- 4.4 Eine Analyse des Terminierungsproblems.- 4.4.1 Einfaches Zählen genügt nicht.- 4.4.2 Das Problem bei synchroner Kommunikation.- 4.5 Charakteristika von Terminierungsalgorithmen.- 4.5.1 Basisprinzipien.- 4.5.2 Eigenschaften, Mericmale und Kriterien.- 4.6 Verfahren mit zwei Wellen.- 4.6.1 Das Doppelzählverfahren.- 4.6.2 Der skeptische Algorithmus.- 4.6.3 Election-basierte Terminierungsalgorithmen.- 4.7 Zeitzonenverfahren.- 4.7.1 Eine symmetrische ringbasierte Version.- 4.7.2 Eine sternförmige Version mit beschränkter Zahl von Zeitzonen.- 4.7.3 Ein effizienter Terminierungstest für synchrone Kommunikation.- 4.7.3.1 Der DFG-Algorithmus.- 4.7.3.2 Eine effiziente Variante.- 4.7.3.3 Eine Realisierung in CSP.- 4.7.3.4 Bemerkungen zu synchronen Lösungen und CSP.- 4.8 Die Vektormethode.- 4.8.1 Der Revisor.- 4.8.2 Das Prinzip.- 4.8.3 Varianten.- 4.9 Die Kreditmethode.- 4.9.1 Eine Realisierung der Kreditmethode.- 4.9.2 Eine Variante.- 4.9.3 Optimierungen und weitere Varianten.- 4.10 Empirische Effizienzmessungen.- 4.10.1 Messungen am Zahlenrätselprogramm.- 4.10.2 Messungen mit synthetischen Benchmarkprogrammen.- 5 Virtuelle Zeit in verteilten Systemen.- 5.1 Zeitdiagramme und Kausalitätsstruktur.- 5.2 Realzeit.- 5.3 Virtuelle Zeit.- 5.4 Vektorzeit.- 5.4.1 Die Struktur der Vektorzeit.- 5.4.2 Die Analogie zu Minkowski´s Raumzeit.- 5.4.3 Anwendungsmöglichkeiten der Vektorzeit.- 5.5 Stichzeitpunkt und Schnappschuß.- 6 Schlußbemerkungen.- Anhang — Meßergebnisse allgemeiner Election-Algorithmen.- Literatur.
1 Einleitung.- 1.1 Verteilte Systeme.- 1.2 Prozesse und Ereignisse.- 1.3 Synchronisation und Kommunikation.- 1.3.1 Synchronisation.- 1.3.2 Kommunikation.- 1.4 Programmiersprachen für verteilte Systeme.- 1.4.1 Verteilte Programmiersprachen.- 1.4.2 Objektorientierte Parallelität, Actor-Modell und Atommodell.- 1.4.3 Die Sprache CSSA.- 1.4.4 Ein verteiltes Beispielprogramm.- 1.5 Verteilte Algorithmen.- 1.5.1 Beobachtungen am ggT-Beispiel.- 1.5.2 Verteilte Kontrollalgorithmen.- 1.5.3 Der Echo-Algorithmus.- 1.6 Ausblick auf die weiteren Kapitel.- 2 Untersuchung von Election-Algorithmen.- 2.1Das Election-Problem.- 2.1.1 Eine Übersicht bekannter Election-Algorithmen.- 2.1.2 Simulationsexperimente: Zufallszahlen und Versuchsmethode.- 2.2 Ringbasierte Election-Verfahren.- 2.2.1Election auf unidirektionalen Ringen.- 2.2.1.1 Eine Anwendung: Das Token-Ring-Protokoll.- 2.2.1.2 Nachrichtenkomplexität des unidirektionalen Verfahrens.- 2.2.2 Election auf bidirektionalen Ringen.- 2.2.2.1 Ein probabilistischer Algorithmus.- 2.2.2.2 Deterministische Varianten.- 2.2.2.3 Eine experimentelle Analyse des Koeffizienten c.- 2.2.3 Der Einfluß nicht-konstanter Nachrichtenlaufzeiten.- 2.3 Election-Algorithmen für andere Topologien.- 2.3.1 Election auf Bäumen.- 2.3.2 Election auf allgemeinen Netzen.- 2.3.2.1 Problematik der Bewertung allgemeiner Election-Algorithmen.- 2.3.2.2 Die allgemeinen Election-Verfahreh.- 2.3.2.3 Repräsentative beliebige Netze.- 2.3.2.4 Experimentelle Untersuchung allgemeiner Election-Verfahren.- 3 Das Schnappschußproblem.- 3.1 Konsistente globale Zustände.- 3.2 Das Schnappschußprinzip.- 3.3 Zwei symmetrische Schnappschußalgorithmen.- 3.4 Basisalgorithmen als Bausteine.- 3.5 Konsistenz durch ´Einfrieren´.- 4 Verteilte Terminierung.- 4.1 Einleitung.- 4.1.1 Das Märchen von der verteilten Terminierung.- 4.2 Ein Beispiel — verteiltes Lösen von krypto-arithmetischen Rätseln.- 4.2.1 Verteiltes Problemlösen.- 4.2.2 Sequentielle und parallele Lösungsansätze.- 4.2.3 Backtracking und Erkennung der Terminierung.- 4.2.4 Weitere Aspekte.- 4.3 Der Terminierungsbegriff.- 4.3.1 Ergebnisorientierte Terminierung.- 4.3.2 Kommunikationsorientierte Terminierung.- 4.4 Eine Analyse des Terminierungsproblems.- 4.4.1 Einfaches Zählen genügt nicht.- 4.4.2 Das Problem bei synchroner Kommunikation.- 4.5 Charakteristika von Terminierungsalgorithmen.- 4.5.1 Basisprinzipien.- 4.5.2 Eigenschaften, Mericmale und Kriterien.- 4.6 Verfahren mit zwei Wellen.- 4.6.1 Das Doppelzählverfahren.- 4.6.2 Der skeptische Algorithmus.- 4.6.3 Election-basierte Terminierungsalgorithmen.- 4.7 Zeitzonenverfahren.- 4.7.1 Eine symmetrische ringbasierte Version.- 4.7.2 Eine sternförmige Version mit beschränkter Zahl von Zeitzonen.- 4.7.3 Ein effizienter Terminierungstest für synchrone Kommunikation.- 4.7.3.1 Der DFG-Algorithmus.- 4.7.3.2 Eine effiziente Variante.- 4.7.3.3 Eine Realisierung in CSP.- 4.7.3.4 Bemerkungen zu synchronen Lösungen und CSP.- 4.8 Die Vektormethode.- 4.8.1 Der Revisor.- 4.8.2 Das Prinzip.- 4.8.3 Varianten.- 4.9 Die Kreditmethode.- 4.9.1 Eine Realisierung der Kreditmethode.- 4.9.2 Eine Variante.- 4.9.3 Optimierungen und weitere Varianten.- 4.10 Empirische Effizienzmessungen.- 4.10.1 Messungen am Zahlenrätselprogramm.- 4.10.2 Messungen mit synthetischen Benchmarkprogrammen.- 5 Virtuelle Zeit in verteilten Systemen.- 5.1 Zeitdiagramme und Kausalitätsstruktur.- 5.2 Realzeit.- 5.3 Virtuelle Zeit.- 5.4 Vektorzeit.- 5.4.1 Die Struktur der Vektorzeit.- 5.4.2 Die Analogie zu Minkowski´s Raumzeit.- 5.4.3 Anwendungsmöglichkeiten der Vektorzeit.- 5.5 Stichzeitpunkt und Schnappschuß.- 6 Schlußbemerkungen.- Anhang — Meßergebnisse allgemeiner Election-Algorithmen.- Literatur.
Verteilte Algorithmen sind Verfahren, die dadurch charakterisiert sind, daB mehrere autonome Prozesse gleichzeitig Teile eines gemeinsamen Problems in kooperativer Weise bearbeiten und der dabei erforderliche Informationsaustausch ausschlieBlich liber Nachrichten erfolgt. Derartige Algorithmen kommen im Rahmen verteilter Systeme zurn Einsatz, bei denen kein gemeinsamer Speicher existiert und die Ubertragungs- und Bearbeitungsdauer von Nachrichten i.a. nieht vernachlassigt werden kann. DaB dabei kein ProzeB eine aktuelle konsistente Sieht des globalen Zustands besitzt, fUhrt zu sammen mit anderen typischen Eigenschaften der Verfahren, wie Nebenliiufigkeit und Nichtdeterminismus, zu interessanten Problemen. In der vorliegenden Arbeit werden einige dieser Probleme analysiert, diskutiert und zueinander in Beziehung gesetzt. Flir eine Reihe von Grundproblemen, zu denen das Election-Problem, das SchnappschufJproblem und das Terminierungsproblem geh6ren, werden verschiedene LOsungsalgorithmen angegeben und miteinander verglichen. Die Bewertung der Algorithmen umfaBt analytische und empirische Untersuchungen sowie eine Diskussion der qualitativen Eigenschaften verschiedener Varianten. Urn ein tieferes Verstandnis des "Prinzips der Verteiltheit" zu erreichen, werden grundsatzliche Aspekte hervorgehoben, wie etwa die Bedeutung des Zeitbegriffs in verteilten Systemen. Dariiber hinaus werden einige typische Methoden und Techniken vorgestellt, die auch fUr die systemnahe oder anwendungsbezogene Programmierung verteilter oder hochgradig paralleler Systeme praktisch relevant sind. Durch die Beschreibung des Urnfeldes und der wichtigsten Konzepte der verteilten Programmierung, durch weiterflihrende Literaturangaben und einige spielerische und gleichnishafte Beispiele werden die Problemstellungen motiviert und die Ergebnisse der Arbeit in den gr6Beren Rahmen des Distributed Computing eingeordnet.
1 Einleitung.- 1.1 Verteilte Systeme.- 1.2 Prozesse und Ereignisse.- 1.3 Synchronisation und Kommunikation.- 1.4 Programmiersprachen für verteilte Systeme.- 1.5 Verteilte Algorithmen.- 1.6 Ausblick auf die weiteren Kapitel.- 2 Untersuchung von Election-Algorithmen.- 2.1Das Election-Problem.- 2.2 Ringbasierte Election-Verfahren.- 2.3 Election-Algorithmen für andere Topologien.- 3 Das Schnappschußproblem.- 3.1 Konsistente globale Zustände.- 3.2 Das Schnappschußprinzip.- 3.3 Zwei symmetrische Schnappschußalgorithmen.- 3.4 Basisalgorithmen als Bausteine.- 3.5 Konsistenz durch 'Einfrieren'.- 4 Verteilte Terminierung.- 4.1 Einleitung.- 4.2 Ein Beispiel - verteiltes Lösen von krypto-arithmetischen Rätseln.- 4.3 Der Terminierungsbegriff.- 4.4 Eine Analyse des Terminierungsproblems.- 4.5 Charakteristika von Terminierungsalgorithmen.- 4.6 Verfahren mit zwei Wellen.- 4.7 Zeitzonenverfahren.- 4.8 Die Vektormethode.- 4.9 Die Kreditmethode.- 4.10 Empirische Effizienzmessungen.- 5 Virtuelle Zeit in verteilten Systemen.- 5.1 Zeitdiagramme und Kausalitätsstruktur.- 5.2 Realzeit.- 5.3 Virtuelle Zeit.- 5.4 Vektorzeit.- 5.5 Stichzeitpunkt und Schnappschuß.- 6 Schlußbemerkungen.- Anhang - Meßergebnisse allgemeiner Election-Algorithmen.- Literatur.
Friedemann Mattern ist seit 1999 an der ETH Zürich als Leiter des Fachgebiets Verteilte Systeme" tätig; im Oktober 2002 gründete er dort das Institut für Pervasive Computing. Mattern studierte Informatik in Bonn und promovierte an der Universität Kaiserslautern. Zwischen 1991 und 1999 hatte er Professuren an der Universität des Saarlandes und an der Technischen Universität Darmstadt inne. Er ist an mehreren Industriekooperationen und Forschungsprojekten zum Thema Ubiquitous und Pervasive Computing beteiligt und ist Mitbegründer des von der ETH Zürich und der Universität St. Gallen gemeinsam getragenen M-Lab-Kompetenzzentrums, das die betriebswirtschaftlichen Auswirkungen des Ubiquitous Computing erforscht.
Inhaltsverzeichnis
1 Einleitung.- 1.1 Verteilte Systeme.- 1.2 Prozesse und Ereignisse.- 1.3 Synchronisation und Kommunikation.- 1.3.1 Synchronisation.- 1.3.2 Kommunikation.- 1.4 Programmiersprachen für verteilte Systeme.- 1.4.1 Verteilte Programmiersprachen.- 1.4.2 Objektorientierte Parallelität, Actor-Modell und Atommodell.- 1.4.3 Die Sprache CSSA.- 1.4.4 Ein verteiltes Beispielprogramm.- 1.5 Verteilte Algorithmen.- 1.5.1 Beobachtungen am ggT-Beispiel.- 1.5.2 Verteilte Kontrollalgorithmen.- 1.5.3 Der Echo-Algorithmus.- 1.6 Ausblick auf die weiteren Kapitel.- 2 Untersuchung von Election-Algorithmen.- 2.1Das Election-Problem.- 2.1.1 Eine Übersicht bekannter Election-Algorithmen.- 2.1.2 Simulationsexperimente: Zufallszahlen und Versuchsmethode.- 2.2 Ringbasierte Election-Verfahren.- 2.2.1Election auf unidirektionalen Ringen.- 2.2.1.1 Eine Anwendung: Das Token-Ring-Protokoll.- 2.2.1.2 Nachrichtenkomplexität des unidirektionalen Verfahrens.- 2.2.2 Election auf bidirektionalen Ringen.- 2.2.2.1 Ein probabilistischer Algorithmus.- 2.2.2.2 Deterministische Varianten.- 2.2.2.3 Eine experimentelle Analyse des Koeffizienten c.- 2.2.3 Der Einfluß nicht-konstanter Nachrichtenlaufzeiten.- 2.3 Election-Algorithmen für andere Topologien.- 2.3.1 Election auf Bäumen.- 2.3.2 Election auf allgemeinen Netzen.- 2.3.2.1 Problematik der Bewertung allgemeiner Election-Algorithmen.- 2.3.2.2 Die allgemeinen Election-Verfahreh.- 2.3.2.3 Repräsentative beliebige Netze.- 2.3.2.4 Experimentelle Untersuchung allgemeiner Election-Verfahren.- 3 Das Schnappschußproblem.- 3.1 Konsistente globale Zustände.- 3.2 Das Schnappschußprinzip.- 3.3 Zwei symmetrische Schnappschußalgorithmen.- 3.4 Basisalgorithmen als Bausteine.- 3.5 Konsistenz durch ¿Einfrieren¿.- 4 Verteilte Terminierung.- 4.1 Einleitung.- 4.1.1 Das Märchen von der verteilten Terminierung.- 4.2 Ein Beispiel ¿ verteiltes Lösen von krypto-arithmetischen Rätseln.- 4.2.1 Verteiltes Problemlösen.- 4.2.2 Sequentielle und parallele Lösungsansätze.- 4.2.3 Backtracking und Erkennung der Terminierung.- 4.2.4 Weitere Aspekte.- 4.3 Der Terminierungsbegriff.- 4.3.1 Ergebnisorientierte Terminierung.- 4.3.2 Kommunikationsorientierte Terminierung.- 4.4 Eine Analyse des Terminierungsproblems.- 4.4.1 Einfaches Zählen genügt nicht.- 4.4.2 Das Problem bei synchroner Kommunikation.- 4.5 Charakteristika von Terminierungsalgorithmen.- 4.5.1 Basisprinzipien.- 4.5.2 Eigenschaften, Mericmale und Kriterien.- 4.6 Verfahren mit zwei Wellen.- 4.6.1 Das Doppelzählverfahren.- 4.6.2 Der skeptische Algorithmus.- 4.6.3 Election-basierte Terminierungsalgorithmen.- 4.7 Zeitzonenverfahren.- 4.7.1 Eine symmetrische ringbasierte Version.- 4.7.2 Eine sternförmige Version mit beschränkter Zahl von Zeitzonen.- 4.7.3 Ein effizienter Terminierungstest für synchrone Kommunikation.- 4.7.3.1 Der DFG-Algorithmus.- 4.7.3.2 Eine effiziente Variante.- 4.7.3.3 Eine Realisierung in CSP.- 4.7.3.4 Bemerkungen zu synchronen Lösungen und CSP.- 4.8 Die Vektormethode.- 4.8.1 Der Revisor.- 4.8.2 Das Prinzip.- 4.8.3 Varianten.- 4.9 Die Kreditmethode.- 4.9.1 Eine Realisierung der Kreditmethode.- 4.9.2 Eine Variante.- 4.9.3 Optimierungen und weitere Varianten.- 4.10 Empirische Effizienzmessungen.- 4.10.1 Messungen am Zahlenrätselprogramm.- 4.10.2 Messungen mit synthetischen Benchmarkprogrammen.- 5 Virtuelle Zeit in verteilten Systemen.- 5.1 Zeitdiagramme und Kausalitätsstruktur.- 5.2 Realzeit.- 5.3 Virtuelle Zeit.- 5.4 Vektorzeit.- 5.4.1 Die Struktur der Vektorzeit.- 5.4.2 Die Analogie zu Minkowski¿s Raumzeit.- 5.4.3 Anwendungsmöglichkeiten der Vektorzeit.- 5.5 Stichzeitpunkt und Schnappschuß.- 6 Schlußbemerkungen.- Anhang ¿ Meßergebnisse allgemeiner Election-Algorithmen.- Literatur.
Klappentext
Problemstellungen motiviert und die Ergebnisse der Arbeit in den gr6Beren Rahmen des Distributed Computing eingeordnet.
