Jeśli problem dwóch generałów jest nierozwiązywalny, jak my, ludzie, możemy się zgodzić na różne rzeczy?

25

Jeśli problem dwóch generałów jest nierozwiązywalny, jak my, ludzie, możemy się zgodzić na różne rzeczy?

Chodzi mi o to, że komunikujemy się codziennie i mamy takie same ograniczenia jak każdy problem komunikacyjny obsługiwany przez informatykę. Dlaczego nas to nie dotyczy?

użytkownik1508072
źródło
18
Kto powiedział wam, że ludzie kiedykolwiek zgadzają się na cokolwiek innego niż ich nieporozumienia?
babou
7
„Nierozwiązalność” problemu „dwóch generałów” ogranicza się do jego kontekstu, tj. W całkowicie asynchronicznym systemie rozproszonym z niewiarygodnymi, niezaufanymi kanałami komunikacyjnymi. W naszym codziennym życiu ludzie mogą je „tolerować”. Nawiasem mówiąc, właśnie odpowiedziałem na inne pytanie, które jest ściśle związane z twoim.
hengxin
4
@babou Niestety, ludzie (z tymi samymi priorytetami) nie mogą nawet zgodzić się z tym nie zgodzić .
hengxin
3
Cóż, ogólnie jest to nierozwiązywalne . Nadal istnieje wiele przypadków, w których możesz zignorować problemy i uciec od nich - większość komunikacji międzyludzkiej zależy od tego. Głównym powodem, dla którego jest to poważny problem w informatyce, jest raczej powód skali - w każdym systemie, który już musi być dystrybuowany, prawdopodobnie pojawiają się te problemy od czasu do czasu, być może nawet codziennie lub więcej. Jest to duży problem, jeśli polegasz w dużej mierze na poprawności, bez mechanizmów samoregulacji. Bardziej ludzkim analogiem są chińskie szepty / telefon - system rozproszony bez korekcji błędów.
Luaan
2
@AlecTeal Nie wiem, skąd bierze się pewność, jak dobrze wygląda pytanie z informatyki , ale w każdym razie: bądź miły. Wykorzystywanie innych nie będzie tutaj tolerowane. (usuwając niezbyt miłe części twojego komentarza)
Raphael

Odpowiedzi:

29

Nie zgadzam się z innymi odpowiedziami, że kanał komunikacji musi być inaczej modelowany. Złośliwość jest nieistotna, proste utracone wiadomości o niezerowym prawdopodobieństwie są wystarczające, aby stworzyć problem dwóch generałów. Na przykład wiadomości e-mail i wiadomości błyskawiczne mają małą, ale nie zerową szansę na upuszczenie wiadomości. Rozmowy telefoniczne mogą być zakłócane, tak jak w przypadku problemu dwóch generałów musisz w jakiś sposób potwierdzić, czy druga osoba usłyszała to, co powiedziałeś, bez końca. A jednak często używam tych kanałów do zawierania umów z innymi ludźmi.

Tym, czego nierozwiązalny problem „dwóch generałów” nie rozwiązuje, jest zagwarantowanie powszechnej wiedzy. W prawdziwym życiu nie potrzebujemy formalnej wspólnej wiedzy, aby kontynuować. Dlatego cel w większości praktycznych sytuacji musi być opisany inaczej niż cel w problemie dwóch generałów.

Zgadzamy się na to, że porozumienie jest „wystarczająco prawdopodobne”. Być może nie będę skłonny zaatakować, chyba że jestem pewien , że zaatakujesz, ale jestem gotów pójść do kawiarni, aby się z tobą spotkać, pod warunkiem, że prawdopodobieństwo awarii komunikacji nie jest rażąco wyższe niż prawdopodobieństwo, że nie uda ci się przybyć z powodu ruchu. W przeciwieństwie do generałów, zaryzykuję spotkanie ze mną.

Jeśli kiedykolwiek ktoś powiedział ci coś trzy razy na różne sposoby, kiedy dostałeś to po raz pierwszy, lub ktoś poprosił Cię o potwierdzenie czegoś, co już potwierdziłeś dwa razy, to dlatego, że osiągnąłeś próg „ wystarczająco prawdopodobne ”, zanim dotarli do swoich.

Wybierz psychologię, filozofię lub biologię ewolucyjną jako właściwą dziedzinę, w której szukasz odpowiedzi na następne pytanie, dlaczego tak naprawdę nie potrzebujemy pełnej gwarancji powszechnej wiedzy :-)

