Logische Uhren, Konsens, Quoren und Konsistenzmodelle: So lernst du Verteilte Systeme in der richtigen Reihenfolge und bestehst die Klausur.

"In verteilten Systemen ist ein Timeout immer eine Vermutung, nie ein Beweis."
Verteilte Systeme ist das Modul, in dem dein bisheriges Programmierwissen plötzlich nicht mehr trägt. Eine Funktion, die lokal immer funktioniert, kann über das Netz halb ausgeführt werden, doppelt ankommen oder in einer Reihenfolge eintreffen, die niemand vorgesehen hat. Dazu gibt es keine gemeinsame Uhr und keinen Beobachter, der den Gesamtzustand kennt. Genau daraus entsteht der Stoff: ein paar Unmöglichkeitsergebnisse, eine Handvoll Verfahren, die trotzdem funktionieren, und Rechenaufgaben, die sich sauber üben lassen. Dieser Leitfaden ordnet beides und zeigt dir, worauf die Klausur hinausläuft.
Drei Eigenschaften unterscheiden ein verteiltes System von einem Einzelrechner, und fast jede Prüfungsfrage hängt an einer davon:
Dass dieses Zusammenspiel keine Schlamperei im Entwurf ist, sondern eine harte Grenze, zeigt das bekannteste Unmöglichkeitsergebnis des Fachs: Fischer, Lynch und Paterson haben 1985 bewiesen, dass es in einem asynchronen System kein deterministisches Protokoll gibt, das garantiert zu einer Einigung kommt, sobald auch nur ein Prozess ausfallen darf. Merk dir die Aussage präzise, denn sie wird in Klausuren gern falsch zitiert: Verboten ist nicht die Einigung, sondern die Garantie, dass das Verfahren in jedem Fall terminiert.
Praktisch heißt das: Du lernst in diesem Modul nicht Lösungen, die alles können, sondern Verfahren mit klar benannten Annahmen. Bei jeder Technik solltest du drei Fragen beantworten können — welches Fehlermodell wird vorausgesetzt, welche Zeitannahme, und was wird im schlimmsten Fall aufgegeben.
Weil es keine verlässliche gemeinsame Zeit gibt, ersetzt die Vorlesung physikalische Zeit durch Kausalität. Leslie Lamport hat dafür 1978 die Grundlage gelegt: Die Relation „happened before" ordnet nur solche Ereignisse, die sich tatsächlich beeinflussen können, und erzeugt damit eine partielle Ordnung. Mit Zeitstempeln lässt sich daraus eine totale Ordnung bauen, die der Kausalität nicht widerspricht.
Die Regeln sind klein genug, um sie in der Klausur aus dem Kopf anzuwenden: Jeder Knoten zählt bei jedem lokalen Ereignis seinen Zähler um eins hoch. Jede Nachricht trägt diesen Zählerstand mit. Beim Empfang setzt der Knoten seinen Zähler auf das Maximum aus eigenem und empfangenem Wert und zählt dann um eins weiter. Das garantiert: Wenn a kausal vor b liegt, ist der Zeitstempel von a kleiner.
Die typische Fehlerquelle ist die Umkehrung. Aus einem kleineren Zeitstempel folgt nicht, dass das Ereignis kausal früher war — es kann genauso gut gleichzeitig (konkurrent) gewesen sein. Genau diese Rückrichtung wird in Aufgaben abgefragt.
Willst du Gleichzeitigkeit erkennen, brauchst du mehr Information: Jeder Knoten führt einen Vektor mit einem Zählerstand pro Knoten. Zwei Ereignisse sind konkurrent, wenn keiner der beiden Vektoren komponentenweise kleiner oder gleich dem anderen ist. Damit wird die Kausalität vollständig abgebildet, der Preis ist Speicher- und Nachrichtenaufwand proportional zur Knotenzahl.
Übe diesen Teil ausschließlich am Zeit-Weg-Diagramm: Knoten als waagerechte Linien, Nachrichten als Pfeile, dann Zeitstempel eintragen und die konkurrenten Paare markieren. Wer das zehnmal gezeichnet hat, verliert in der Prüfung keine Punkte mehr daran.
Konsens heißt: Mehrere Knoten einigen sich auf einen Wert, obwohl einzelne ausfallen können. Lamport hat mit Paxos ein Verfahren beschrieben, das in genau dieser Lage sicher zu einer Einigung kommt, und später mit „Paxos Made Simple" eine zugänglichere Darstellung nachgelegt. Diego Ongaro und John Ousterhout haben 2014 mit Raft einen Algorithmus vorgestellt, der dieselbe Aufgabe löst, sich aber in drei klar getrennte Teile zerlegen lässt: Leaderwahl, Log-Replikation und Sicherheitsbedingungen. Ihre Nutzerstudie zeigte, dass Studierende Raft leichter lernen als Paxos — wenn deine Vorlesung beides behandelt, ist Raft darum der bessere Einstieg, um die Struktur zu verstehen.
Der rechnerische Kern ist die Quorenarithmetik, und sie ist klausurtauglich kurz:
| Fehlermodell | Verhalten des fehlerhaften Knotens | Nötige Knotenzahl für f Fehler |
|---|---|---|
| Crash (fail-stop) | Knoten hält an und antwortet nicht mehr | 2f + 1 (Mehrheitsquorum) |
| Byzantinisch, mündliche Nachrichten | Knoten darf beliebig falsch und widersprüchlich antworten | 3f + 1 (mehr als zwei Drittel loyal) |
| Byzantinisch, signierte Nachrichten | wie oben, Nachrichten aber fälschungssicher | prinzipiell für jede Anzahl lösbar |
Die beiden byzantinischen Zeilen gehen auf Lamport, Shostak und Pease (1982) zurück: Mit rein mündlichen Nachrichten ist das Problem nur lösbar, wenn mehr als zwei Drittel der Beteiligten loyal sind; mit unfälschbaren schriftlichen Nachrichten fällt diese Schranke weg. Wenn in einer Aufgabe „3f + 1" verlangt wird, ist das Fehlermodell byzantinisch — bei reinen Crash-Ausfällen genügt die Mehrheit.
Dazu kommt die Abgrenzung zum Zwei-Phasen-Commit, die fast immer geprüft wird: 2PC ist ein Atomaritätsprotokoll, kein Konsensverfahren. Es blockiert, wenn der Koordinator nach dem Prepare ausfällt, weil die Teilnehmer dessen Entscheidung nicht rekonstruieren können. Konsensverfahren wie Raft lösen genau das, indem die Entscheidung selbst replizierbar wird.
Replikation macht ein System verfügbar und schnell — und bringt die Frage mit, was ein Lesezugriff danach noch garantiert. Seth Gilbert und Nancy Lynch haben 2002 Brewers CAP-Vermutung für das asynchrone Netzmodell bewiesen: Konsistenz, Verfügbarkeit und Partitionstoleranz sind nicht gleichzeitig erreichbar. Wichtig für die mündliche Prüfung ist die saubere Lesart. CAP ist keine Auswahl „zwei von drei", die man sich beim Entwurf aussucht; Partitionen passieren unabhängig von deinem Willen, und die Entscheidung fällt erst während einer Partition — konsistent antworten oder überhaupt antworten.
| Modell | Garantie | Preis |
|---|---|---|
| Linearisierbar | Alle sehen eine einzige, zeitlich plausible Reihenfolge | Koordination bei jedem Zugriff, Verfügbarkeitsverlust bei Partition |
| Kausal | Kausal abhängige Operationen sieht jeder in derselben Reihenfolge | Konkurrente Schreibzugriffe müssen zusammengeführt werden |
| Eventual | Ohne neue Schreibzugriffe konvergieren alle Replikate | Zwischenzeitlich veraltete Lesewerte |
Die zugehörige Rechenregel für Quorumsysteme lautet R + W > N: Lese- und Schreibquorum müssen sich überlappen, damit ein Lesezugriff den letzten Schreibzugriff sieht. Daraus baust du in Aufgaben beliebige Varianten — W = N macht Schreiben teuer und Lesen billig, R = 1 umgekehrt.
Die Prüfungsform hängt am Modulhandbuch, und die Spannweite ist groß. Im Modul 63211 „Verteilte Systeme" der FernUniversität in Hagen etwa findet die Prüfung im Wintersemester als zweistündige Präsenzklausur statt, im Sommersemester als mündliche Prüfung von rund 25 Minuten — dieselbe Stoffliste, zwei völlig verschiedene Vorbereitungen. Prüf deshalb zuerst, welche Form bei dir gilt: Eine Klausur belohnt eingeübte Rechenwege, eine mündliche Prüfung belohnt die Fähigkeit, Annahmen und Grenzen eines Verfahrens zu benennen.
Diese Aufgabentypen kommen in beiden Formen wieder:
Rechne diese Typen an Altklausuren, nicht an Folien. Der Stoff fühlt sich beim Lesen verständlich an und bricht genau dann zusammen, wenn du ein Diagramm selbst zeichnen musst — der Abstand zwischen „nachvollziehen" und „selbst herleiten" ist in diesem Modul größer als in jedem anderen. Abrufübungen statt Wiederlesen sind hier deshalb nicht nur eine nette Lerntechnik, sondern der Unterschied zwischen bestehen und nicht bestehen.
Der Stoff baut streng aufeinander auf: Ohne Fehlermodelle verstehst du Konsens nicht, ohne Kausalität keine Konsistenzmodelle. Arbeite deshalb in dieser Reihenfolge.
| Phase | Fokus | Woran du merkst, dass es sitzt |
|---|---|---|
| Semesterbeginn | Systemmodelle, Fehlermodelle, Zeitannahmen | Du kannst zu jedem Verfahren sagen, welches Fehlermodell es voraussetzt |
| Mitte | Logische und Vektoruhren, gegenseitiger Ausschluss, Wahlverfahren | Du zeichnest Zeit-Weg-Diagramme ohne Vorlage |
| Spätes Semester | Konsens (Paxos, Raft), Replikation, Konsistenzmodelle | Du erklärst Raft in drei Teilen, ohne auf Folien zu schauen |
| Klausurphase | Altklausuren, Quorenrechnen, Abgrenzungsfragen | Du erkennst den Aufgabentyp in zehn Sekunden |
Zwei Nachbarmodule helfen dir dabei direkt weiter: Netzgrundlagen und Protokollschichten gehören in den Rechnernetze-Guide mit OSI, TCP/IP und Subnetting, und die Beweistechnik für Unmöglichkeitsargumente übst du am besten mit der Theoretischen Informatik mit Beweisen und Automaten. Transaktionen und Isolationsstufen, die bei Replikation wieder auftauchen, stehen im Datenbanken-Guide zu ER-Modell, Normalisierung und SQL; Prozesse, Scheduling und Synchronisation im Betriebssysteme-Guide. Als Lehrbuch nutzt du sinnvollerweise van Steen und Tanenbaum, „Distributed Systems" in der vierten Auflage — die digitale Fassung stellen die Autoren kostenlos bereit, und viele Modulbeschreibungen nennen sie als Basistext.
Für die Wiederholung lohnt sich ein festes Intervallsystem: Definitionen und Fehlermodelle gehören auf Karten, die du nach dem Prinzip geplanter Wiederholungsintervalle abfragst, während die Rechenwege Übungsblätter brauchen. Wenn du aus Vorlesungsfolien und Skript schnell abfragbares Material machen willst, kann dir Learnboost beim Lernplan und den Karteikarten die Fleißarbeit abnehmen — den Teil, der wirklich zählt, nämlich das selbstständige Herleiten am Diagramm, ersetzt dir kein Werkzeug.
Eine Lamport-Uhr ist ein einzelner Zähler pro Knoten und garantiert nur eine Richtung: Liegt Ereignis a kausal vor b, dann ist der Zeitstempel von a kleiner. Die Umkehrung gilt nicht — aus einem kleineren Zeitstempel folgt nicht, dass das Ereignis früher war, es kann auch konkurrent gewesen sein. Vektoruhren führen dagegen einen Zählerstand pro Knoten und bilden die Kausalität vollständig ab: Zwei Ereignisse sind genau dann konkurrent, wenn keiner der Vektoren komponentenweise kleiner oder gleich dem anderen ist. Der Preis ist Aufwand proportional zur Knotenzahl.
Seth Gilbert und Nancy Lynch haben 2002 bewiesen, dass im asynchronen Netzmodell Konsistenz, Verfügbarkeit und Partitionstoleranz nicht gleichzeitig garantiert werden können. Die verbreitete Lesart „wähle zwei von drei" ist irreführend: Netzpartitionen passieren unabhängig von deinem Entwurf, du kannst sie nicht abwählen. Die Entscheidung fällt erst während einer Partition, und sie lautet: konsistent antworten oder überhaupt antworten. Außerhalb von Partitionen kannst du beides haben.
Das Ergebnis von Fischer, Lynch und Paterson aus 1985 verbietet nicht die Einigung, sondern die Garantie: In einem asynchronen System kann kein deterministisches Protokoll zusichern, dass es bei einem möglichen Prozessausfall immer terminiert. Paxos und Raft sind deshalb sicher, aber nicht unter allen Umständen terminierungsgarantiert — sie einigen sich korrekt und kommen in der Praxis zum Ergebnis, sobald das Netz sich hinreichend gutartig verhält. Diese Unterscheidung zwischen Sicherheit und Lebendigkeit ist eine klassische Prüfungsfrage.
Bei reinen Crash-Ausfällen genügt ein Mehrheitsquorum, also 2f + 1 Knoten für f Ausfälle: Fünf Knoten überleben zwei Ausfälle. Dürfen fehlerhafte Knoten beliebig falsch und widersprüchlich antworten (byzantinisches Fehlermodell), brauchst du bei rein mündlichen Nachrichten mehr als zwei Drittel loyale Teilnehmer, also 3f + 1 Knoten — das haben Lamport, Shostak und Pease 1982 gezeigt. Mit unfälschbaren signierten Nachrichten entfällt diese Schranke. Steht in einer Aufgabe 3f + 1, ist das Fehlermodell byzantinisch.
Zuerst klären, welche Prüfungsform gilt, denn sie unterscheidet sich je Hochschule stark. Im Modul 63211 der FernUniversität in Hagen ist es im Wintersemester eine zweistündige Präsenzklausur und im Sommersemester eine mündliche Prüfung von etwa 25 Minuten. Eine Klausur belohnt eingeübte Rechenwege wie Zeitstempel und Quoren, eine mündliche Prüfung die Fähigkeit, Annahmen und Grenzen eines Verfahrens zu benennen. In beiden Fällen gilt: Zeichne Zeit-Weg-Diagramme selbst, statt Folien zu lesen.