Konsensalgorithmen

Konsensalgorithmen sind Protokolle, die in verteilten Systemen sicherstellen, dass eine Gruppe von Knoten trotz Ausfällen oder Netzwerkverzögerungen eine gemeinsame Entscheidung trifft. Typische Anwendungsfälle sind die Replikation von Zuständen, die Reihenfolge von Transaktionen oder Log-Einträgen, sowie die Festlegung eines globalen, übereinstimmenden Zustands.

Wesentliche Eigenschaften umfassen Sicherheit (Safety), die sicherstellt, dass zwei korrekt funktionierende Knoten nicht widersprüchliche Entscheidungen treffen, Liveness (Fortbestehen), die garantiert, dass zumindest eine Entscheidung getroffen wird, sowie Fehlertoleranz gegenüber Ausfällen. In der Praxis gilt oft, dass n Knoten bis zu f fehlerhafte Knoten tolerieren, wobei n ≥ 2f+1 bei Crash-Fehlern und n ≥ 3f+1 bei Byzantinischen Fehlern nötig ist.

Wichtige Beispiele sind Paxos, Raft und byzantinisch tolerante Protokolle wie PBFT oder Tendermint. Paxos zielt darauf ab, eine konsistente Reihenfolge von Entscheidungen zu erreichen, Raft betont Verständlichkeit durch einen Leader und klare Log-Replikation, PBFT/Tendermint behandeln bösartig handelnde Knoten, oft mit mehreren Kommunikationsrunden.

Funktionsweise im Groben: Die Protokolle arbeiten in Phasen oder Runden, stimmen über vorgeschlagene Werte ab und gelangen schließlich zur Bestellung von Log-Einträgen. Der Leader oder Koordinator koordiniert die Replikation, während Follower oder Akzeptoren die Entscheidungen bestätigen; bei Byzantinischen Varianten kommen zusätzliche Validierungsstufen hinzu.

Anwendungen finden sich in verteilten Datenbanken, Cloud-Diensten, Dateisystemen und Blockchain-Plattformen, wo konsistente Zustandsreplikation und geordnete Transaktionen zentral sind.

Herausforderungen umfassen Netzwerkpartitionen, asynchrone Kommunikation, Latenz, Skalierung und die Komplexität von Implementierungen; Entscheidungstransparenz und die Balance zwischen Konsistenz und Verfügbarkeit bleiben zentrale Designfragen.