Proposition - Erkennen veralteter Datenstände in verteilten Systemen

• Involvierte Definitionen:
  • Lamport Vector Clock
  • siehe auch Erkennen von Inkonsistenzen in verteilten Systemen
• Veranstaltung: DEDS
• Referenz: @storl2024 (KE6, NoSQL: Datenmodelle und Techniken; Teil 2.5)

⠀

Proposition: Erkennen veralteter Datenstände in verteilten Systemen

Seien Knoten mit jeweiligen Vector Clocks und gegeben.

Ist das System in einem konsistenten Zustand (keine parallelen Transaktionen), so erhalten wir den Node mit dem aktuellsten Datenstand durch

Wir wählen also denjenigen Node , dessen eigene Lamport-Uhr den höchsten Wert enthält.

Anmerkung

Beispiel: Vector Clock

Seien die Vector-Clocks der Knoten gegeben durch

Wir sprechen nun das folgende Beispiel durch:

Erste Transaktion

Wir starten mit einer Transaktion an dem Knoten und setzen

Dieses Update wird nun an die Knoten propagiert und wir setzen nun auch

Zweite Transaktion

Nun erhält der Knoten eine Transaktion. Wir setzen daher

Das Update wird nun an und propagiert:

Dritte Transaktion

Nun erhält der Knoten eine Transaktion. Wir setzen daher

und propagieren das Update wieder

Vierte Transaktion

Der Knoten erhält eine Transaktion. Wir setzen daher

und propagieren das Update weiter

Fünfte Transaktion und read

Der Knoten erhält eine Transaktion. Wir setzen daher

Bevor wir das Update jedoch propagieren können, erhalten Knoten und Knoten jeweils eine read-Anfrage.

Das System kann nun durch einen Abgleich der Vector Clocks und erkennen, dass der Knoten einen aktuelleren Stand als der Knoten hat.