Die Byzantinischen Generäle

Die Byzantinischen Generäle
Von
Doris Reim
und
Bartek Ochab
aus dem Artikel:
The Byzantine Generals Problem
by Leslie Lamport, Robert Shostak, Marshall Pease
Agenda
I.
Einleitung
II.
Lösbarkeit ?
III.
OM-Algorithmus
IV.
SM-Algorithmus
V.
Fehlende Kommunikationswege
VI.
Zuverlässige Systeme
VII.
Zusammenfassung
Byzanz unter Beschuß
●
1453: Der Fall Konstantinopels
●
Komponenten in Computersystemen können
lügen
- Was passiert, wenn eine fehlerhafte Komponente widersprüchliche
Daten an andere versendet?
●
Abstraktion des Problems auf die Generäle
- Jede Einheit hat ihren eigenen General
- Die Generäle können sich nur über Boten verständigen
- Sie müssen sich auf einen gemeinsamen Plan einigen
- Es kann Verräter geben
Erfolgsgarantie?
- Voraussetzungen Für einen Sieg brauchen die Generäle einen
Algorithmus, der folgendes garantiert:
●
A: Alle loyalen Generäle kommen zur selben
Entscheidung
- Unabhängig vom Verhalten der Verräter
●
B: Eine geringe Anzahl Verräter kann die
loyalen Generäle nicht zu einer Fehlentscheidung bringen
- Vorgehen: jeder beobachtet und vermittelt den anderen, was er
sieht
Mögliche Methode
Idee:
●
Die einzigen Befehle sind “Angriff” und
“Rückzug”
●
Die Nachrichten aller Generäle werden gesammelt
●
Entscheidung per Mehrheitsvotum
Problem des Generals und
seiner Leutnants
●
Ein kommandierender General muß seinen
n-1 Leutnants seine Befehle schicken, so
daß folgendes erfüllt ist:
✔ IC1: Jeder loyale Leutnant erhält den gleichen Befehl
✔ IC2: Wenn der General loyal ist, befolgt jeder
loyale Leutnant den Befehl, den er erhalten
hat
Agenda
I.
Einleitung
II.
Lösbarkeit ?
III.
OM-Algorithmus
IV.
SM-Algorithmus
V.
Fehlende Kommunikationswege
VI.
Zuverlässige Systeme
VII.
Zusammenfassung
Lösbarkeit ?
●
Bei mündlichen Nachrichten ist das Problem
nicht lösbar, wenn unter drei Generälen
auch nur ein Verräter ist
Lösbarkeit ?
●
Bei mündlichen Nachrichten ist das Problem
nicht lösbar, wenn unter drei Generälen
auch nur ein Verräter ist
Lösbarkeit ?
●
Bei der Übersetzung auf mehr als drei
Generäle ergibt sich, daß 3m Generäle nicht
mit m Verrätern umgehen können
●
Auch ein Entschärfen der Bedingungen IC1
und IC2 macht das Problem nicht “besser”
Grundidee: nur der Zeitpunkt des Angriffs muß vereinbart werden
✔ IC1': Alle loyalen Leutnants starten innerhalb von 10 min
gemeinsam ihren Angriff
✔ IC2': Wenn der General loyal ist, greift jeder loyale Leutnant
innerhalb von 10 min nach dem befohlenen Zeitpunkt an
Agenda
I.
Einleitung
II.
Lösbarkeit ?
III.
OM-Algorithmus
IV.
SM-Algorithmus
V.
Fehlende Kommunikationswege
VI.
Zuverlässige Systeme
VII.
Zusammenfassung
Definition: Mündliche Nachricht
●
A1: Jede versandte Nachricht wird korrekt
empfangen
–
●
A2: Der Empfänger weiß, wer der Sender ist
–
●
Hierdurch können Verräter nicht in den Nachrichtenverkehr anderer
eingreifen.
Hierdurch können sich Verräter nicht als jemand anderes ausgeben.
A3: Das Fehlen einer Nachricht kann
festgestellt werden
Weitere Vorraussetzungen
●
Jeder General kann mit jedem anderen direkt
kommunizieren
●
Leutnants befolgen einen Standardbefehl,
wenn sie keinen (gültigen) erhalten
OM(m) Algorithmus
●
Gilt für alle nichtnegativen m.
●
Löst das byzantinische Generäle Problem für
3m+1 oder mehr Generäle mit maximal m
Verrätern.
●
Sei eine Funktion Mehrheit gegeben, die das
Mehrheitsvotum implementiert
OM(m) Algorithmus
(1)Kommandant sendet seinen Befehl an jeden
Leutnant
(2)Jeder Leutnant vermerkt den Befehl, den er
erhalten hat, und agiert dann selbst als
Kommandant, indem er OM(m-1) auf alle
anderen n-2 Leutnants anwendet
(3)Jeder Leutnant vermerkt alle Befehle die er
erhalten hat und benutzt dann Mehrheit
OM(m) Algorithmus, m>0
OM(m) Algorithmus, m>0
OM(m) Algorithmus, m>0
OM(m) Algorithmus, m>0
OM(m) Algorithmus, m>0
OM(m) Algorithmus, m>0
OM(m) Algorithmus, m>0
OM(m) Algorithmus, m>0
OM(m) Algorithmus, m>0
OM(m) Algorithmus, m>0
Agenda
I.
Einleitung
II.
Lösbarkeit ?
III.
OM-Algorithmus
IV.
SM-Algorithmus
V.
Fehlende Kommunikationswege
VI.
Zuverlässige Systeme
VII.
Zusammenfassung
Lösungsstrategie für signierte
Nachrichten
●
Idee: Den Verräter behindern, indem ihm das
Versenden gefälschter Nachrichten
erschwert wird:
✔ A4:
✔ a) Die Signatur eines loyalen Generals kann
nicht gefälscht werden und eine Änderung am
Inhalt der Nachricht wird erkannt
✔ b) Jeder kann die Signatur des Generals
verifizieren
Eigenschaften
●
Das Verfahren löst das Problem für m
Verräter
●
Für weniger als m+2 Generäle ist die Frage
Unsinn
●
Jeder Leutnant erhält eine signierte
Nachricht vom General, kopiert sie, hängt
seine Signatur an und sendet sie an die
anderen.
–
Wie kopiert wird, spielt keine Rolle!
Definition: SM(m)-Algorithmus
●
Sei Choice eine Funktion, die aus einer
Menge V von Befehlen einen einzelnen
auswählt, mit folgenden Eigenschaften:
–
–
Wenn die Menge V nur das Element v enthält, dann gilt:
Choice(V) = v
Choice({}) = „Rückzug“
●
Sei x:j:i der Wert x signiert von General j und
i
●
Sei 0 der Kommandant
SM(m) Algotithmus
Init: Für alle i : Vi = {}
(1) Der Befehlshaber signiert und sendet
seinen Befehl an jeden Leutnant
(2) für jedes i:
A) Wenn Leutnant i eine Nachricht der Form v:0
vom Kommandanten erhält und er bislang noch
keine Nachricht erhalten hat, dann
i) Vi = {v}, und
ii) er sendet die Nachricht v:0:i an jeden anderen
Leutnant
SM(m) Algotithmus
B) Wenn Leutnant i eine Nachricht der Form v:0:j1:...jk
erhält und v noch nicht in Vi ist,
i) fügt er v zu Vi hinzu
ii) wenn k < m, sendet er die Nachricht v:0:j1:...jk:i an die
übrigen Leutnants
(3) für jedes i:
Wenn Leutnant i keine weiteren
Nachrichten mehr erhalten wird,
befolgt er die Anweisung choice(Vi)
SM(1)
Agenda
I.
Einleitung
II.
Lösbarkeit ?
III.
OM-Algorithmus
IV.
SM-Algorithmus
V.
Fehlende Kommunikationswege
VI.
Zuverlässige Systeme
VII.
Zusammenfassung
Fehlende Kommunikationswege
●
Bisher: Jeder konnte mit jedem anderen
direkt kommunizieren
●
Jetzt: Ein einfacher, endlicher, ungerichteter
Graph gibt an, wer mit wem kommunizieren
kann.
Definition: Reguläre
Nachbarschaft
✔ 1) Alle Knoten aus der Menge sind Nachbarn
des Knotens i.
✔ 2) Für jeden Knoten k im Graphen der
ungleich i ist, existieren Wege von den
Nachbarknoten von i nach k, die nicht über i
laufen, so dass zwei verschiedene Wege
nichts ausser dem Endknoten k gemeinsam
haben.
Definition: P-Regularität
✔ Alle Knoten des Graphen besitzen eine
Menge aus Nachbarn, die aus genau P
verschiedenen Knoten besteht.
3-Regulärer Graph
3-Regulärer Graph
Erweiterung von
OM(m) auf OM(m,p)
●
Die Erweiterung löst das byzantinische
Generäle Problem mit m Verrätern, wenn der
Kommunikationsgraph p-regulär ist.
–
Der Kommunkationsgraph muß mindestens 3m-regulär sein
–
Der Graph muß mindestens 3m+1 Generäle enthalten
Definition: OM(m,p)
Algorithmus
●
1.) Der Kommandant sendet seinen Befehl zu jedem benachbarten
Leutnant
●
2.) Für alle Leutnants i, die direkte Nachbarn des Kommandanten sind:
Jeder sendet seinen erhaltenen Befehl zu jedem Leutnant k:
●
–
A) Wenn m=1, sende den Befehl zu allen anderen Leutnants k
–
B) Wenn m>1, dann agiert Leutnant i wie der Kommandant und
wendet den Algorithmus OM(m-1,p-1) mit dem Graphen ohne den
ursprünglichen Kommandanten an.
3.) Jeder Leutnant vermerkt alle Befehle, die er erhalten hat, und
benutzt dann Mehrheit auf die Liste aller Befehle, die er empfangen hat.
OM(1,3)
OM(1,3)
OM(1,3)
OM(1,3)
OM(1,3)
OM(1,3)
Überlegungen zum Graphen
●
Der OM(m,p) Algorithmus verlangt einen 3mregulären Kommunikationsgraph
–
●
Im Falle der minimalen Anzahl an Generälen (4) bedeutet das
vollständige Vernetzung
Der SM(m) Algorithmus kann leicht erweitert
werden, um die schwächst mögliche
Bedingung an die Konnektivität zu erhalten
Wieviel Konnektivität ist nötig?
●
IC1 verlangt, daß alle loyalen Leutnants den
gleichen Befehl befolgen.
➔
●
Kann nicht garantiert werden, wenn zwei loyale Leutnants nur über
einen Verräter hinweg kommunizieren können.
IC2 verlangt, daß loyale Leutnants einem
loyalen Kommandanten gehorchen
➔
Unmöglich, wenn der Kommandant nicht mit den Leutnants
verbunden ist
➔
Unmöglich, wenn der Kommandant nur über einen Verräter hinweg
mit den loyalen Leutnants kommunizieren kann.
Bedinung an die Konnektivität
➔
Der Subgraph, der durch die loyalen
Generäle gebildet wird ist vollständig.
–
Jeder loyale General kann jeden anderen loyalen General erreichen
–
Unter dieser Hypothese ist das byzantinische Generäle Problem mit
dem SM(n-2) Algorithmus lösbar, unabhängig von der Anzahl der
Verräter, mit n als Anzahl der Generäle
Agenda
I.
Einleitung
II.
Lösbarkeit ?
III.
OM-Algorithmus
IV.
SM-Algorithmus
V.
Fehlende Kommunikationswege
VI.
Zuverlässige Systeme
VII.
Zusammenfassung
Zuverlässige Systeme
●
●
Zuverlässigkeit wird versucht durch
Redundanz zu erreichen
–
Mehrere Prozessoren berechnen den selben Wert um den Ausfall
einzelner Pozessoren zu kompensieren
–
Der Endwert wird dann durch Mehrheitsvotum ermittelt
Diese Idee setzt vorraus, daß alle
redundanten Komponenten denselben Input
bekommen
Sicherheit durch Redundanz
●
Das System muss folgende Bedingungen
erfüllen, damit durch Mehrheitsvotum
Zuverlässigkeit garantiert werden kann.
–
1. Alle nicht fehlerhaften Prozessoren müssen
dieselbe Eingabe benutzen.
–
2. Wenn das Input-Device nicht fehlerhaft ist,
benutzen alle nicht fehlerhaften Prozessoren den
erhaltenen Wert.
Erkenntnis
Verlässliche Systeme
●
Unsere Algorithmen garantieren, daß alle
Prozessoren den selben Wert für ihre
Berechnungen erhalten.
●
Sind Mehrheit und Choice z.B. MedianFunktionen, so garantieren unsere
Algorithmen, daß der Fehler nicht größer ist
als durch das Input-Device vorgegeben.
Umsetzung in die Praxis
●
A1 : Jede Nachricht von einem korrekten
Prozessor wird immer korrekt empfangen
➔
In der Realität nicht garantierbar
➔
Das Versagen einer Leitung ist für den Prozessor dasselbe, als
wenn der andere Prozessor versagen würde
➔
Wenn wir ahnehmen, daß eine fehlerhafte Leitung nicht zur
Fälschung von signierten Nachrichten führt, ist der SM(m)
Algorithmus unabhägig von solchen Fehlern.
•
Diese führen nur zur Reduzierung der Verknüpfungen im
Kommunikationsgraphen
Umsetzung in die Praxis
●
A2 : Der Absender einer Nachricht ist immer
ermittelbar.
➔
Nur durch separate Leitungen für jeden Kommunikationsweg
realisierbar.
➔
Bei gemeinsamen Kommunikationsnetzwerken müssen fehlerhafte
Kommunikationsknoten mitbetrachtet werden, was wieder zum
„byzantinische Generäle“ Problem führt.
➔
Annahme entfällt im Fall von signierten Nachrichten.
Umsetzung in die Praxis
●
A3 : Das Fehlen einer Nachricht kann immer
ermittelt werden.
➔
Nur durch Time-out Wartezeiten realisierbar
➔
Dadurch müssen weitere Nebenbedingungen erfüllt werden.
➔
➔
➔
1.) Die Zeit zum generieren und versenden einer Nachricht ist konstant
2.) Uhren von Sender und Empfänger sind bis auf einen gewissen maximalen
Fehler synchron.
Uhren der Prozessoren müssen von Zeit zu Zeit neu synchronisiert
werden.
•
Anderes schweres Problem, jedoch änlich zum „byzantinische Generäle“
Problem.
Umsetzung in die Praxis
●
A4 : Signaturen von nicht fehlerhaften
Prozessoren müssen fälschungssicher sein.
➔
Kann niemals garantiert werden.
➔
➔
Folgende Bedingungen an die Signatur müssen erfüllt werden
➔
➔
➔
Allerdings kann die Warscheinlichkeit für den Bruch dieser Bedingung beliebig
klein gemacht werden.
1) Kein fehlerhafter Prozessor kann die Signatur eines fehlerfreien Prozessors
erzeugen.
2) Wenn die Nachricht gegeben ist, muss die Sigantur erkannt werden können.
Um die Einzigartigkeit der Signatur zu bewahren, sollte es
vermieden werden eine Nachricht neu zu signieren.
Agenda
I.
Einleitung
II.
Lösbarkeit ?
III.
OM-Algorithmus
IV.
SM-Algorithmus
V.
Fehlende Kommunikationswege
VI.
Zuverlässige Systeme
VII.
Zusammenfassung
Zusammenfassung
●
Beide Algorithmen sind teuer
●
Verbesserung des Problems nur, falls
Vorannahmen gemacht werden können, die
gewisse Fehlerfälle ausschließen
Danke für die
Aufmerksamkeit