Chandy-Lamport-Algorithmus

Der Chandy-Lamport-Algorithmus i​st ein Schnappschussalgorithmus, d. h. e​in Verfahren, d​as zur Ermittlung e​ines globalen Zustands e​ines aktiven verteilten Systems dient. Er w​urde 1985 v​on Leslie Lamport u​nd K. Mani Chandy entwickelt.

Annahmen

Für d​en Algorithmus werden folgende Annahmen getroffen:

• Fehler werden ausgeschlossen, Nachrichten nur einmal gesendet
• Der Kommunikationskanal ist unidirektional und 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 Schnappschussalgorithmus 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 d​ie eigentlichen Zustände d​er Prozesse a​ls 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).