Byzantinische Fehlertoleranz

Herkunft und Begriff

Der Begriff geht auf den Aufsatz „The Byzantine Generals Problem“ von Leslie Lamport, Robert Shostak und Marshall Pease zurück, erschienen 1982 in der Fachzeitschrift ACM Transactions on Programming Languages and Systems. Die Autoren arbeiteten damals am SRI International an fehlertoleranten Rechnern für die Flugsteuerung. Lamport erhielt 2013 den Turing Award, unter anderem für Arbeiten zu verteilten Systemen.

Das Gedankenexperiment: Mehrere Divisionen einer byzantinischen Armee belagern eine Stadt. Ihre Generäle können sich nur über Boten verständigen und müssen sich auf einen gemeinsamen Plan einigen, angreifen oder abziehen. Unter ihnen sind Verräter, die den anderen widersprüchliche Nachrichten schicken. Gesucht ist ein Verfahren, mit dem sich alle loyalen Generäle auf denselben Plan einigen.

Merkmale

• Beliebige Fehler: Ein byzantinisch fehlerhafter Teilnehmer kann schweigen, falsche Werte melden oder verschiedenen Teilnehmern Verschiedenes mitteilen.
• Regel 3f+1: Mit einfachen, nicht signierten Nachrichten ist eine Einigung genau dann möglich, wenn mehr als zwei Drittel der Teilnehmer korrekt arbeiten. Um f fehlerhafte Teilnehmer zu verkraften, braucht es mindestens 3f+1 Teilnehmer, für einen also vier. Drei Teilnehmer reichen nicht, weil ein einziger Verräter zwei loyale gegeneinander ausspielen kann.
• Signierte Nachrichten: Lassen sich Nachrichten fälschungssicher unterschreiben, ist das Problem für jede Zahl von Teilnehmern und Verrätern lösbar.

Anwendung

• Flug- und Raumfahrtsteuerung: Vierfach redundante Rechnerverbünde wie im Space Shuttle tolerieren einen beliebig fehlerhaften Rechner. Siehe Quadrupel-Redundanz.
• Verteilte Datenbanken und Blockchains: Konsensverfahren wie Practical Byzantine Fault Tolerance (Castro und Liskov, 1999) sorgen dafür, dass sich Rechner im Netz trotz manipulierter Knoten auf einen gemeinsamen Datenstand einigen.
• Künstliche Intelligenz: In Systemen mit mehreren KI-Agenten oder Prüfmodellen stellt sich dieselbe Frage. Ein Modell, das sich in Tests anders verhält als im Einsatz oder bewusst falsche Ergebnisse liefert, entspricht einem byzantinischen Teilnehmer.

Kritik und Grenzen

• Aufwand: Die Zahl der auszutauschenden Nachrichten wächst mit der Zahl der Teilnehmer stark an. Das begrenzt die Größe solcher Verbünde.
• Unabhängigkeit: Die Garantie gilt nur, solange höchstens f Teilnehmer fehlerhaft sind. Haben alle Teilnehmer denselben Fehler, etwa in gemeinsamer Software, hilft das Verfahren nicht.
• Modelle: Bei Sprachmodellen ist schwer festzustellen, ob ein Teilnehmer fehlerhaft ist, weil es für viele Aufgaben keine eindeutig richtige Ausgabe gibt.

Siehe auch

• Quadrupel-Redundanz
• N-Versionen-Programmierung
• KI-Agent
• Praxis: Quadrupel-Redundanz: Was KI-Agenten von der Raumfahrt lernen können