Odnosi się także do praktycznych problemów w informatyce. Na przykład, gdy używamy kodu korygującego pojedynczy błąd, aby „potwierdzić”, że symbol w wiadomości dotarł poprawnie, wszystko, co robimy, to akceptacja faktu, że prawdopodobieństwo podwójnego błędu jest na razie nieistotne. Następnie w protokole możemy mieć CRC, aby dodatkowo zmniejszyć prawdopodobieństwo niewykrycia błędu. Nic z tego nie rozwiązuje problemu dwóch generałów, ale dla mnie, mojego banku i akceptanta wystarczy „zgodzić się”, że doszło do transakcji kartą kredytową, z małym prawdopodobieństwem, że się nie zgadzamy.

Steve Jessop
źródło
3
Złośliwość jest znacząca w sensie praktycznym, ponieważ ogranicza stopień pewności, którą można osiągnąć. Jeśli przyjmie się, że interferencja jest wynikiem losowych czynników losowych, a nie wrogości, wówczas dla dowolnego prawdopodobieństwa p > 0 można zaprojektować protokół tak, aby prawdopodobieństwo błędnego „konsensusu” było mniejsze niż p, a prawdopodobieństwo pomyślnego konsensusu wyniesie większy niż 1-p. Jednak przeciw wrogowi, który jest wrogi i wszechwiedzący, takie algorytmy mogą nie być w stanie wiele osiągnąć.
supercat
3
@ supercat: OK. Chodzi mi jednak o to, że problem dwóch generałów, który dotyczy pytającego, pozostaje problemem, gdy wykluczona jest złośliwość: niemożliwość jest konsekwencją błędu, a nie złośliwości. Powiedziałbym, że idealnie problem powinien być tak sformułowany, aby brakujące wiadomości nie musiały być konsekwencją działań wroga, po prostu wiemy, że niektóre wiadomości zbłądzą. Jednak problem generałów bizantyjskich wyraźnie przedstawia przeciwników.
Steve Jessop
Więc dwaj generałowie powinni najpierw zgodzić się na wspólną kawę. Następnie mogą zaplanować bitwę twarzą w twarz, co daje im niezawodny kanał!
David Richerby,
1
@DavidRicherby: rzeczywiście działa to wyjątkowo dobrze w teatrach wojennych, które są dobrze wyposażone w kawiarniach. Informatycy bardzo rzadko spotykają się z jakimkolwiek innym terenem, więc prawdziwi generałowie są dość sami, jeśli chodzi o teorię CS. A egzystencjaliści generałowie nie mają niezawodnego kanału, nawet twarzą w twarz, więc nigdy nikogo nie atakują, ponieważ nie mogą mieć pewności, że ich sojusznicy istnieją, nie mówiąc już o wrogu.
Steve Jessop,
Ponieważ jest to informatyka i można odgadnąć pojemność kanału, ta odpowiedź mogłaby być lepsza, gdyby odniosła się do twierdzenia Shannona i przedyskutowała je: en.wikipedia.org/wiki/Noisy-channel_coding_theorem
Daniel
18

Centralny (przeznaczony kalambur) problem Dwóch Generałów jest złośliwym wrogiem pomiędzy nimi. Chociaż modeluje to nierzetelny kanał, modeluje go w sposób, którego zwykle nie spotykamy. W tym problemie wiadomości mogą przechodzić przez ręce wroga i nie ma żadnych ograniczeń czasowych, weryfikacji, szyfrowania ani niczego innego, o czym nie myślałem.

Kiedy komunikujemy się w praktyce, po pierwsze nie oczekuje się, że kanały, z których korzystamy, będą zawodne w ten sposób. Oczywiście kanały mogą być hałaśliwe, ale różni się to od złośliwości. Prawdopodobieństwo, że kanał, który jest zaszumiony na poziomie bitów, może losowo wygenerować nie tylko prawidłowy komunikat, który spełnia dowolny kod korygujący błąd, którego używamy, ale jest również prawidłowy, ponieważ ma sens dla odbiornika, jest bardzo niski. Możemy również wykorzystywać takie elementy, jak kryptografia klucza publicznego do szyfrowania i / lub podpisywania wiadomości, co utrudnia fałszywe wiadomości. Po trzecie, znaczna część naszej komunikacji jest wrażliwa na czas - faktycznie rozmawiamy z ludźmi, więc nie ma opóźnienia w odpowiedzi, w takim przypadku będziemy musieli być zadowoleni, że osoba, z którą rozmawiamy, to osoba, z którą mamy rozmawiać do.

W większości przypadków zakładamy po prostu, że w komunikatach nie ma żadnego istotnego źródła błędu i nie możemy tego zrobić. Możemy sobie wyobrazić scenariusz, w którym naprawdę złośliwy człowiek w środku korumpuje kanał, ale natrafiamy na kilka rzeczy; krypto klucza publicznego jest nadal skuteczne, ale co ważniejsze, wysiłek i moc potrzebne do dokładnego zepsucia wystarczająco znacznej części komunikacji znacznie wykraczają poza to, co jest możliwe. Gdyby tak nie było, inteligencja sygnałów wojskowych byłaby znacznie bardziej skuteczna niż jest (nie dlatego, że nie jest skuteczna, po prostu byłoby lepiej).

