Small logo of ETH main building ETH Zurich : Computer Science : Pervasive Computing : Distributed Systems : Research : Distributed Algorithms/Verteilte Algorithmen

Verteilte Algorithmen

Verteilte 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 Forschungsgebietes

Verteilte 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
Abstract --- Full Paper

[3] Friedemann Mattern : Distributed Termination Detection with Sticky State Indicators. Technical Report 200/90, Department of Computer Science, University of Kaiserslautern, Germany, 1990
Abstract --- Full Paper

[4] Friedemann Mattern : Global Quiescence Detection Based on Credit Distribution and Recovery. Information Processing Letters 30, pp. 195 - 200, 1989
Abstract --- Full Paper

[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
Abstract --- Full Paper

[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
Abstract --- Full Paper

[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
Abstract --- Full Paper

[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.)
Abstract --- Full Paper

[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
Abstract --- Full Paper

[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
Abstract --- Full Paper

[12] Friedemann Mattern, Jörg Richter und Horst Mehl : Leistungssteigerung ereignisgesteuerter Simulation durch Multi-Mikro-Rechnersysteme.
Technical Report No. A03/93, Department of Computer Science, University of Saarland, 1993 (Abschlussbericht zum gleichnamigen DFG-Projekt.)
Abstract --- Full paper

[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.)
Abstract --- Full Paper

[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
Abstract --- Full Paper

[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
Abstract

[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
Abstract --- Extended Abstract

[21] Tel G., Mattern F.: Comments on "Ring Based Termination Detection Algorithm for Distributed Computations". Information Processing Letters 31, pp. 127-128, 1989
Full Paper

[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
Abstract --- Full Paper

[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
Full Paper

ETH ZurichDistributed Systems Group
Last updated April 29 2011 11:03:10 AM MET hv