Verteilte Systeme lernen: Konsens, Replikation, Zeit

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

Verteilte Systeme lernen: Konsens, Replikation, Zeit

"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.

Warum verteilte Systeme eine eigene Denkweise brauchen

Drei Eigenschaften unterscheiden ein verteiltes System von einem Einzelrechner, und fast jede Prüfungsfrage hängt an einer davon:

  • Teilausfall: Ein einzelner Knoten fällt aus, der Rest läuft weiter. Es gibt also keinen Zustand „System an" oder „System aus", sondern beliebig viele Mischzustände.
  • Asynchronie: Nachrichten brauchen unbestimmt lange. Deshalb kannst du einen abgestürzten Knoten nicht von einem langsamen unterscheiden — ein Timeout ist immer eine Vermutung, kein Beweis.
  • Keine globale Zeit: Jeder Knoten hat seine eigene Uhr. Eine Aussage wie „A passierte vor B" ist ohne weitere Annahmen gar nicht definiert.

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.

Zeit und Ordnung: logische Uhren statt Armbanduhr

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.

Lamport-Uhren

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.

Vektoruhren

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 und Replikation: die Standardverfahren der Vorlesung

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:

FehlermodellVerhalten des fehlerhaften KnotensNötige Knotenzahl für f Fehler
Crash (fail-stop)Knoten hält an und antwortet nicht mehr2f + 1 (Mehrheitsquorum)
Byzantinisch, mündliche NachrichtenKnoten darf beliebig falsch und widersprüchlich antworten3f + 1 (mehr als zwei Drittel loyal)
Byzantinisch, signierte Nachrichtenwie oben, Nachrichten aber fälschungssicherprinzipiell 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.

Konsistenzmodelle einordnen

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.

ModellGarantiePreis
LinearisierbarAlle sehen eine einzige, zeitlich plausible ReihenfolgeKoordination bei jedem Zugriff, Verfügbarkeitsverlust bei Partition
KausalKausal abhängige Operationen sieht jeder in derselben ReihenfolgeKonkurrente Schreibzugriffe müssen zusammengeführt werden
EventualOhne neue Schreibzugriffe konvergieren alle ReplikateZwischenzeitlich 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.

Beweis- und Rechenaufgaben der Klausur üben

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:

  1. Zeitstempel eintragen: Zeit-Weg-Diagramm gegeben, Lamport- oder Vektoruhren ausfüllen, konkurrente Ereignisse benennen.
  2. Quorum berechnen: Knotenzahl und Fehlermodell gegeben, nötige Mehrheiten bestimmen oder begründen, warum ein Verfahren mit dieser Knotenzahl scheitert.
  3. Ablauf durchspielen: Leaderwahl oder Log-Replikation Schritt für Schritt bei Nachrichtenverlust oder Netzteilung verfolgen.
  4. Einordnen und begründen: Zu einem beschriebenen System das Konsistenzmodell bestimmen und die Konsequenz für Lesezugriffe nennen.
  5. Grenzen zeigen: Argumentieren, warum ein naiver Ansatz bei Teilausfall oder Asynchronie nicht funktioniert.

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.

Lernplan für das Semester

Der Stoff baut streng aufeinander auf: Ohne Fehlermodelle verstehst du Konsens nicht, ohne Kausalität keine Konsistenzmodelle. Arbeite deshalb in dieser Reihenfolge.

PhaseFokusWoran du merkst, dass es sitzt
SemesterbeginnSystemmodelle, Fehlermodelle, ZeitannahmenDu kannst zu jedem Verfahren sagen, welches Fehlermodell es voraussetzt
MitteLogische und Vektoruhren, gegenseitiger Ausschluss, WahlverfahrenDu zeichnest Zeit-Weg-Diagramme ohne Vorlage
Spätes SemesterKonsens (Paxos, Raft), Replikation, KonsistenzmodelleDu erklärst Raft in drei Teilen, ohne auf Folien zu schauen
KlausurphaseAltklausuren, Quorenrechnen, AbgrenzungsfragenDu 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.

Häufig gestellte Fragen (FAQ):

Was ist der Unterschied zwischen Lamport-Uhren und Vektoruhren?

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.

Was sagt das CAP-Theorem wirklich aus?

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.

Warum ist Konsens laut FLP unmöglich, obwohl Raft und Paxos funktionieren?

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.

Wie viele Knoten brauche ich, um f Ausfälle zu tolerieren?

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.

Wie bereite ich mich auf die Prüfung in Verteilte Systeme vor?

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.