Wenn das Problem der beiden Generäle unlösbar ist, wie können wir Menschen uns dann auf Dinge einigen?

25

Wenn das Problem der beiden Generäle unlösbar ist, wie können wir Menschen uns dann auf Dinge einigen?

Ich meine, wir kommunizieren jeden Tag und haben dieselben Einschränkungen wie jedes Kommunikationsproblem in der Informatik. Warum betrifft es uns nicht?

user1508072
quelle
18
Wer hat dir gesagt, dass Menschen sich in irgendetwas anderem als in ihren Meinungsverschiedenheiten einig sind?
Babou
7
Die "Unlösbarkeit" des Problems "zwei Generäle" ist auf seinen Kontext beschränkt, dh auf ein vollständig asynchron verteiltes System mit unzuverlässigen, nicht vertrauenswürdigen Kommunikationskanälen. In unserem täglichen Leben können die Menschen sie "tolerieren". Übrigens, ich habe gerade eine andere Frage beantwortet, die eng mit Ihrer zusammenhängt.
Hengxin
4
@babou Leider können Leute (mit den gleichen Vorgesetzten) nicht einmal zustimmen, nicht zuzustimmen .
Hengxin
3
Nun, es ist im Allgemeinen unlösbar . Es gibt immer noch viele Fälle, in denen Sie die Probleme ignorieren und damit durchkommen können - der Großteil der menschlichen Kommunikation stützt sich darauf. Der Hauptgrund dafür, dass es sich um ein erhebliches Problem in der Informatik handelt, liegt in der Größenordnung. In jedem System, das bereits verteilt werden muss, treten diese Probleme wahrscheinlich gelegentlich auf, möglicherweise sogar täglich oder mehrmals. Dies ist ein großes Problem, wenn Sie sich stark auf die Korrektheit ohne Selbstkorrekturmechanismen verlassen. Ein näheres menschliches Analogon ist Chinese Whispers / Telephone - ein verteiltes System ohne Fehlerkorrektur.
Luaan
2
@AlecTeal Ich weiß nicht, woher die Gewissheit kommt, zu wissen, wie eine gute Informatik- Frage aussieht, aber auf jeden Fall: Bitte seien Sie nett. Missbrauch wird hier nicht toleriert. (Entfernen der nicht so schönen Teile Ihres Kommentars)
Raphael

Antworten:

29

Ich bin mit anderen Antworten nicht einverstanden, dass der Kommunikationskanal anders modelliert werden muss. Böswilligkeit ist irrelevant. Einfache verlorene Nachrichten mit einer Wahrscheinlichkeit ungleich Null reichen aus, um das Problem der beiden Generäle zu lösen. E-Mail und Sofortnachrichten haben beispielsweise eine geringe, aber keine Null-Chance, Nachrichten zu löschen. Telefonanrufe können Störungen hervorrufen. Wie bei dem Problem der beiden Generäle müssen Sie also irgendwie bestätigen, ob die andere Person ad infinitum gehört hat, was Sie gesagt haben. Und doch nutze ich diese Kanäle häufig, um Vereinbarungen mit anderen Menschen zu treffen.

Was das unlösbare "Zwei-Generäle" -Problem nicht löst, ist, garantiert allgemein bekannt zu werden. Im wirklichen Leben benötigen wir kein allgemeines formelles Wissen, um fortzufahren. Daher muss das Ziel in den meisten praktischen Situationen anders beschrieben werden als das Ziel in dem Problem der beiden Generäle.

Wir geben uns damit zufrieden, dass die Zustimmung "hinreichend wahrscheinlich" ist. Ich bin möglicherweise nicht bereit anzugreifen, es sei denn, ich bin sicher, dass Sie angreifen werden, aber ich bin bereit, zum Café zu gehen, um Sie zu treffen, vorausgesetzt, die Wahrscheinlichkeit eines Kommunikationsfehlers ist nicht grob höher als die Wahrscheinlichkeit, dass Sie dies nicht tun wegen verkehrs ankommen. Im Gegensatz zu den Generälen werde ich die Chance nutzen, mich zu treffen.