Zauważ, że chociaż głównie poruszałem komunikację za pośrednictwem komputera / maszyny, te same argumenty można wysunąć w celu komunikacji interpersonalnej - źródła hałasu zwykle nie mogą sfałszować całej wiadomości, mamy systemy korekcji dla tych, które wprowadzają losowe, niskopoziomowe hałas, a wysiłek po prostu nie jest tego wart w prawie każdym przypadku, aby istniał wystarczająco zasobów i zmotywowany złośliwy atakujący.

Luke Mathieson
źródło
7
AFAIK, problem dwóch generałów nie wymaga złośliwego kanału komunikacji, tylko niewiarygodnego. Problem nie polega na tym, że wiadomości są uszkodzone lub zmodyfikowane; tylko przy ich braku: en.wikipedia.org/wiki/…
Ajedi32
1
@ Ajedi32, powinienem wyjaśnić, co mam na myśli - konfiguracja metaforyczna ma złośliwego wroga, posłańcy nie tylko odchodzą, ale to, co najbardziej natychmiast to równoważy, to utrata całych wiadomości bez modelu prawdopodobieństwa. Biorąc pod uwagę, że nie wysyłamy wiadomości jako jednostek atomowych, „utratę wiadomości” można interpretować jako utratę bitów, utratę pakietów itp. Drugą połową jest to, że kanały komunikacyjne mają analizowalne właściwości - mogą mieć losowy szum, ale jest to modelowe podejście, z którym możemy sobie poradzić, wtedy jedynym innym źródłem utraty informacji jest ...
Luke Mathieson,
... faktyczne złośliwe zachowanie, które możemy również zauważyć. Krótko mówiąc, problem dwóch generałów daje hipotetyczną sytuację, która jest nierealna w swoich założeniach. Tak, może gdzieś utracić informacje, ale nie ma (w codziennych rozsądnych sytuacjach) nieograniczonych błędów.
Luke Mathieson,
16

„Nierozwiązywalność” problemu „Dwóch generałów” (lub zwanego problemem „skoordynowanego ataku”) jest ograniczona do jego kontekstu, tj. W całkowicie asynchronicznym systemie rozproszonym z niewiarygodnymi, niezaufanymi kanałami komunikacyjnymi. W naszym codziennym życiu ludzie mogą „tolerować” takie złe sytuacje.

W książce Rozumowanie o wiedzy ; Sekcja 6.1 , autorzy komentują to

Fakt, że skoordynowany atak wymaga powszechnej wiedzy, zależy od naszego wymogu, że skoordynowany atak musi być jednoczesny . W praktyce jednoczesność może być zbyt silnym wymogiem. Protokół, który gwarantuje, że generałowie zaatakują w krótkim czasie, może być całkiem zadowalający.

Dalej komentuje to

Niemniej jednak nawet takie słabsze formy koordynacji są nieosiągalne, jeśli komunikacja jest zawodna .

W naszym codziennym życiu ludzie mogą tolerować (i tolerują) krótkie opóźnienia i niewiarygodne kanały (opracowane przez @Luke Mathieson). (Jeśli wejdziesz głębiej i zapytasz „jak” i „dlaczego”, prawdopodobnie nie jest to objęte informatyką).

hengxin
źródło
2
Jeśli spojrzysz na nowoczesną komunikację, zwłaszcza na wojnie, bardzo ostrożnie wybierasz strategie, które nie zależą od takich problemów. Gdy zależą od takich problemów, prawie zawsze istnieje jakiś plan awaryjny, aby sobie z tym poradzić. W programie informatycznym umieszczamy wszystkie nasze jajka w jednym koszyku i deklarujemy, że „każda potencjalna awaria, bez względu na to, jak nieprawdopodobna, jest zbyt duża”
Cort Ammon - Przywróć Monikę
3

