Chandy-Lamport-Algorithmus

Der Chandy-Lamport-Algorithmus ist ein Schnappschussalgorithmus, d. h. ein Verfahren, das zur Ermittlung eines globalen Zustands eines aktiven verteilten Systems dient. Er wurde 1985 von Leslie Lamport und K. Mani Chandy entwickelt.

Annahmen

Für den 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 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).