Wenn Sie sich zum ersten Mal dreimal auf unterschiedliche Weise von jemandem etwas erklären lassen oder von jemandem aufgefordert werden, etwas zu bestätigen, das Sie bereits zweimal bestätigt haben, dann liegt das daran, dass Sie die Schwelle von " ausreichend wahrscheinlich ", bevor sie ihre erreichten.

Wählen Sie Psychologie, Philosophie oder Evolutionsbiologie als den richtigen Bereich, um nach einer Antwort auf die nächste Frage zu suchen. Warum brauchen wir eigentlich keine umfassende Garantie für allgemeines Wissen ?:-)

Es bezieht sich auch auf praktische Probleme beim Rechnen. Wenn wir zum Beispiel mit einem einzigen Fehlerkorrekturcode "validieren", dass ein Symbol in einer Nachricht korrekt angekommen ist, akzeptieren wir nur, dass die Wahrscheinlichkeit eines Doppelfehlers vorerst vernachlässigbar ist. Dann, später im Protokoll, könnten wir eine CRC haben, um die Wahrscheinlichkeit eines unentdeckten Fehlers weiter zu verringern. Nichts davon löst das Problem der beiden Generäle, aber es genügt mir, meiner Bank und einem Händler, dass eine Kreditkartentransaktion stattgefunden hat, mit einer geringen Wahrscheinlichkeit, dass wir nicht zustimmen.

Steve Jessop
quelle
3
Böswilligkeit ist im praktischen Sinne bedeutsam, weil sie den Grad an Sicherheit einschränkt, der erreicht werden kann. Wenn man annimmt, dass eine Störung eher das Ergebnis zufälliger Zufallsfaktoren als von Böswilligkeit ist, kann man für jede Wahrscheinlichkeit p > 0 ein Protokoll so entwerfen, dass die Wahrscheinlichkeit eines fehlerhaften "Konsenses" geringer ist als p und die Wahrscheinlichkeit eines erfolgreichen Konsenses größer als 1-p. Gegen einen böswilligen und allwissenden Gegner können solche Algorithmen jedoch möglicherweise nicht viel bewirken.
Supercat
3
@supercat: OK. Mein Punkt ist jedoch, dass das Problem der beiden Generäle, das den Fragesteller betrifft, ein Problem bleibt, wenn Böswilligkeit ausgeschlossen wird: Die Unmöglichkeit ist eine Folge von Irrtum, nicht von Böswilligkeit. Ich würde sagen, dass das Problem idealerweise so gestaltet sein sollte, dass die fehlenden Botschaften nicht die Folge feindlicher Handlungen sein müssen. Wir wissen nur, dass einige Botschaften in die Irre gehen. Das Problem der byzantinischen Generäle führt jedoch ausdrücklich gegnerische Spieler ein.
Steve Jessop
Die beiden Generäle sollten sich also zunächst darauf einigen, gemeinsam Kaffee zu trinken. Dann können sie den Kampf von Angesicht zu Angesicht planen, was ihnen einen zuverlässigen Kanal gibt!
David Richerby
1
@DavidRicherby: In der Tat funktioniert dies sehr gut in Kriegsschauplätzen, die mit Cafés gut ausgestattet sind. Informatiker treffen sehr selten auf ein anderes Terrain, so dass die wahren Generäle in Bezug auf die CS-Theorie so ziemlich auf sich allein gestellt sind. Und existentialistische Generäle haben keinen verlässlichen Kanal, auch nicht von Angesicht zu Angesicht. Sie greifen niemanden an, weil sie nicht sicher sein können, ob ihre Verbündeten existieren, geschweige denn der Feind.
Steve Jessop
Da es sich um Informatik handelt und Sie die Kanalkapazität erraten können, ist diese Antwort möglicherweise besser, wenn sie mit Shannons Theorem verknüpft und diskutiert wird: en.wikipedia.org/wiki/Noisy-channel_coding_theorem
daniel
18

