Schnappschussalgorithmus

Unter Schnappschussalgorithmus oder auch Verteilte Momentaufnahme wird ein Verfahren verstanden, das zur Ermittlung eines globalen Zustands eines aktiven verteilten Systems dient. Es wurde von Leslie Lamport und K. Mani Chandy entwickelt und ist daher auch als Chandy-Lamport-Algorithmus bekannt.

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 Kommunikationspfad 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

Ablauf

Der Prozess, der den Schnappschussalgortihmus startet, erstellt einen Schnappschuss seines lokalen Zustandes und sendet eine Markierung an jeden fortführenden Kanal. Beim Empfang einer Markierungsnachricht ergeben sich zwei Möglichkeiten:

1. Beim Empfang der ersten Markierung speichert der Prozess seinen Zustand, sendet die Markierungsnachricht seinerseits an die fortführenden Kanäle weiter und beginnt mit der Aufzeichnung aller eingehenden Nachrichten.
2. Wenn bereits eine Markierung empfangen wurde, stoppt der Prozess die Aufzeichnung.

Durch dieses Verfahren werden sowohl die eigentlichen Zustände der Prozesse als auch Nachrichten zwischen einzelnen Prozessen aufgezeichnet.

Literatur

• Leslie Lamport, K. Mani Chandy: Distributed Snapshots: Determining Global States of a Distributed System. In: ACM Transactions on Computer Systems 3. Nr. 1, Februar 1985. (PDF; 1 MB).