Schnappschussalgorithmus
aus Wikipedia, der freien Enzyklopädie
Unter Schnappschussalgorithmus oder auch Verteilte Momentaufnahme wird ein Verfahren verstanden, das zur Ermittlung eines globalen Zustands eines aktiven verteilten Systems dient.
[Bearbeiten] Annahmen
Für den Algorithmus werden folgende Annahmen getroffen:
- Fehler werden ausgeschlossen, Nachrichten nur einmal gesendet
- Der Kommunikationskanal hat eine Richtung und ist nach dem FIFO-Prinzip geordnet
- Es gibt einen Kommunikationskanal zwischen beliebigen Paaren von Prozessen im System
- Ein beliebiger Prozess kann den Algorithmus auslösen
- Der Algorithmus hat keinen Einfluss auf die normale Ausführung des Prozesses
- Jeder Prozess im System zeichnet seinen lokalen Zustand und den Zustand herführender Kanäle auf
[Bearbeiten] Ablauf
Der Algorithmus verwendet Markierungsnachrichten. Jeder Prozess, der einen Schnappschuss auslöst, zeichnet seinen lokalen Zustand auf und sendet eine Markierung an alle fortführenden Kanäle. Den Empfängern wird dadurch kenntlich gemacht, dass sie ebenfalls an der Aufzeichnung des globalen Zustands teilnehmen sollen.
Die anderen Prozesse zeichnen nach Eintreffen einer Markierung ihren lokalen Zustand auf und senden Markierungen an alle fortführenden Kanäle.
Falls ein Prozess hingegen eine Nachricht erst nach der Aufzeichnung seines lokalen Zustands empfängt, zeichnet es den Zustand des herführenden Kanals auf, von dem die Markierung kam. Dieser Zustand setzt sich aus der Abfolge von Nachrichten zusammen, die vom Prozess empfangen wurden, seit zuletzt der eigene lokale Zustand aufgezeichnet wurde und bevor die Markierung empfangen wurde.
