Dienstag, Februar 14, 2006
Byzantinische Generäle
Guten Morgen, liebe Leserschaft!
Guten Morgen, Byzantiner!
Mal wieder halte ich es für nötig meine Leserschaft mit Bildungs zu versorgen. Zwar ist es nicht gerade so, dass die Leserschaft große Begeisterung für die Hermannschen Belehrungen empfand, doch was mutt dat mutt.
Wie wir alle wissen, gab es mal ein schönes byzantinischem Reich mit vielen Generälen, mehr oder weniger bestechlich waren. Diese komischen Generälen waren auch Bestandteil eines Papers vom Lamport et al.[1]
Diese abstrakte und verzwickte Angelegenheit wird erst wirklich verständlich wenn wir dieses Problem auf die Realität übertragen. Nehmen wir an, wir haben einen Obergeneral, dieser gibt Befehle. Ein Verräter versucht Verwirrung zu stiften. Um ihre Entscheidung zu Treffen, erhalten die Rangniederen Generäle Nachrichten von allen anderen Generälen über einen Poten. Über eine Mehrheitsentscheidung ist es einem General möglich bei 3m+1 Generälen und m Verrätern die richtige Entscheidung zu treffen, falls der Ranghöchste General loyal ist.
Wer ist der Verräter?Gute Nacht, liebe Leserschaft!
(Mittwoch, Februar 15, 2006 10:48:00 PM):
Danke für diese Bildungs.
Hermann (Donnerstag, Februar 16, 2006 6:45:00 PM):
Ja, das wirklich interessante habe ich heute erst festgestellt:
Ist der General loyal, dann braucht es 2k+m+1 Generäle. Wobei k die Zahl der Verräter ist.
Ist der General der Verräter, dann brauchen wir sogar 3m+1 Generäle, sobei m ist Anzahl der Generäle ist!
(Donnerstag, Februar 16, 2006 10:28:00 PM):
Konnen Generäle den auch vorgeben loyal oder verräterisch zu sen um zusatzlich Verwirrung zu stiftenß
Hermann (Freitag, Februar 17, 2006 11:24:00 AM):
Hehe, lustig wenn man es sich noch mal durchliest, was ich geschrieben hatte.
Also... es geht darum eine gemeinsame Entscheidung zu finden. Wenn nun der Rang höchste General an allen einen falschen Befehl sendet, dann können das die Rangniederen nicht erkennen, und machen das was er sagt. Sendet er allerdings an alle Generäle verschiedene Befehle, sprechne diese sich ab und stellen fest, dass da etwas nicht stimmen kann. So werden sie eine Mehrheitsentscheidung machen, in dem der Oral-Message-Algorithmus rekursiv von jedem der Generäle ausgeführt wird, und zwar mit m Rekursionsstufen!
Also vorgeben können Sie nix, denn sie werden erkannt. Es sei denn die Zahl der loyalen Generäle ist zu niedrig.
Kommentar veröffentlichen
<< Home
