Schnappschussalgorithmus

Ein Schnappschussalgorithmus (engl.: snapshot algorithm), auch: verteilte Momentaufnahme, dient dazu, einen konsistenten Zustand eines verteilten Systems zu speichern. Da es im Allgemeinen keinen gemeinsamen Speicher und keine gemeinsame Zeit gibt, ist das nicht trivial möglich.

Beispiel

Mehrere Rechner arbeiten in einem verteilten System zusammen, jeder repräsentiert ein Konto. Es können durch Nachrichten Beträge von einem auf ein anderes Konto überwiesen werden.

Es soll die Summe der Kontostände ermittelt werden. Würde lediglich von jedem Rechner der Kontostand abgefragt, kann das Ergebnis falsch sein, wenn ein Rechner eine Überweisung losgeschickt (und damit seinen Kontostand erniedrigt) hat, diese aber noch nicht beim Empfänger angekommen ist. Ein Schnappschussalgorithmus löst solche Inkonsistenzen auf.

Bekannte Schnappschussalgorithmen

  • Chandy-Lamport-Algorithmus
  • Lai-Yang-Algorithmus
  • Spezialetti-Kearns-Algorithmus
  • Mattern-Algorithmus