Das Problem der byzantinischen Generäle

Das Problem der byzantinischen Generäle kann wie folgt erklärt werden. Ein General, der einen Befehl ausgibt (hier als Kommandeur bezeichnet), muss seinen Befehl an die n − 1 anderen Generäle (Leutnants) schicken, so dass die folgenden Bedingungen zutreffen:

• B1: Alle loyalen Leutnants gehorchen den selben Befehl.
• B2: Falls der befehlshabende General (Kommandeur) loyal ist, dann gehorcht jeder loyale Leutnant dessen Befehl.

Im Folgenden soll sichergestellt werden, dass diese Bedingungen stets zutreffen. Alle Nachrichten sind mündlich und der Inhalt wird alleine vom Absender bestimmt. Zunächst soll die Situation an einem Beispiel verdeutlicht werden.

Abbildung 1: Leutnant 2 ist ein Verräter

In diesem Beispiel ist Leutnant 2 der Verräter. Da der Kommandeur loyal ist, gibt er die gleichen Befehle an alle Generäle aus. Im hier verdeutlichen Fall ist dieser Befehl "Angriff". Um zu gewährleisten, dass alle loyalen Generalle die gleiche Entscheidung treffen, leitet jeder Leutnant den erhaltenen Befehl an alle anderen Generäle weiter. Somit sendet Leutnant 1 eine Nachricht an Leutnant 2, die besagt, dass der vom Kommandeur erhaltene Befehl "Angriff" lautet. Jedoch ist Leutnant 2 ein Verräter und sendet daher eine Nachricht mit dem Befehl "Rückzug" an Leutnant 1.

Im zweiten Beispiel (Abbildung 2) ist der Kommandeur ein Verräter und kann somit inkonsistente Befehle an seine Leutnants ausgeben. Angenommen der Kommandeur gibt Leutnant 1 den Befehl "Angriff" und Leutnant 2 den Befehl "Rückzug", so leiten beide Leutnants den erhalten Befehl an den anderen weiter. Es wird deutlich, dass für Leutnant 1 die gleiche Situation wie im ersten Beispiel (Abbildung 1) entsteht. Es ist für ihn unentscheidbar, ob der Kommandeur oder Leutnant 2 der Verräter ist.

Abbildung 2: Der Kommandeur ist ein Verräter

Es kann bewiesen werden, dass keine Lösung funktionieren kann, wenn nicht mehr als zwei Drittel der Generäle loyal sind. Zuerst muss der Fall für drei Generäle betrachtet werden, wovon einer nicht loyal ist [1].

Dieser Fall kann verallgemeinert werden, um zu zeigen, dass keine Lösung für weniger oder gleich 3m Generäle mit m Verrätern funktionieren kann. Hierzu wird eine byzantinische Armee von drei Generälen verwendet. Jeder dieser Generäle simuliert etwa ein Drittel einer weiteren Armee. Der byzantinische Kommandeur simuliert hierbei den albanischen Kommandeur und zusätzlich bis zu m−1 albanische Leutnants. Jeder der beiden byzantinischen Leutnants simuliert bis zu m albanische Leutnants.

Abbildung 3: Eine albanische Armee wird mit Hilfe von drei byzantinischen Generälen simuliert

Im folgenden werden diese Annahmen vorausgesetzt:

• A1: Jede gesendete Nachricht, wird korrekt zugestellt
• A2: Der Empfänger einer Nachricht weiß, wer der Absender war
• A3: Das Fehlen einer Nachricht kann festgestellt werden

Die ersten beiden Bedingungen stellen sicher, dass ein Verräter sich nicht in die Kommunikation zweier Generäle stellen kann. A3 sorgt dafür, dass ein Verräter die Entscheidungsfindung nicht verhindern kann, indem er keine Nachrichten sendet. Es wird klar, dass es hierbei notwendig ist, dass jeder General Nachrichten direkt zu jedem anderen General senden kann. Falls ein Verräter keine Nachricht sendet, wird ein Senden der Nachricht "Rückzug" angenommen.

Ein Algorithmus für die Lösung des Problems

Im folgenden wird ein Algorithmus behandelt, der das Problem der byzantinischen Generäle für 3m + 1 Generäle in der Anwesenheit von höchstens m Verrätern löst.

Hierzu wird eine Mehrheitsfunktion M(v1 , ..., v_n−1) definiert. Jedes v_i steht entweder für "Angriff" oder "Rückzug". Falls keine Mehrheit gefunden werden kann, wird das Ergebnis auf "Rückzug" gesetzt. In Abbildung 4 wird der Algorithmus für vier Generäle verdeutlicht. Leutnant 3 ist ein Verräter. Da der Kommandeur loyal ist, sendet er den gleichen Wert an alle Generäle aus. Leutnants 1 und 2 senden den empfangen Wert an alle anderen Leutnants aus, da auch diese loyal sind.

Abbildung 4: Beispiel für vier Generäle, wovon ein Leutnan nicht loyal ist

Der dritte Leutnant jedoch sendet falsche oder verschiedene Werte aus. Wie aus der Abbildung 4 zu sehen, beeinflusst der Verräter den Ausgang der Mehrheitsfunktion M nicht. Weiterhin halten beide interaktiven Konsistenzbedingungen. Alle Leutnants kommen zum selben Mehrheitsergebnis und folgen daher den selben Befehl (B1). Weiterhin folgen alle Leutnants dem Befehl des Kommandeurs, da dieser loyal ist (B2).

Quellen
[1] M. Pease, R. Shostak, L. Lamport, Reaching agreement in the presence of faults. J. ACM 27, 2 (Apr. 1980), 228-234.
[2] Lamport L., Shostak R. , and Pease M. (July 1982). The Byzantine Generals Problem. ACM Trans. Programming Languages and Systems 4 (3)
[3] https://de.wikipedia.org/wiki/Byzantinischer_Fehler (allgemeiner Fall aus der IT)