Wiki: https://en.wikipedia.org/wiki/Byzantine_fault_tolerance
In der Arbeit "Einigung in Gegenwart von Fehlern erzielen" haben M. Pease et al. bewiesen, dass es kein Protokoll (irgendeiner Art) gibt, für das das Problem gelöst werden kann, wo steht für die Anzahl der Generäle und steht für die Anzahl der Verräter. Der Schlüssel ihres Beweises ist die Unmöglichkeit des Falles. Die von ihnen verwendete Methode sieht jedoch nicht wie ein informationstheoretischer Beweis aus. Es scheint also, dass ihr Ergebnis nicht "Unmöglichkeit eines willkürlichen Protokolls" ist.
Meine Frage: Gibt es einen auf der Informationstheorie basierenden Beweis für den Fall?? Genauer gesagt, gibt es einen Beweis oder ein Gegenbeispiel für den Satz "Es gibt kein Protokoll, das das Problem der byzantinischen Generäle löst, wo"?
Hinweis: Das typische Protokoll (Es funktioniert für beliebige ) vorgeschlagen von L. Lamport et al. ist KEIN geeignetes Gegenbeispiel, da es einen Signaturmechanismus benötigt, der im Sinne der Informationstheorie NICHT absolut zuverlässig ist, wenn wir davon ausgehen, dass Verräter über Infinity-Computing-Ressourcen verfügen.
Antworten:
Im synchronen Kommunikationsmodell gibt esn Agenten, die sich eine Uhr teilen. In jeder Kommunikationsrunde sendet jeder Agent eine beliebige Nachricht an jeden anderen Agenten und empfängt dann die Nachricht, die er von jedem anderen Agenten gesendet hat.
Ein Protokoll zur byzantinischen Einigung übern Agenten unterstützen m Byzantinische Agenten sind ein Kommunikationsprotokoll für Agenten, die die folgenden Eigenschaften erfüllen:
Das Unmöglichkeitsergebnis besagt, dass ein solches Protokoll genau dann existiert, wennn>3m .
Es gibt ein anderes Modell, in dem ein Agent eine Nachricht signieren kann, und diese Signatur kann nicht manipuliert werden. In diesem Modell (das ich formal nicht spezifizieren werde) kann das Problem für jedes gelöst werdenn,m .
Eine der Schwierigkeiten im Bereich verteilter Systeme ist die Kompliziertheit des Berechnungsmodells. Wenn Sie die Bedeutung von Unmöglichkeitsergebnissen verstehen möchten, müssen Sie sich mit diesen Modellen ausführlich vertraut machen (noch detaillierter als die eher informelle Behandlung in dieser Antwort).
quelle