Byzantinischer Fehler

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Beispiel eines byzantinischen Fehlers:
Uhr 3 ist fehlerhaft und verursacht einen byzantinischen Fehler.

Als byzantinischer Fehler bezeichnet man in der Informationstechnik Fehler, bei denen sich ein System beliebig falsch verhalten kann. Beispielsweise schickt ein Server gelegentlich falsche Antworten und erreicht gelegentlich falsche Systemzustände. Ein byzantinischer Fehler beschreibt im Allgemeinen ein schwierig zu erfassendes Fehlermodell.

In Mehrprozessor-Systemen bezeichnet der byzantinische Fehler eine Fehlerklasse. Falls eine Komponente an verschiedene Prozessoren unterschiedliche (protokollkonforme) Ergebnisse liefert, spricht man von einem byzantinischen Fehler. Bei der Planung wird davon ausgegangen, dass x Prozessoren bösartig arbeiten und das System maximal stören wollen.

Herkunft der Bezeichnung[Bearbeiten | Quelltext bearbeiten]

Das Adjektiv byzantinisch bezieht sich auf das Problem der byzantinischen Generäle. Es ist ein Problem der Übereinkunft, welches darin besteht, dass die Heerführer einstimmig beschließen müssen, ob sie eine feindliche Armee angreifen sollen oder nicht. Kompliziert wird das Problem durch die räumliche Trennung der Befehlshaber; sie müssen also Boten hin- und herschicken. Dazu kommt die Möglichkeit, dass sich unter den Generälen Verräter befinden können, die an die anderen Generäle absichtlich irreführende Informationen schicken können.

Lösungen[Bearbeiten | Quelltext bearbeiten]

Die erste Veröffentlichung mit Lösungen zum Problem der byzantinischen Generäle geht zurück auf Lamport, Shostak und Pease im Jahr 1982. Sie führten das Problem auf ein Problem vom Befehlshaber und Leutnant zurück, wobei alle loyalen Leutnants in Einklang handeln müssen und ihre Aktionen mit den Befehlen des Befehlshabers übereinstimmen müssen, wenn dieser loyal ist. Kurz, der General wählt, indem er alle anderen Befehle als Wahlstimmen behandelt.

  • Eine erläuterte Lösung beachtet das Szenario, bei dem Nachrichten gefälscht werden. Solange der Anteil der verräterischen Generäle kleiner als ein Drittel ist, ist diese Lösung tolerant gegenüber einem byzantinischen Fehler. Die Unmöglichkeit, mit einem Drittel oder mehr Verrätern umgehen zu können, reduziert das Problem auf den Beweis, dass der Fall mit einem Befehlshaber und zwei Leutnants nicht lösbar ist, wenn der Befehlshaber ein Verräter ist. Wenn es drei Befehlshaber gibt, wobei der Verräter ist und von die Nachricht „Angriff“ und von die Nachricht „Rückzug“ erhält, dann können weder noch bestimmen, wer der Verräter ist, wenn sie sich gegenseitig die Nachricht von senden. muss nicht unbedingt der Verräter sein, da ja auch oder die Nachricht von verändert haben kann.
Es kann gezeigt werden, dass, wenn die Anzahl der Generäle ist und die Anzahl der Verräter innerhalb von ist, es nur eine Lösung gibt, wenn ist.
  • Eine zweite Lösung benötigt nicht fälschbare Signaturen (in modernen Computersystemen wird das durch Public-Key-Kryptographie erreicht). Diese erhält Fehlertoleranz bei beliebiger Anzahl verräterischer Generäle. (Siehe auch: Block Chain)
  • Eine weitere Lösung ist eine Variation der ersten beiden Lösungen, die Byzantinischer-Fehler-Toleranz erreicht, wenn nicht alle Generäle direkt miteinander kommunizieren können.

Literatur[Bearbeiten | Quelltext bearbeiten]

  • Hermann Kopetz: Real-Time Systems. Kluwer Academic Publishers, April 1997, ISBN 0-7923-9894-7.
  • L. Lamport, R. Shostak, M. Pease: The Byzantine Generals Problem. In: ACM Trans. Programming Languages and Systems. Band 4, Nr. 3, Juli 1982, S. 382–401 (pdf, Leslie Lamport: My Writings).