Ponieważ nie potrzebujemy gwarantowanej gwarancji, że coś się wydarzy, gdy będziemy mieli wystarczające doświadczenie, które mówi nam, co może się wydarzyć. Powiedzmy na przykład, że przyjaciel chce się ze mną spotkać. Prześle mi e-mailem czas i miejsce, a ja odpowiadam: „Brzmi świetnie, do zobaczenia”. Nie potrzebuję więcej informacji, aby móc się z nim spotkać w określonym miejscu i czasie. Tylko dlatego, że nie mogłem zagwarantowaćto, że dostał moją odpowiedź, nie wystarczy, by przekonać mnie do działania zgodnie z moimi założeniami. Moje doświadczenie mówi mi, że e-mail jest dość niezawodny i że jeśli z jakiegoś powodu nie otrzyma mojej odpowiedzi, prześle mi e-maila. Z mojego doświadczenia wynika, że ​​nie muszę się martwić, że moja odpowiedź zostanie cicho odrzucona, a wszystkie dalsze wiadomości od niego również zostaną po cichu odrzucone. Ta kombinacja wydarzeń po prostu nie zdarza się wystarczająco często, aby znacząco zakłócać moją zdolność do poznawania ludzi.

Jeśli te narożne przypadki (lub inne problemy) zaczęły się zdarzać częściej, to zmieniłoby moje doświadczenie , a następnie rozważyłbym zmianę mojej strategii. Na przykład mogę zadzwonić do tej osoby, zamiast wysyłać jej e-mailem. Albo mogę skorzystać z witryny kalendarza. Lub inna opcja.

W odniesieniu do komunikacji interpersonalnej uważam, że problemy techniczne problemu dwóch generałów same w sobie nie są bardzo problematyczne, ale mogą powiększać inne problemy. Jeśli wyślę komuś e-mail z prośbą o pracę i nie otrzymam od niego odpowiedzi w rozsądnym czasie, co mam zrobić? Jak długo powinienem się powstrzymywać przed wysłaniem wiadomości? Jeśli wyślę wiadomość uzupełniającą, czy uznają ją za przyjazne przypomnienie, czy też poczują się zirytowani? Jak mam sformułować wiadomość uzupełniającą, aby nie wydawać się zbyt zarozumiała (ponieważ jeśli sieć faktycznie upuściła poprzednią wiadomość, to jest to pierwsza wiadomość ode mnie)?

Charakter tych pytań zależy od ludzi i kontekstu. Nie ma żadnych gwarantowanych odpowiedzi. Ale znowu nie potrzebujemy gwarancji, aby odnieść sukces. Wszystko, czego potrzebujemy, to introspekcja, empatia i umiejętność uczenia się na podstawie doświadczenia. Możemy odkrywać i rozwijać własne unikalne strategie - które mogą się różnić od innych - które pozwalają nam z czasem stać się lepszymi komunikatorami.

kartik_subbarao
źródło
-1

Czy możesz podać mi dokładną wartość pi w notacji dziesiętnej? My ludzie zaokrąglamy i przybliżamy, gdy wiemy, że dokładna wartość jest nierozwiązywalna.

RajuK
źródło
2
Witamy! Szukamy odpowiedzi, które zawierają pewne szczegóły i wyjaśnienia, a nie tylko krótkie komentarze. Pomysł w twoim komentarzu został już szczegółowo omówiony w istniejących odpowiedziach na pytanie, więc nie sądzę, żebyś tu w ogóle coś dodawał.
David Richerby,
Mój komentarz jest zwięzły i na temat. Sparafrazowano pytanie, w jaki sposób ludzie zgadzają się na cokolwiek, jeśli wiemy, że problem jest nierozwiązywalny? Moja odpowiedź pochodzi z matematyki (w szczególności liczby dziesiętne), które zaokrąglamy i przybliżamy.
RajuK,
Twój komentarz jest taki: komentarz. Gdy będziesz mieć wystarczającą reputację, będziesz mógł dodawać komentarze. Do tego czasu możesz publikować tylko odpowiedzi, a odpowiedzi powinny być bardziej szczegółowe, jak już wyjaśniłem.
David Richerby,
Pytanie jako takie nie jest pytaniem naukowym, ale pytaniem o ludzkie zachowanie. Dlatego moja odpowiedź była na temat. Dlaczego pytanie nie zostało oznaczone jako pytanie niebędące informatyką i odrzucone?
RajuK,
Jeśli uważasz, że pytanie jest nie na temat, powinieneś je oflagować i nie odpowiadać. Należy również pamiętać, że witryny Stack Exchange (nawet komentarze na ich temat) nie są przeznaczone do dyskusji.
David Richerby,
-1

Dowód mówi tylko, że niemożliwe jest zaprojektowanie protokołu, który niezawodnie rozwiąże problem (tj. Doskonale w każdym przypadku).

Nie oznacza to, że nie można zaprojektować protokołu, który w większości rozwiązuje problem. Ludzie, mając charakter bayesowski, są całkiem dobrzy w projektowaniu protokołów, które rozwiązują dany problem z pewnym stopniem jakości i / lub pewnym stopniem sukcesu, który jest zadowalający pod względem zysków i strat w długim okresie.

Człowiek znikąd
źródło