Zentral (Wortspiel beabsichtigt) für das Zwei-Generäle-Problem ist ein böswilliger Feind dazwischen. Obwohl dies einen unzuverlässigen Kanal modelliert, modelliert es ihn auf eine Weise, auf die wir normalerweise nicht stoßen. Bei diesem Problem werden die Nachrichten möglicherweise durch feindliche Hände weitergeleitet, und es gibt keine Zeitbeschränkungen, Überprüfungen, Verschlüsselungen oder andere Dinge, an die ich nicht gedacht habe.

Wenn wir in der Praxis kommunizieren, wird zunächst nicht erwartet, dass die von uns verwendeten Kanäle auf diese Weise unzuverlässig sind. Kanäle können zwar laut sein, aber das ist etwas anderes als böswillig. Die Wahrscheinlichkeit, dass ein Kanal, der auf Bitebene verrauscht ist, zufällig nicht nur eine gültige Nachricht erzeugt, die den von uns verwendeten Fehlerkorrekturcode erfüllt, sondern auch insofern gültig ist, als dies für den Empfänger sinnvoll ist, ist sehr gering. Wir können auch Dinge wie die Kryptografie mit öffentlichen Schlüsseln verwenden, um Nachrichten zu verschlüsseln und / oder zu signieren, wodurch es wieder schwieriger wird, eine echte Nachricht zu fälschen. Drittens ist ein erheblicher Teil unserer Kommunikation zeitkritisch - wir sprechen tatsächlich mit Menschen, sodass es keine Verzögerung bei der Antwort gibt. In diesem Fall müssen wir uns davon überzeugen, dass die Person, mit der wir sprechen, die Person ist, mit der wir sprechen sollen zu.

In den meisten Fällen gehen wir lediglich davon aus, dass die Nachrichten keine signifikante Fehlerquelle aufweisen, und kommen damit durch. Wir können uns ein Szenario vorstellen, in dem wirklich ein böswilliger Mann in der Mitte den Kanal beschädigt, aber wir stoßen auf ein paar Dinge. Die Verschlüsselung mit öffentlichen Schlüsseln ist immer noch wirksam, aber was noch wichtiger ist, der Aufwand und die Leistung, die erforderlich sind, um einen ausreichend wichtigen Teil der Kommunikation genau zu beschädigen, liegen weit über dem Machbaren. Wenn dies nicht der Fall wäre, wäre die militärische Signalaufklärung weitaus effektiver als sie ist (nicht, dass sie nicht effektiv ist, sie wäre einfach besser).

Beachten Sie, dass ich zwar hauptsächlich die computer- / maschinenvermittelte Kommunikation angesprochen habe, für die zwischenmenschliche Kommunikation jedoch dieselben Argumente angeführt werden können - die Geräuschquellen können normalerweise nicht eine ganze Nachricht vortäuschen Lärm, und der Aufwand lohnt sich einfach nicht in jedem Fall, damit es einen ausreichend ausgestatteten und motivierten Angreifer gibt.

Luke Mathieson
quelle
7
AFAIK, das Problem der beiden Generäle, erfordert keinen schädlichen Kommunikationskanal, sondern nur einen unzuverlässigen. Das Problem besteht nicht darin, dass Nachrichten beschädigt oder geändert werden. nur mit ihnen nicht erhalten: en.wikipedia.org/wiki/…
Ajedi32
1
@ Ajedi32, ich sollte klarstellen, was ich meine - die metaphorische Anordnung hat einen böswilligen Feind, die Boten wandern nicht nur ab, sondern was dies am ehesten bedeuten würde, ist der Verlust ganzer Nachrichten ohne Wahrscheinlichkeitsmodell. Da wir keine Nachrichten als atomare Einheiten senden, kann der "Verlust einer Nachricht" als Verlust von Bits, Verlust von Paketen usw. interpretiert werden. Die andere Hälfte ist, dass Kommunikationskanäle analysierbare Eigenschaften haben - sie können zufälliges Rauschen aufweisen. aber es ist in einer modellfähigen Weise, mit der wir nachweislich fertig werden können, dann ist die einzige andere Quelle für Informationsverlust ...
Luke Mathieson
... tatsächlich böswilliges Verhalten, das wir auch bemerkbar machen können. Kurz gesagt, das Problem der beiden Generäle ergibt eine hypothetische Situation, die in ihren Annahmen unrealistisch ist. Ja, irgendwo könnten Informationen verloren gehen, aber es gibt (in alltäglichen, vernünftigen Situationen) keine unbegrenzten Fehler.
Luke Mathieson
16

