31. Okt 2008, 21:19

In Mehrprozessor-Systemen bezeichnet ein byzantinischer 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.

[Bearbeiten] Herkunft der Bezeichnung

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 Information schicken können.

[Bearbeiten] Lösungen

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 "Befehlshaber und Leutnant"-Problem zurück, wobei alle loyalen Leutnante 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, aber was Byzantinisch-Fehlertolerant ist, so lange der Anteil der verräterischen Generäle nicht gleich oder größer als ein Drittel ist. Die Unmöglichkeit mit einem Drittel oder mehr Verrätern umgehen zu können, reduziert das Problem auf den Beweis, dass ein "1 Befehlshaber und 2 Leutnante"-Problem nicht lösbar ist, wenn der Befehlshaber ein Verräter ist. Wenn es drei Befehlshaber (A, B, C) gibt, wobei A der Verräter ist, und B von A die Nachricht "Angriff", und C von A die Nachricht "Rückzug" erhält, dann können weder B noch C bestimmen wer der Verräter ist, wenn sie sich gegenseitig die Nachricht von A senden. A muß nicht unbedingt der Verräter sein, da ja auch B oder C die Nachricht von A verändert haben kann.

Es kann gezeigt werden, dass wenn n die Anzahl der Generäle ist und t die Anzahl der Verräter innerhalb von n ist, dass es nur eine Lösung gibt wenn n größer oder gleich 3t+1 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 einer beliebigen Anzahl von verräterischen Generälen.
• Eine weitere Lösung ist eine Variation der ersten beiden Lösungen, die Byzantinische-Fehlertoleranz erreicht, wenn nicht alle Generäle direkt miteinander kommunizieren können.

[Bearbeiten] Literatur

• L. Lamport, R. Shostak, und M. Pease: The Byzantine Generals Problem. In: ACM Trans. Programming Languages and Systems. 4, Nr. 3, Juli 1982, S. 382-401 (http://research.microsoft.com/users/lamport/pubs/byz.pdf). 
• Hermann Kopetz, Real-Time Systems, Kluwer Academic Publishers, ISBN 0-7923-9894-7

Dieser Artikel ist eine Kopie aus der freien Enzyklopädie Wikipedia. Am Originalartikel kann jeder Korrekturen und Ergänzungen vornehmen. Zudem kann man frühere Versionen einsehen.

Abkürzungen • Dateiendungen • Netzjargon