Если проблема двух генералов неразрешима, как мы, люди, можем договориться о вещах?

25

Если проблема двух генералов неразрешима, как мы, люди, можем договориться о вещах?

Я имею в виду, что мы общаемся каждый день и имеем те же ограничения, что и любая проблема общения, которую решает информатика. Почему это не влияет на нас?

user1508072
источник
18
Кто сказал вам, что люди когда-либо соглашаются на что-то кроме своих разногласий?
Бабу
7
«Неразрешимость» проблемы «двух общих» ограничена ее контекстом, т. Е. В полностью асинхронной распределенной системе с ненадежными, ненадежными каналами связи. В нашей повседневной жизни люди могут "терпеть" их. Кстати, я только что ответил на другой вопрос, который тесно связан с вашим.
hengxin
4
@babou К сожалению, люди (с одинаковыми приоритетами) не могут даже согласиться не соглашаться .
hengxin
3
Ну, это вообще неразрешимо . Есть еще много случаев, когда вы можете игнорировать проблемы и сойти с рук - большая часть человеческого общения зависит от этого. Основная причина того, что это серьезная проблема в информатике, в значительной степени является причиной масштаба - в любой системе, которая уже должна быть распространена, вы, вероятно, время от времени получаете эти проблемы, возможно, даже ежедневно или больше. Это большая проблема, если вы сильно полагаетесь на правильность, без механизмов самокоррекции. Более близким человеческим аналогом является китайский шепот / телефон - распределенная система без исправления ошибок.
Луаан
2
@AlecTeal Я не знаю, откуда наверняка узнать, как выглядит хороший вопрос по информатике , но в любом случае: пожалуйста, будьте милы. Оскорблять других здесь не допустимо. (удаляя не очень приятные части вашего комментария)
Рафаэль

Ответы:

29

Я не согласен с другими ответами, что канал связи должен быть смоделирован по-другому. Злоба не имеет значения, простых потерянных сообщений с любой ненулевой вероятностью достаточно, чтобы создать проблему двух генералов. электронная почта и IM, например, имеют низкую, но не нулевую вероятность отбрасывать сообщения. Телефонные звонки могут испытывать помехи, так как в случае двух общих проблем вам нужно каким-то образом подтвердить, слышал ли другой человек то, что вы сказали, до бесконечности. И все же я часто использую эти каналы для заключения соглашений с другими людьми.

То, что не может решить неразрешимая проблема «двух генералов», - это получить гарантированное общее знание. В реальной жизни нам не нужны формальные общие знания, чтобы продолжить. Поэтому цель в большинстве практических ситуаций должна быть описана иначе, чем цель в двух общих задачах.

Мы согласны с тем, что соглашение «достаточно вероятно». Возможно, я не буду готов атаковать, если я не уверен, что вы будете атаковать, но я готов пойти в кафе, чтобы встретиться с вами, при условии, что вероятность сбоя связи не намного выше, чем вероятность того, что вы не сможете это сделать. прибыть из-за движения. В отличие от генералов, я рискну, если вы встретите меня.

Если вам когда-нибудь приходилось кого-то трижды объяснять вам по-разному, когда вы получили это впервые, или когда-либо кто-то просил вас подтвердить то, что вы уже дважды подтвердили, то это потому, что вы достигли своего порога " достаточно вероятно, "прежде чем они достигли их.

Выбирайте психологию, философию или эволюционную биологию в качестве правильной области, в которой нужно искать ответ на следующий вопрос, почему нам не нужна полная гарантия общих знаний :-)

Это также относится к практическим проблемам в области вычислительной техники. Например, когда мы используем код, исправляющий одну ошибку, чтобы «проверить», что символ в сообщении прибыл правильно, все, что мы делаем, это признаем, что вероятность двойной ошибки в настоящее время незначительна. Затем позже в протоколе мы могли бы иметь CRC, чтобы еще больше снизить вероятность необнаруженной ошибки. Ничто из этого не решает проблему двух генералов, но мне, моему банку и торговцу достаточно «согласиться» на то, что произошла транзакция по кредитной карте, с небольшой вероятностью того, что мы не согласны.

Стив Джессоп
источник
3
Злоба имеет важное значение в практическом смысле, потому что она ограничивает степень уверенности, которая может быть достигнута. Если предположить, что помехи являются результатом случайных факторов, а не недоброжелательности, то для любой вероятности p > 0 можно разработать протокол так, чтобы вероятность ошибочного «консенсуса» была меньше p, а вероятность успешного консенсуса - больше 1-р. Однако против злонамеренного и всезнающего противника такие алгоритмы могут быть неспособны достичь многого.
суперкат
3
@supercat: ОК. Но я хочу сказать, что проблема двух общих вопросов, которая касается спрашивающего, остается проблемой, когда злоба исключена: невозможность является следствием ошибки, а не злобы. Я бы сказал, что в идеале проблема должна быть сформулирована так, чтобы пропущенные сообщения не были следствием действий противника, мы просто знаем, что некоторые сообщения сбиваются с пути. Однако проблема византийских генералов явно вводит противоборствующих игроков.
Стив Джессоп
Поэтому два генерала должны сначала договориться о кофе вместе. Тогда они могут планировать сражение лицом к лицу, что дает им надежный канал!
Дэвид Ричерби
1
@DavidRicherby: действительно, это очень хорошо работает на театрах военных действий, которые хорошо оборудованы кафе. Компьютерные ученые очень редко сталкиваются с какой-либо другой местностью, поэтому реальные генералы в значительной степени самостоятельны в том, что касается теории КС. И у генералов-экзистенциалистов нет надежного канала даже лицом к лицу, поэтому они никогда не нападают на кого-либо, потому что не могут быть уверены, что их союзники существуют, не говоря уже о враге.
Стив Джессоп
Так как это информатика, и вы можете догадаться о пропускной способности канала, этот ответ мог бы быть лучше, если бы он связался с теоремой Шеннона и обсудил ее: en.wikipedia.org/wiki/Noisy-channel_coding_theorem
Даниэль
18

