C1ph4: Die Seite wurde neu angelegt: „Datei:ByzantineError.svg|mini|Beispiel eines byzantinischen Fehlers:
Uhr 3 ist fehlerhaft und verursacht einen byzantinischen Fehler, indem (anstatt 1000)…“

2018-01-19T20:39:09Z

Die Seite wurde neu angelegt: „Datei:ByzantineError.svg|mini|Beispiel eines byzantinischen Fehlers:<br>Uhr 3 ist fehlerhaft und verursacht einen byzantinischen Fehler, indem (anstatt 1000)…“

Neue Seite

[[Datei:ByzantineError.svg|mini|Beispiel eines byzantinischen Fehlers:<br>Uhr 3 ist fehlerhaft und verursacht einen byzantinischen Fehler, indem (anstatt 1000) das eine Mal 500 und das andere Mal 1500 gesendet werden.]]

Als '''byzantinische 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 ==
Das Adjektiv byzantinisch bezieht sich auf das ''Problem der [[Byzantinisches Reich|byzantinischen]] Generäle''. Einer Legende nach hatten [[Osmanisches Reich|osmanische]] Generäle, [[Eroberung von Konstantinopel (1453)|die im Jahr 1453 n. Chr. Konstantinopel belagerten]], ein Kommunikationsproblem. Wegen der starken Befestigung Konstantinopels war es notwendig, dass die Generäle mit ihren Truppen die Stadt gleichzeitig aus verschiedenen Richtungen angriffen. Die Generäle konnten über Boten miteinander kommunizieren. Allerdings intrigierten einige der Generäle gegen andere. Ihr Ziel war es, ihre Konkurrenten beim Sultan in Misskredit zu bringen – beispielsweise dadurch, dass sie die anderen durch geschickt gestreute Fehlinformationen zu einem verfrühten Angriff treiben wollten. Keiner der Generäle wusste nun, welche Information authentisch war und wem sie vertrauen konnten.

Es geht also um ein Problem der Übereinkunft, welches darin besteht, dass die Heerführer einstimmig beschließen müssen, ob sie angreifen oder nicht. Kompliziert wird das Problem durch die räumliche Trennung der [[Befehlshaber]]; sie müssen also Boten hin- und herschicken. Außerdem kommt die Möglichkeit hinzu, dass sich unter den Generälen Verräter befinden können, die an die anderen Generäle absichtlich irreführende Informationen schicken können.

Mathematisch zeigte sich, dass die loyalen Generäle unter diesen Voraussetzungen nur dann eine Einigungschance haben, wenn der Anteil der Intriganten kleiner als ein Drittel ist. Somit gab es insbesondere bei drei Generälen, von denen einer ein Intrigant ist, keine Lösung – jedenfalls nicht mit Hilfe klassischer Kommunikationsmethoden wie Boten.

== Lösungen ==
Die erste Veröffentlichung mit Lösungen zum Problem der byzantinischen Generäle geht zurück auf [[Leslie Lamport|Lamport]], Shostak und Pease im Jahr 1982. Sie führten das Problem auf ein Problem von 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 <math>(A, B, C)</math> gibt, wobei <math>A</math> der Verräter ist und <math>B</math> von <math>A</math> die Nachricht „Angriff“ und <math>C</math> von <math>A</math> die Nachricht „Rückzug“ erhält, dann können weder <math>B</math> noch <math>C</math> bestimmen, wer der Verräter ist, wenn sie sich gegenseitig die Nachricht von <math>A</math> senden. <math>A</math> muss nicht unbedingt der Verräter sein, da ja auch <math>B</math> oder <math>C</math> die Nachricht von <math>A</math> verändert haben kann.
: Es kann gezeigt werden, dass, wenn <math>n</math> die Anzahl der Generäle ist und <math>t</math> die Anzahl der Verräter innerhalb von <math>n</math> ist, es nur eine Lösung gibt, wenn <math>n \ge 3*t+1</math> ist, d.h. dass es bei einem Verräter erst bei vier Generälen eine Lösung gibt, da: <math>n \ge 3*1+1 => n \ge 4</math>. Bei zwei Verrätern braucht man also bereits mind. 7 Generäle, da: <math>n \ge 3*2+1 => n \ge 7</math>
* Eine zweite Lösung benötigt nicht fälschbare [[Digitale Signatur|Signaturen]] (in modernen Computersystemen wird das durch [[Öffentlicher Schlüssel|Public-Key]]-Kryptographie erreicht). Diese erhält Fehlertoleranz bei beliebiger Anzahl verräterischer Generäle. (''Siehe auch:'' [[Blockchain]])
* 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 ==
* [[Hermann Kopetz]]: ''Real-Time Systems.'' Kluwer Academic Publishers, April 1997, ISBN 0-7923-9894-7.
* {{Literatur|Autor=L. Lamport, R. Shostak, M. Pease|Online=[http://research.microsoft.com/en-us/um/people/lamport/pubs/byz.pdf pdf], Leslie Lamport: ''My Writings''|Titel=The Byzantine Generals Problem |Sammelwerk=[[Association for Computing Machinery|ACM]] Trans. Programming Languages and Systems |Band=4|Nummer=3|Monat=Juli|Jahr=1982|Seiten=382–401}}

== Externe Links ==
* {{Internetquelle |autor=Axel Tillemans |url=http://www.wissenschaft.de/technik-kommunikation/physik/-/journal_content/56/12054/1149640/Schweizer-Quantenphysiker-b%C3%A4ndigen-Byzantinische-Gener%C3%A4le/ |titel=Schweizer Quantenphysiker bändigen Byzantinische Generäle |zugriff=2017-03-04}}
* {{Internetquelle |autor=Doris Reim, Bartek Ochab |url=https://www.mtv.tu-berlin.de/fileadmin/a3435/Lehre/SoSe06/DistAlgs/Byzanz1.pdf |titel=Die Byzantinischen Generäle |werk=The Byzantine Generals Problemby Leslie Lamport, Robert Shostak, Marshall Pease |hrsg=[[Technische Universität Berlin]] |zugriff=2016-10-16 |format=PDF}}
* {{Internetquelle |autor=Esra Ünal |url=http://www.mi.fu-berlin.de/inf/groups/ag-tech/teaching/2010_SS/S_19510b_Proseminar_Technische_Informatik/esra-uenal-report.pdf |titel=Seminararbeit Byzantinische Fehler |werk=Proseminar Technische Informatik |hrsg=[[Freie Universität Berlin]] – Institut für Informatik |zugriff=2016-10-16 |format=PDF}}

[[Kategorie:Rechnerarchitektur]]
[[Kategorie:Technischer Defekt]]

Delegierten byzantinischen Fehlertoleranz - Versionsgeschichte

C1ph4: Die Seite wurde neu angelegt: „Datei:ByzantineError.svg|mini|Beispiel eines byzantinischen Fehlers:Uhr 3 ist fehlerhaft und verursacht einen byzantinischen Fehler, indem (anstatt 1000)…“

C1ph4: Die Seite wurde neu angelegt: „Datei:ByzantineError.svg|mini|Beispiel eines byzantinischen Fehlers:
Uhr 3 ist fehlerhaft und verursacht einen byzantinischen Fehler, indem (anstatt 1000)…“