Chandy-Lamport-Algorithmus
# 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:

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

