Unmöglichkeit für byzantinische Generäle Problem wo

7

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 kannn3m, wo n steht für die Anzahl der Generäle und msteht für die Anzahl der Verräter. Der Schlüssel ihres Beweises ist die Unmöglichkeit des Fallesn=3,m=1. 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?n=3,m=1? 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, won=3,m=1"?


Hinweis: Das typische Protokoll SM(m) (Es funktioniert für beliebige n,m) 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.

Lwins
quelle
1
Was ist ein "informationstheoretischer Beweis"? Warum erwarten Sie in diesem Fall einen solchen Beweis?
Yuval Filmus
An @YuvalFilmus: Ich denke, dass (vielleicht ist es ein falscher Glaube) der ursprüngliche Beweis der Unmöglichkeit besagt, dass "es kein Protokoll in einer bestimmten Form für gibt n3m", was anders ist als" es gibt kein Protokoll für n3m". Also suche ich einen Beweis (oder ein Gegenbeispiel) für letzteres. Beachten Sie, dass das typische Protokoll SM(m) (Es funktioniert für beliebige n,m) 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.
Lwins
Was Sie also wirklich fragen, ist, welches Ergebnis genau in dem Papier "Erreichen einer Einigung in Gegenwart von Fehlern" bewiesen ist. Vermutlich wird dies in der Arbeit erklärt.
Yuval Filmus
Zu @YuvalFilmus: Nicht genau wahrscheinlich. Wie ich oben erwähnt habe, suche ich einen Beweis (oder ein Gegenbeispiel) für den Satz "Es gibt kein Protokoll fürn3m".
Lwins

Antworten:

3

Im synchronen Kommunikationsmodell gibt es nAgenten, 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 über n Agenten unterstützen m Byzantinische Agenten sind ein Kommunikationsprotokoll für Agenten, die die folgenden Eigenschaften erfüllen:

  • Jeder Agent empfängt ein Eingabebit.
  • Die Agenten beginnen alle zum Zeitpunkt 0 zu sprechen.
  • Es gibt höchstens m byzantinische Agenten, deren Verhalten willkürlich ist.
  • Die anderen Agenten folgen dem Protokoll.
  • Das Protokoll wird immer beendet (dies bedeutet, dass die nicht-byzantinischen Agenten immer einen speziellen "Beendigungs" -Zustand des Protokolls erreichen und dann für immer aufhören zu sprechen), mit einem Rückgabewert, der ebenfalls ein bisschen ist.
  • Die Rückgabewerte müssen alle übereinstimmen (beachten Sie, dass dies nur für nicht-byzantinische Agenten gilt).
  • Wenn alle Eingangsbits gleich sind, müssen die Rückgabewerte gleich sein.

Das Unmöglichkeitsergebnis besagt, dass ein solches Protokoll genau dann existiert, wenn n>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).

Yuval Filmus
quelle
Vielen Dank für Ihre geduldige Erklärung :) Und ich habe die letzte Frage: Wie könnte ich den Beweis für die Unmöglichkeit eines synchronen Kommunikationsmodells finden? Der Beweis in Papierform "Einigung in Gegenwart von Fehlern erzielen" scheint nicht derjenige zu sein. Könnten Sie Literatur (z. B. Papier oder Buch) vorschlagen, die in hohem Maße mit dem Kommunikationsmodell mit byzantinischen Knoten zusammenhängt?
Lwins
Mir ist nur ein Beweis bekannt, und es ist der in der Zeitung. Den gleichen Beweis in einem etwas anderen Modell finden Sie in den Vorlesungsunterlagen von Chiu Yuen Koo .
Yuval Filmus
Hier ist ein Lehrbuch: Attiya und Welch, Distributed Computing: Grundlagen, Simulationen und fortgeschrittene Themen, zweite Ausgabe, Wiley, 2004.
Yuval Filmus