Konsistenzerhaltung

Zweck und Grundproblem

Konsistenzerhaltung (englisch: consistency control) bezeichnet in der Informatik Verfahren, die bei der Ausführung von Operationen in verteilten Systemen übereinstimmende Zustände sichern sollen. Sie ist ein Teil der Synchronisation; im Bereich Computer Supported Cooperative Work wird sie durch Late-Join ergänzt.

Das Grundproblem entsteht, wenn mehrere Teilsysteme mit identischen Anfangszuständen fast gleichzeitig dasselbe Datum verändern. Eine solche Veränderung heißt Operation. Betreffen zwei Operationen dasselbe Datum, sind sie konfliktär. Wegen der Übertragungsverzögerung können die Teilsysteme die Operationen in unterschiedlicher Reihenfolge oder zu unterschiedlichen Zeitpunkten ausführen. Dadurch können ihre Zustände voneinander abweichen. Für die Konsistenzerhaltung sind deshalb sowohl die Ausführungsreihenfolge als auch der Ausführungszeitpunkt wichtig.

Kriterien für diskrete Operationen

Bei einer Operation muss zwischen ihrem Erzeugungszeitpunkt und ihrem Ausführungszeitpunkt unterschieden werden. Eine Operation ist von einer anderen abhängig, wenn sie logisch nach dieser ausgeführt werden muss. Operationen ohne solche Abhängigkeit heißen nebenläufig.

Kausalität liegt vor, wenn jede abhängige Operation bei allen Instanzen erst nach der Operation ausgeführt wird, von der sie abhängt. Dieses Kriterium allein erhält die Konsistenz noch nicht vollständig, weil es keine Reihenfolge für nebenläufige Operationen festlegt.

Konvergenz bedeutet: Alle Instanzen führen dieselbe Menge von Operationen aus und erreichen schließlich denselben Zustand. Das ist stärker als Kausalität, erlaubt aber weiterhin unterschiedliche Zwischenzustände.

Korrektheit wird anhand einer gedachten „perfekten Instanz“ definiert, die jede Operation bereits zum Zeitpunkt ihrer Erzeugung ausführt. Nach einer Menge von Operationen müssen alle wirklichen Instanzen denselben Endzustand wie diese perfekte Instanz besitzen. Absolut gleichzeitig erzeugte Operationen werden durch ein Tie-Break-Kriterium eindeutig hintereinander angeordnet. Korrektheit ist das stärkste der drei Kriterien und schließt Konvergenz ein.

Zustandsvektoren und Reihenfolge

Zur technischen Umsetzung werden Zustandsvektoren verwendet. Beim Erzeugen einer Operation erhält sie einen Vektor, der für jede Instanz eine Sequenznummer enthält. Diese Nummer zeigt, welche Operationen die betreffende Instanz bis dahin bereits ausgeführt hat. Der Vektor beschreibt somit die Zustände aller Instanzen zum Erzeugungszeitpunkt und wird zusammen mit der Operation übertragen. Auch jede Instanz verwaltet einen eigenen Zustandsvektor.

Eine empfangene Operation ist kausal ausführbar, wenn zwei Bedingungen gelten: Die Sequenznummer der erzeugenden Instanz ist im empfangenen Vektor genau um 1 größer als im eigenen Vektor; zugleich sind alle übrigen empfangenen Sequenznummern kleiner oder gleich den entsprechenden eigenen Nummern. Dann bleibt die Kausalität bei der Ausführung erhalten.

Für die Korrektheit wird zusätzlich eine Kleiner-als-Relation festgelegt. Dazu vergleicht man die Summen aller Sequenznummern zweier Zustandsvektoren. Die Operation mit der kleineren Summe gilt als kleiner. Bei gleicher Summe entscheidet ein Tie-Break-Kriterium, beispielsweise anhand der Identifikationsnummern der beteiligten Instanzen. Diese Relation umfasst automatisch auch die kausale Abhängigkeit: Ist eine Operation kleiner als eine andere, ist die zweite von der ersten abhängig.

Die Relation ordnet die Operationen so, wie die perfekte Instanz sie ausführen würde. Eine wirkliche Instanz wahrt die Korrektheit, wenn sie nach allen bisherigen Operationen den Zustand besitzt, der sich aus dieser festgelegten Reihenfolge ergibt.

Kontinuierliche Vorgänge

Die beschriebene Umsetzung ist zunächst für diskrete Anwendungen gedacht, bei denen kein zeitlicher Ablauf innerhalb eines Vorgangs berücksichtigt werden muss. Bei kontinuierlichen Vorgängen ist dagegen auch entscheidend, wann eine Operation ausgeführt werden soll.

Konsistenz bedeutet hier: Zu einem bestimmten Zeitpunkt befinden sich alle Instanzen im gleichen Endzustand, nachdem sie sämtliche Operationen empfangen haben, deren Ausführungszeitpunkt davor liegt. Dieses Kriterium ist schwach, weil es zeitweise verschiedene Zwischenzustände erlaubt und weder die tatsächliche Reihenfolge noch den tatsächlichen Zeitpunkt der Ausführung festlegt.

Korrektheit wird erneut mithilfe einer perfekten Instanz bestimmt, die jede Operation zu deren Ausführungszeitpunkt ausführt. Nachdem alle Operationen mit früherem Ausführungszeitpunkt eingetroffen sind, müssen alle Instanzen denselben Zustand wie diese perfekte Instanz besitzen. Korrektheit ist auch hier das stärkste Kriterium und erfüllt laut Artikel zugleich das Kriterium Konvergenz.

Bei guten Uhren sollten absolut gleichzeitig erzeugte Operationen nicht vorkommen. Falls dies doch geschieht, kann erneut ein Tie-Break-Kriterium eine eindeutige Reihenfolge herstellen. Kausalität ist bei kontinuierlichen Vorgängen weniger wichtig und dient vor allem dazu, grobe Fehler zu vermeiden, etwa die Veränderung eines Objekts, bevor dieses erzeugt wurde.

Beispiele und Grenzen

Das Problem lässt sich an einem Internet-Strategiespiel zeigen: Hans schießt auf Peter, während Peter gleichzeitig ausweicht. Wegen der Netzwerkverzögerung sieht Hans den Schuss zuerst als Treffer und erst danach Peters Flucht. Peter verarbeitet dagegen zuerst sein Ausweichmanöver und anschließend den Schuss. Die beiden Rechner führen dieselben Operationen in umgekehrter Reihenfolge aus und zeigen daher unterschiedliche Ergebnisse.

Selbst formal korrekt angewandte Verfahren können den inhaltlichen Sinn von Operationen nicht erkennen. Deshalb können vorübergehend inkonsistente Zustände auftreten; dies heißt temporäre Inkonsistenz. Nimmt ein Benutzer sie wahr, spricht man von Artefakten. Ein Beispiel sind „springende“ Spielfiguren, wenn verspätet eingetroffene Operationen nachträglich in den Spielablauf eingefügt werden.

Artefakte können außerdem sekundäre Inkonsistenzen verursachen: Ein Benutzer entscheidet aufgrund fehlerhafter oder veralteter Informationen anders, als er bei korrekter Information entschieden hätte. Ein Spieler könnte beispielsweise anders reagieren, wenn er wüsste, dass sein Gegner bereits vor ihm steht. Konsistenzerhaltung kann Zustände und Operationsreihenfolgen also formal koordinieren, verhindert aber nicht automatisch alle für Menschen sinnlosen oder irreführenden Situationen.