Die "Unlösbarkeit" des "Two Generals" -Problems (oder "Coordinated Attack" -Problem) ist auf seinen Kontext beschränkt, dh auf ein vollständig asynchron verteiltes System mit unzuverlässigen, nicht vertrauenswürdigen Kommunikationskanälen. In unserem täglichen Leben können Menschen solche schlechten Situationen "tolerieren".

In dem Buch Reasoning about Knowledge ; Abschnitt 6.1 , die Autoren kommentieren das

Die Tatsache, dass ein koordinierter Angriff allgemein bekannt ist, hängt von unserer Anforderung ab, dass der koordinierte Angriff gleichzeitig erfolgen muss . In der Praxis kann Gleichzeitigkeit eine zu starke Anforderung sein. Ein Protokoll, das garantiert, dass die Generäle innerhalb kurzer Zeit aufeinander losgehen, kann durchaus zufriedenstellend sein.

Er kommentiert das weiter

Trotzdem sind selbst solche schwächeren Formen der Koordination nicht erreichbar, wenn die Kommunikation unzuverlässig ist .

In unserem täglichen Leben tolerieren (und tolerieren) die Menschen kurze Verzögerungen und unzuverlässige Kanäle (wie von Luke Mathieson herausgearbeitet). (Wenn Sie tiefer gehen und nach dem "Wie" und "Warum" fragen, dann liegt dies wahrscheinlich außerhalb des Rahmens der Informatik.)

Hengxin
quelle
2
Wenn Sie sich mit moderner Kommunikation beschäftigen, insbesondere im Krieg, wird große Sorgfalt darauf verwendet, Strategien auszuwählen, die nicht von solchen Problemen abhängen. Wenn sie von solchen Problemen abhängen, gibt es fast immer einen Notfallplan, um sich damit zu befassen. Im Informatik-Programm legen wir alle unsere Eier in einen Korb und erklären, dass "jeder mögliche Fehler, egal wie unwahrscheinlich er ist, zu viel ist"
Cort Ammon - Reinstate Monica
3

Weil wir keine garantierte Gewissheit brauchen, dass etwas passieren wird , wenn wir über ausreichende Erfahrung verfügen , die uns sagt, was wahrscheinlich ist . Nehmen wir zum Beispiel an, ein Freund möchte sich mit mir treffen. Er schickt mir eine E-Mail mit Zeit und Ort und ich antworte mit "Hört sich toll an, wir sehen uns dann." Ich benötige keine weiteren Informationen, um ihn am angegebenen Ort und zur angegebenen Zeit zu treffen. Nur weil ich nicht garantieren konnteDass er meine Antwort erhalten hat, reicht nicht aus, um mich davon abzuhalten, nach meinen Annahmen zu handeln. Meine Erfahrung zeigt mir, dass E-Mails ziemlich zuverlässig sind und dass er mich erneut per E-Mail benachrichtigt, wenn er aus irgendeinem Grund meine Antwort nicht erhalten hat. Meine Erfahrung sagt mir, dass ich mir keine Sorgen machen soll, wenn meine Antwort stillschweigend verworfen wird und alle Follow-up-Nachrichten von ihm ebenfalls stillschweigend verworfen werden. Diese Kombination von Ereignissen kommt einfach nicht oft genug vor, um meine Fähigkeit, Leute zu treffen, erheblich zu beeinträchtigen.

Wenn diese Eckfälle (oder andere Probleme) häufiger auftreten würden, würde dies meine Erfahrung ändern , und dann würde ich eine Änderung meiner Strategie in Betracht ziehen. Zum Beispiel könnte ich die Person anrufen, anstatt sie per E-Mail zu kontaktieren. Oder ich verwende eine Kalenderwebsite. Oder eine andere Option.