Центральная (каламбур) проблема двух генералов - злобный враг между ними. Хотя это моделирует ненадежный канал, он моделирует его таким образом, с которым мы обычно не сталкиваемся. В этой проблеме сообщения могут проходить через руки противника, и нет никаких временных ограничений, проверки, шифрования или чего-либо еще, о чем я не думал.

Когда мы общаемся на практике, во-первых, не ожидается, что используемые нами каналы будут ненадежными. Конечно, каналы могут быть шумными, но это не то же самое, что быть вредоносным. Вероятность того, что канал с шумом на уровне битов может случайным образом создать не только действительное сообщение, которое удовлетворяет любому используемому нами коду с исправлением ошибок, но также действительна в том смысле, что это имеет смысл для приемника, очень мала. Мы также можем использовать такие вещи, как криптография с открытым ключом, для шифрования и / или подписи сообщений, что усложнит повторное подделывание реального сообщения. В-третьих, значительная часть нашего общения чувствительна ко времени - мы на самом деле общаемся с людьми, поэтому мы не должны задерживаться с ответом, и в этом случае мы должны быть уверены, что человек, с которым мы разговариваем, - это человек, с которым мы должны разговаривать. к.

В большинстве случаев мы просто предполагаем, что в сообщениях нет значительного источника ошибок, и нам это сходит с рук. Мы можем представить себе сценарий, когда злонамеренный посредник действительно портит канал, но мы сталкиваемся с несколькими вещами; криптография с открытым ключом по-прежнему эффективна, но, что более важно, усилия и мощность, необходимые для точного повреждения достаточно значительной части коммуникации, намного превосходят реальные возможности. Если бы это было не так, разведка по военным сигналам была бы гораздо более эффективной, чем была бы (не то, чтобы она не была эффективной, она была бы лучше).

Обратите внимание, что хотя я в основном касался связи между компьютером и машиной, для межличностного общения можно приводить те же аргументы - источники шума обычно не могут подделать целое сообщение, у нас есть системы коррекции для тех, которые вводят случайные, низкоуровневые шум, и усилия почти не стоят того, чтобы быть достаточно обеспеченным и мотивированным злоумышленником.

Люк Мэтисон
источник
7
AFAIK, проблема двух генералов не требует вредоносного канала связи, просто ненадежный. Проблема не в том, что сообщения повреждены или изменены; только с ними не принимаются: en.wikipedia.org/wiki/…
Ajedi32
1
@ Ajedi32, я должен прояснить, что я имею в виду - метафорическая установка имеет злого врага, мессенджеры не просто уходят, но то, к чему это будет наиболее приравнено, - это потеря целых сообщений без вероятностной модели. Учитывая, что мы не отправляем сообщения как элементарные объекты, «потерю сообщения» можно интерпретировать как потерю битов, потерю пакетов и т. Д. Другая половина заключается в том, что каналы связи обладают анализируемыми свойствами - они могут иметь случайный шум, но это в модельной манере, с которой мы можем с уверенностью справиться, тогда единственный другой источник потери информации - это ...
Люк Мэтисон,
... фактическое вредоносное поведение, которое мы также можем сделать заметным. Короче говоря, проблема двух генералов дает гипотетическую ситуацию, которая нереальна в своих предположениях. Да, может где-то потерять информацию, но нет (в повседневных разумных ситуациях) безграничной ошибки.
Люк Мэтисон
16

«Неразрешимость» проблемы «двух общих» (или называемой проблемой «скоординированной атаки») ограничена ее контекстом, т. Е. В полностью асинхронной распределенной системе с ненадежными ненадежными каналами связи. В нашей повседневной жизни люди могут "терпеть" такие плохие ситуации.

В книге « Рассуждение о знании» ; В разделе 6.1 авторы отмечают, что

Тот факт, что скоординированная атака подразумевает общее знание, зависит от нашего требования, что скоординированная атака должна быть одновременной . На практике одновременность может быть слишком сильным требованием. Протокол, который гарантирует, что генералы атакуют в течение короткого времени друг от друга, может быть вполне удовлетворительным.

Далее он комментирует, что

Тем не менее, даже такие более слабые формы координации недостижимы, если общение ненадежно .

