Schnappschuss-Algorithmus

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

Wenn der Prozess, der den Schnappschuss ausgelöst hat, von allen anderen Prozessen wieder eine Markierung erhalten hat, weiß er, dass alle ihren Zustand aufgezeichnet haben und kann bei Bedarf die Resultate abholen.

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).