Linearisierbarkeit (englisch Linearizability) ist das stärkste Konsistenzmodell für einzelne gemeinsam genutzte Objekte. Maurice Herlihy und Jeannette Wing führten sie 1990 in dem Papier „Linearizability: A Correctness Condition for Concurrent Objects" (ACM Transactions on Programming Languages and Systems, Band 12, Heft 3) als Korrektheitsbedingung für nebenläufige Datenstrukturen ein.
Kernidee: Der Linearisierungspunkt
Ein Objekt ist linearisierbar, wenn sich jede überlappende Ausführung so deuten lässt, als wäre jede Operation an einem einzigen Punkt zwischen Aufruf und Antwort atomar wirksam geworden — dem Linearisierungspunkt. Das Gesamtergebnis entspricht einer gültigen sequentiellen Ordnung aller Operationen, als hätte es keine Überlappungen gegeben.
Realzeit-Bedingung
Entscheidend ist die Echtzeit-Bedingung: Ist Operation A vollständig abgeschlossen, bevor Operation B startet, dann muss A in der linearen Ordnung vor B stehen. Genau diese Bindung an die reale Zeit unterscheidet Linearisierbarkeit von Sequential Consistency, die nur eine gemeinsame Gesamtordnung verlangt, ohne abgeschlossene Operationen vor später gestarteten zu priorisieren.
Praktische Eigenschaften
- Lokalität: Linearisierbarkeit ist lokalkomponierbar — ist jedes einzelne Objekt linearisierbar, dann auch das Gesamtsystem. Das erlaubt modulare Verifikation nebenläufiger Programme.
- Praxis: Atomare Register, wartefreie und sperrfreie Warteschlangen und Stacks, konsistente Hashtabellen; Testwerkzeuge wie Jepsen prüfen Linearisierbarkeit realer Systeme.
- Kosten: Die strenge Ordnung braucht einen globalen Synchronisationspunkt und ist teuer — viele verteilte Systeme relaxieren zu Modellen wie Weak Consistency, Kausale Konsistenz oder Eventual Consistency.
Abgrenzung zu Serialisierbarkeit und SQL
In Datenbanken entspricht strikte Serialisierbarkeit der Linearisierbarkeit (Serialisierbarkeit plus Echtzeit-Bedingung). Die klassischen SQL-Isolationsebenen Read Committed und Repeatable Read liegen deutlich darunter; Snapshot Isolation verhindert zwar viele Anomalien, ist aber nicht serialisierbar. Im CAP-Theorem steht Linearisierbarkeit auf der Konsistenz-Seite, während Konsens (etwa Raft oder Paxos) die technische Grundlage für strikte Ordnung in verteilten Systemen bildet — mehr dazu unter Verteilte Systeme. Starke Konsistenz ist der Oberbegriff, dessen strengste Ausprägung die Linearisierbarkeit ist.