В нашей повседневной жизни люди могут терпеть (и терпят) короткие задержки и ненадежные каналы (как разработано @Luke Mathieson). (Если вы пойдете глубже и спросите «как» и «почему», то это, вероятно, выходит за рамки информатики.)

Hengxin
источник
2
Если вы посмотрите на современное общение, особенно на войне, то очень тщательно выбираете стратегии, которые не зависят от таких проблем. Когда они зависят от таких проблем, почти всегда существует какой-то план действий в чрезвычайных ситуациях, чтобы справиться с ним. В программе по информатике мы складываем все яйца в одну корзину и объявляем «любой потенциальный сбой, каким бы невероятным он ни был, слишком велик»
Корт Аммон - Восстановите Монику
3

Потому что нам не нужна гарантированная уверенность в том, что что - то будет происходить , когда мы имеем достаточный опыт , который говорит нам , что , вероятно , произойдет. Например, скажем, что друг хочет встретиться со мной. Он посылает мне по электронной почте время и место, и я отвечаю: «Звучит отлично, увидимся». Мне не нужно больше информации, чтобы продолжить встречу с ним в указанном месте и времени. Просто потому, что я не мог гарантироватьтого, что он получил мой ответ, недостаточно, чтобы заставить меня действовать исходя из моих предположений. Мой опыт подсказывает, что электронная почта достаточно надежна, и если по какой-то причине он не получит мой ответ, он снова отправит мне электронное письмо. Мой опыт подсказывает мне не беспокоиться о том, что мой ответ молча отбрасывают, а все последующие сообщения от него также молча отбрасывают. Такое сочетание событий не происходит достаточно часто, чтобы существенно помешать моей способности встречаться с людьми.

Если бы такие угловые случаи (или другие проблемы) начали происходить чаще, это изменило бы мой опыт , и тогда я бы подумал об изменении своей стратегии. Например, я мог бы позвонить человеку, а не по электронной почте. Или я мог бы использовать веб-сайт календаря. Или какой-то другой вариант.

Применительно к межличностному общению я обнаружил, что технические проблемы проблемы двух генералов сами по себе не являются чрезвычайно проблематичными, но могут усилить другие проблемы. Что мне делать, если я отправляю кому-нибудь запрос на работу по электронной почте и не получаю от него ответа в течение разумного периода времени? Как долго я должен задерживаться перед отправкой последующего сообщения? Если я отправлю последующее сообщение, они воспримут это как дружеское напоминание или они будут чувствовать раздражение? Как мне сформулировать последующее сообщение, чтобы оно не выглядело слишком самонадеянным (потому что если сеть фактически отбросила предыдущее сообщение, то это первое, что они услышали от меня)?

Природа этих вопросов зависит от людей и контекста. Там нет гарантированных ответов. Но опять же, нам не нужны гарантии, чтобы быть успешными. Все, что нам нужно, это такие вещи, как самоанализ, сочувствие и способность учиться на опыте. Мы можем обнаружить и разработать наши собственные уникальные стратегии, которые могут значительно отличаться от других, которые позволяют нам со временем стать лучшими коммуникаторами.

kartik_subbarao
источник
-1

Можете ли вы дать мне точное значение пи в десятичной записи? Мы, люди, округляем и приближаемся, когда знаем, что точное значение неразрешимо.

Rajuk
источник
2
Добро пожаловать! Мы ищем ответы, которые содержат некоторые детали и объяснения, а не просто краткие комментарии. Идея в вашем комментарии уже подробно обсуждалась в существующих ответах на вопрос, поэтому я не думаю, что вы вообще что-то здесь добавляете.
Дэвид Ричерби,
Мой комментарий лаконичен и точен. Перефразированный вопрос заключался в том, как люди соглашаются на что-либо, если мы знаем, что проблема неразрешима? Мой ответ от математики (особенно пи в десятичной), которую мы округляем и приближаем.
RajuK
Ваш комментарий - это просто комментарий. Когда у вас будет достаточно репутации, вы сможете оставлять комментарии. До тех пор вы можете только публиковать ответы, и ожидается, что ответы будут более подробными, чем это, как я уже объяснил.
Дэвид Ричерби
Вопрос как таковой - это не вопрос комп-науки, а вопрос о поведении человека. Следовательно, мой ответ был к сути. Почему вопрос не был помечен как вопрос, не связанный с компьютерной наукой, и был отклонен?
RajuK
Если вы считаете, что вопрос не по теме, вы должны пометить его, а не отвечать на него. Также обратите внимание, что сайты Stack Exchange (даже комментарии к ним) не предназначены для обсуждения.
Дэвид Ричерби
-1

Доказательство только говорит о том, что невозможно разработать протокол, который надежно решит проблему (т.е. идеально в каждом случае).

В нем не говорится, что невозможно разработать протокол, который в основном решает проблему. Люди, являющиеся байесовскими по природе, весьма хороши в разработке протоколов, которые решают данную проблему с некоторой степенью качества и / или некоторой степенью успеха, которая является удовлетворительной с точки зрения прибылей и убытков в долгосрочной перспективе.

Нигде человек
источник