|
Verteilte AlgorithmenVerteilte Algorithmen sind Verfahren, die dadurch charakterisiert sind, dass mehrere autonome Prozesse gleichzeitig Teile eines gemeinsamen Problems in kooperativer Weise bearbeiten und der dabei erforderliche Informationsaustausch ausschliesslich über Nachrichten erfolgt.
Beschreibung des ForschungsgebietesVerteilte Algorithmen [17] kommen im Rahmen dezentraler Systeme zum Einsatz, bei denen kein gemeinsamer Speicher existiert und die Übertragungszeit von Nachrichten i.a. nicht vernachlässigt werden kann. Da dabei kein Prozess eine aktuelle konsistente Sicht des globalen Zustands besitzt, führt dies zu schwierigen, aber interessanten Problemen [20] [1].So ist es beispielsweise überraschenderweise nicht trivial, das Ende einer Berechnung auf einem derartigen System festzustellen [16] [18] [21] [22] [23] [24] [26] [3] [4]. Ein anderes Problem, das sowohl von theoretischer als auch praktischer Relevanz ist, stellt das Garbage-Collection-Problem in verteilten Systemen dar. Aufgrund der Parallelität der Objekte und der Tatsache, dass Referenzen in Nachrichten unterwegs sein können, ist es nicht leicht, hierfür einen guten Algorithmus zu finden. Interessanterweise ergibt sich bei näherer Analyse, dass diese beiden Probleme zusammenhängen: So lässt sich jeder Garbage-Collection-Algorithmus in mechanischer Weise in einen Algorithmus zur Erkennung der verteilten Terminierung transformieren [5]. Charakteristisch für verteilte Systeme ist das Fehlen einer exakten globalen Zeitbasis - tatsächlich ist das Synchronisieren verteilter Uhren mittels Nachrichten schwierig. Als Konsequenz daraus ist es in derartigen Systemen nicht nur problematisch, einen konsistenten Zustandsschnappschuss der zugrundeliegenden Berechnung im Sinne einer Momentaufnahme zu erhalten, sondern es gibt noch nicht einmal einen ausgezeichneten Beobachter, der die Gütigkeit gewisser Eigenschaften "zweifelsfrei" feststellen könnte - verschiedene Beobachter können diesbezüglich zu unterschiedlichen Ergebnissen kommen [6]. Dies hat unmittelbare Konsequenzen für das "Debuggen" und "Monitoring" verteilter Anwendungen. Um so interessanter ist daher die Charakterisierung von solchen Eigenschaften, die beobachterinvariant sind. Die Tatsache, dass verteilte Berechnungen als halbgeordnete Mengen von Ereignissen modelliert werden können, legt eine neue Interpretation des Zeitbegriffs als eine halbgeordnete Menge n-dimensionaler Vektoren mit Verbandsstruktur nahe [15] [7]. Dabei bekommen auch die "Alltagsbegriffe" zentraler oder synchroner Systeme wie "später", "gleichzeitig", "Uhrensynchronisation", "Stichzeitpunkt" etc. eine neue, verallgemeinerte, jedoch adäquate und anschauliche Interpretation. Mit diesem neuen - quasi relativistischen - Zeitbegriff, der eine gewisse formale Analogie zum Minkowski'schen Raum-Zeit Modell besitzt, lässt sich die Kausalitätsstruktur von Ereignissen in verteilten Systemen in isomorpher Weise repräsentieren. Eine mögliche Anwendung ist die Bestimmung paarweise unabhängiger Ereignisse, wodurch u.a. global konsistente Zustandsschnappschüsse ermittelt werden können [25] [9]. Ferner lassen sich mit dieser "Vektorzeit" kausaltreue Beobachter implementieren. Ein weiterer Anwendungsbereich dieses Zeitmodells stellt das Testen verteilter Programme dar. In diesem Zusammenhang spielt auch der Aspekt der Synchronität beim Nachrichtenaustausch eine wichtige Rolle. Es zeigt sich, dass sich die Begriffe "synchrone Kommunikation" und "asynchrone Kommunikation" mittels der Kausalitätsrelation zwischen Ereignissen formal definieren lassen, und dass im Spektrum zwischen synchroner und asynchroner Kommunikation diejenigen Berechnungen angesiedelt sind, die als "kausal geordnet" bezeichnet werden [10] [11]. Solche Berechnungen haben die Eigenschaft, dass die Kausalbeziehung zwischen Ereignissen (etwa durch indirekte Überholungen von Nachrichten) nicht verletzt werden. Ein typischer Anwendungsbereich verteilter Algorithmen ist auch die "verteilte Simulation" [19]: Zur Beschleunigung des Simulationsablaufs wird bei einem ereignisgesteuerten verteilten Simulationssystem das Simulationsmodell in mehrere miteinander kooperierende, jedoch weitgehend autonome Submodelle aufgeteilt, die jeweils durch einen eigenen Simulator bearbeitet werden [12]. Jeder Simulator besitzt seine eigene logische Simulationsuhr, welche asynchron zu den anderen Simulationsuhren in diskreten Schritten auf den Zeitpunkt des jeweils lokal nächsten zu simulierenden Ereignisses gesetzt wird. Das jeweilige globale Minimum aller Simulationsuhren ist von besonderem Interesse, da es den eigentlichen Fortgang der Simulation bestimmt und gestattet, nicht mehr benötigte Sicherungskopien für Rücksetzmaßnahmen zu löschen. Dieses Minimum ist eine monotone Funktion der Realzeit; es ist nicht einfach zu bestimmen, da es während des Simulationsablaufs sprunghaft den Ort wechselt. Es lässt sich allerdings zeigen, dass die Minimumsbestimmung (die sogenannte GVT-Approximation) mit dem Problem der Terminierungserkennung und dem Problem der konsistenten Schnappschussbestimmung eng verwandt ist, und sich daher entsprechende Lösungen adaptieren lassen [13] [14]. Die Beschäftigung mit verteilten Algorithmen führt nicht nur dazu, dass Lösungen für praktische und theoretische Probleme gefunden werden, sondern vermittelt auch geeignete Modellvorstellungen verteilter Abläufe. Dadurch erschließen sich einem grundlegende Einsichten in Phänomene und fundamentale Aspekte verteilter Systeme. Literatur: [1] [2] Friedemann Mattern :
Distributed Control Algorithms (Selected Topics).
In: F. Özguner, F. Ercal (Eds.): Parallel Computing on
Distributed
Memory Multiprocessors, Springer-Verlag, pp. 167 - 185, 1993 [3] Friedemann Mattern :
Distributed Termination Detection with Sticky State Indicators.
Technical Report 200/90, Department of Computer Science, University
of
Kaiserslautern, Germany, 1990 [4] Friedemann Mattern :
Global Quiescence Detection Based on Credit Distribution and
Recovery.
Information Processing Letters 30, pp. 195 - 200, 1989 [5] Gerard Tel and Friedemann Mattern :
The Derivation of Distributed Termination Detection Algorithms from
Garbage Collection Schemes.
ACM TOPLAS 15:1, pp. 1 - 35, January 1993
[6] Reinhard Schwarz and Friedemann Mattern :
Detecting Causal Relationships in Distributed Computations: In Search
of the Holy Grail.
Distributed Computing, Vol. 7 No. 3, pp. 149 - 174, 1994 [7] [8] Friedemann Mattern :
On the Relativistic Structure of Logical Time in Distributed
Systems.
In: Datation et Controle des Executions Reparties, Bigre 78 (ISSN
0221-525),
pp. 3 - 20, 1992 [9] [9a] Friedemann Mattern :
Virtual Time and Global States of Distributed Systems.
In: Cosnard M. et al. (eds): Proc. Workshop on Parallel and
Distributed Algorithms, North-Holland / Elsevier, pp. 215 - 226, 1989
(Reprinted in: Z. Yang, T.A. Marsland (eds.), "Global States and
Time in
Distributed Systems", IEEE, 1994, pp. 123 - 133.) [10] Bernadette Charron-Bost, Friedemann Mattern, and Gerard Tel
:
Synchronous, Asynchronous, and Causally Ordered Communication.
Distributed Computing, Vol. 9 No. 4, pp. 173 - 191, 1996 [11] Friedemann Mattern and Stefan Fünfrocken :
A Non-Blocking Lightweight Implementation of Causal Order Message
Delivery.
In: K.P. Birman, F. Mattern, A. Schiper (Eds.): Theory and Practice in
Distributed Systems, Springer-Verlag, LNCS 938, pp. 197 - 213, 1995
[12] Friedemann Mattern, Jörg Richter und Horst Mehl :
Leistungssteigerung ereignisgesteuerter Simulation durch
Multi-Mikro-Rechnersysteme.
[13] Friedemann Mattern :
Efficient Algorithms for Distributed Snapshots and Global Virtual
Time Approximation.
Journal of Parallel and Distributed Computing, Vol. 18,
pp. 423 - 434, August 1993
(Reprinted in: Z. Yang, T.A. Marsland (eds.), "Global States and
Time in
Distributed Systems", IEEE, 1994, pp. 27 - 36.) [14] Friedemann Mattern, Horst Mehl, Anneke A. Schoone, and
Gerard Tel :
Global Virtual Time Approximation with Distributed Termination
Detection Algorithms.
Technical Report RUU-CS-91-32, Department of Computer Science,
University of Utrecht, The Netherlands, 1991 [15] Mattern F.: Über die relativistische Struktur logischer Zeit in verteilten Systemen. In: J. Buchmann, H. Ganzinger, W.J. Paul (Hg.): Informatik - Festschrift zum 60. Geburtstag von Günter Hotz, Teubner, pp. 309-331, 1992 [16] Mattern F.: Asynchronous Distributed Termination - Parallel and Symmetric Solutions with Echo Algorithms. Algorithmica 5, pp. 325-340, 1990 [17]
Mattern F.:
Verteilte Basisalgorithmen.
Springer-Verlag, 1989 [18] Mattern F.: An Efficient Distributed Termination Detection Test. Information Processing Letters 31, pp. 203-208, 1989 [19] Mattern F., Mehl H.: Diskrete Simulation - Prinzipien und Probleme der Effizienzsteigerung durch Parallelisierung. Informatik-Spektrum 12:4, pp. 198-210, 1989 [20]
Mattern F.:
Message Complexity of Simple Ring-based Election
Algorithms - an Empirical Analysis.
Proc. 9th Int. Conf. Distributed
Computing Systems, pp. 94-100, 1989 [21]
Tel G., Mattern F.:
Comments on "Ring Based Termination
Detection Algorithm for Distributed Computations".
Information Processing
Letters 31, pp. 127-128, 1989 [22] Mattern F.: Experience with a New Distributed Termination Detection Algorithm. In: Van Leeuwen J. (ed) Proc. of the 2nd International Workshop on Distributed Algorithms, Springer-Verlag, LNCS 312, pp. 127-143, 1988 [23] Mattern F., Mohr R.: An Empirical Evaluation of a Class of Distributed Termination Detection Algorithms. Technical Report SFB124- 28/88, Department of Computer Science, University of Kaiserslautern, Germany, 1988 [24]
Mattern F.:
Algorithms for Distributed Termination Detection.
Distributed Computing 2:3, pp. 161-175, 1987 [25] Mattern F.: Effiziente Bestimmung von Schnappschüssen in verteilten Systemen. In: Paul M. (Hg.): GI - 17. Jahrestagung, Springer-Verlag, Informatik-Fachberichte 156, pp. 89-109, 1987 [26]
Mattern F.:
Das Märchen von der verteilten Terminierung.
Informatik-Spektrum 8:6, pp. 342-343, 1985 |
  |