In Bezug auf die zwischenmenschliche Kommunikation stelle ich fest, dass die technischen Probleme des Zwei-Generäle-Problems für sich genommen nicht sehr problematisch sind, aber andere Probleme vergrößern können. Was kann ich tun, wenn ich jemandem eine Arbeitsanfrage per E-Mail sende und von ihm innerhalb eines angemessenen Zeitraums keine Antwort erhalte? Wie lange sollte ich warten, bevor ich eine Follow-up-Nachricht sende? Wenn ich eine Follow-up-Nachricht sende, werden sie diese als freundliche Erinnerung betrachten oder werden sie sich irritiert fühlen? Wie soll ich die Follow-up-Nachricht formulieren, um nicht zu anmaßend zu wirken (denn wenn das Netzwerk die vorherige Nachricht tatsächlich verworfen hat, ist dies das erste, das sie von mir hören)?

Die Art dieser Fragen hängt von den Personen und dem jeweiligen Kontext ab. Es gibt keine garantierten Antworten. Aber auch hier brauchen wir keine Garantien, um erfolgreich zu sein. Alles, was wir brauchen, sind Dinge wie Selbstbeobachtung, Empathie und die Fähigkeit, aus Erfahrungen zu lernen. Wir können unsere eigenen einzigartigen Strategien entdecken und entwickeln - die sich durchaus von anderen unterscheiden können -, die es uns ermöglichen, mit der Zeit bessere Kommunikatoren zu werden.

kartik_subbarao
quelle
-1

Können Sie mir den genauen Wert von pi in Dezimalschreibweise geben? Wir Menschen runden ab und ungefähr, wenn wir wissen, dass der genaue Wert unlösbar ist.

RajuK
quelle
2
Herzlich willkommen! Wir suchen nach Antworten, die einige Details und Erklärungen enthalten, anstatt nur kurze Kommentare. Die Idee in Ihrem Kommentar wurde bereits in den vorhandenen Antworten auf die Frage ausführlich besprochen, sodass ich glaube, dass Sie hier überhaupt nichts hinzufügen.
David Richerby
Mein Kommentar ist kurz und bündig. Die umschriebene Frage war, wie sich Menschen auf etwas einigen können, wenn wir wissen, dass ein Problem nicht lösbar ist. Meine Antwort stammt aus der Mathematik (speziell Pi in Dezimal), die wir abrunden und approximieren.
Rajuk
Ihr Kommentar ist genau das: ein Kommentar. Wenn Sie über eine ausreichende Reputation verfügen, können Sie Kommentare veröffentlichen. Bis dahin können Sie nur Antworten veröffentlichen, und es wird erwartet, dass die Antworten detaillierter sind, wie ich bereits erläutert habe.
David Richerby
Die Frage als solche ist keine comp-naturwissenschaftliche Frage, sondern eine Frage zum menschlichen Verhalten. Daher war meine Antwort auf den Punkt. Warum wurde die Frage nicht als Nicht-Informatik-Frage markiert und abgelehnt?
Rajuk
Wenn Sie der Meinung sind, dass die Frage nicht zum Thema gehört, sollten Sie sie markieren und nicht beantworten. Bitte beachten Sie auch, dass Stack Exchange-Sites (auch Kommentare dazu) keine Diskussionsrunden sind.
David Richerby
-1

Der Beweis besagt nur, dass es unmöglich ist, ein Protokoll zu entwerfen, das das Problem zuverlässig löst (dh in jedem Fall perfekt).

Es heißt nicht, dass es unmöglich ist, ein Protokoll zu entwerfen, das das Problem meistens löst. Menschen, die bayesianischer Natur sind, können sehr gut Protokolle entwerfen, die ein bestimmtes Problem mit einem gewissen Grad an Qualität und / oder Erfolg lösen, der in Bezug auf Gewinne und Verluste auf lange Sicht zufriedenstellend ist.

Nirgendwo, Mann
quelle