Проблема двух генералов
В области вычислений « Проблема двух генералов» — это мысленный эксперимент, призванный проиллюстрировать подводные камни и проблемы проектирования, связанные с попыткой скоординировать действие путем общения по ненадежному каналу связи. В эксперименте два генерала могут общаться друг с другом, только отправив гонца через территорию противника. Эксперимент спрашивает, как они могут достичь соглашения о времени начала атаки, зная при этом, что любой посыльный, которого они отправят, может быть захвачен.
Проблема двух генералов часто появляется как введение в более общую проблему византийских генералов на вводных занятиях по компьютерным сетям (особенно в отношении протокола управления передачей , где показано, что TCP не может гарантировать согласованность состояний между конечными точками и почему это важно). случае), хотя это применимо к любому типу двусторонней связи, где возможны сбои связи. Ключевая концепция эпистемической логики , эта проблема подчеркивает важность общеизвестных знаний . Некоторые авторы также называют это парадоксом двух генералов , проблемой двух армий или проблемой скоординированного нападения . [ 1 ] [ 2 ] Проблема двух генералов была первой проблемой компьютерной связи, неразрешимость которой оказалась доказана. [ 3 ] Важным следствием этого доказательства является то, что такие обобщения, как проблема византийских генералов, также неразрешимы перед лицом произвольных сбоев связи, что обеспечивает основу реалистичных ожиданий для любых протоколов распределенной согласованности.
Определение
[ редактировать ]Две армии , каждая из которых возглавляется разными генералами , готовятся атаковать укрепленный город. Армии расположились лагерем недалеко от города, каждая в своей долине. Третья долина разделяет два холма, и единственный способ общения двух генералов — это отправить гонцов через долину. К сожалению, долина оккупирована защитниками города, и есть шанс, что любой гонец, посланный через долину, будет схвачен. [ 4 ]
Хотя два генерала договорились, что будут атаковать, они еще не договорились о времени атаки. Для достижения успеха необходимо, чтобы армии двух генералов атаковали город одновременно, иначе армия атакующих-одиночек погибнет при попытке. Таким образом, они должны общаться друг с другом, чтобы определить время атаки и согласиться на атаку в это время, и каждый генерал должен знать, что другой генерал знает, что они согласились с планом атаки. Поскольку подтверждение получения сообщения требуется потенциально бесконечная серия сообщений может быть потеряно так же легко, как и исходное сообщение, для достижения консенсуса . [ 5 ]
Мысленный эксперимент предполагает рассмотрение того, как они могут прийти к консенсусу. В простейшей форме известно, что один генерал является лидером, определяет время атаки и должен сообщить об этом времени другому генералу. Проблема в том, чтобы придумать алгоритмы, которые могли бы использовать генералы, включая отправку сообщений и обработку полученных сообщений, которые могли бы позволить им сделать правильный вывод:
- Да, мы оба нападём в условленное время.
Учитывая, что генералам довольно просто прийти к соглашению о времени атаки (т.е. одно успешное сообщение с успешным подтверждением), тонкость проблемы двух генералов заключается в невозможности разработки алгоритмов, которые генералы могли бы использовать. смело согласиться с приведенным выше утверждением. [ нужна ссылка ]
Иллюстрируя проблему
[ редактировать ]Первый генерал может начать с отправки сообщения: «Атака в 09:00 4 августа». Однако после отправки первый генерал понятия не имеет, дошел ли посланник. Эта неопределенность может привести к тому, что первый генерал не решится атаковать из-за риска оказаться единственным атакующим.
Конечно, второй генерал может послать первому подтверждение: «Я получил ваше сообщение и нападу в 09:00 4 августа». Однако посланник, несущий подтверждение, может столкнуться с захватом, а второй генерал может колебаться, зная, что первый может сдержаться без подтверждения.
Дальнейшие подтверждения могут показаться решением — пусть первый генерал пришлет второе подтверждение: «Я получил ваше подтверждение о планируемой атаке в 09:00 4 августа». Однако этот новый посланник первого генерала тоже может быть схвачен. Таким образом, быстро становится очевидным, что независимо от того, сколько раундов подтверждения будет сделано, невозможно гарантировать выполнение второго требования, заключающегося в том, что каждый генерал уверен, что другой согласился с планом атаки. Оба генерала всегда будут задаваться вопросом, дошел ли их последний посланник. [ 6 ]
Доказательство
[ редактировать ] |
Поскольку этот протокол является детерминированным , предположим, что существует последовательность фиксированного количества сообщений, одно или несколько из которых доставлены успешно, а одно или несколько — нет. Предполагается, что у обоих генералов должна быть общая уверенность в необходимости нападения . Рассмотрим последнее такое сообщение, которое было успешно доставлено. Если бы это последнее сообщение не было успешно доставлено, то по крайней мере один генерал (предположительно получатель) решил бы не атаковать. Однако с точки зрения отправителя последнего сообщения последовательность отправленных и доставленных сообщений точно такая же, какой она была бы, если бы это сообщение было доставлено. Поскольку протокол детерминирован, отправитель последнего сообщения все равно примет решение об атаке. Теперь мы создали ситуацию, когда предложенный протокол приводит к тому, что один генерал атакует, а другой не атакует, что противоречит предположению, что протокол является решением проблемы.
Недетерминированный протокол с потенциально переменным количеством сообщений можно сравнить с конечным деревом с метками ребер , где каждый узел в дереве представляет исследованный пример до указанной точки. Протокол, который завершается перед отправкой каких-либо сообщений, представлен деревом, содержащим только корневой узел. Ребра от узла до каждого дочернего узла помечены сообщениями, отправленными для достижения дочернего состояния. Листовые узлы представляют собой точки, в которых протокол завершается. Предположим, существует недетерминированный протокол P , который решает проблему двух генералов. Затем, используя аргумент, аналогичный тому, который использовался выше для детерминированных протоколов фиксированной длины, P' должен также решить проблему двух генералов, где дерево, представляющее P', получается из дерева для P путем удаления всех листовых узлов и ребер, ведущих им. Поскольку P конечно, из этого следует, что протокол, который завершается до отправки каких-либо сообщений, решит проблему. Но очевидно, что это не так. Следовательно, недетерминированный протокол, решающий проблему, не может существовать.
Инженерные подходы
[ редактировать ] |
Прагматичный подход к решению проблемы двух генералов заключается в использовании схем, которые принимают неопределенность канала связи и не пытаются ее устранить, а, скорее, смягчают ее до приемлемой степени. Например, первый генерал мог бы отправить 100 гонцов, предполагая, что вероятность того, что все будут захвачены, мала. При таком подходе первый генерал будет атаковать несмотря ни на что, а второй генерал будет атаковать, если будет получено какое-либо сообщение. Альтернативно, первый генерал мог бы отправлять поток сообщений, а второй генерал мог бы отправлять подтверждения каждому, при этом каждый генерал чувствовал бы себя более комфортно с каждым полученным сообщением. Однако, как видно из доказательства, ни один из них не может быть уверен, что атака будет скоординированной. Не существует алгоритма, который они могли бы использовать (например, атаковать, если получено более четырех сообщений), который бы наверняка предотвратил атаку одного без другого. Кроме того, первый генерал может пометить каждое сообщение, указав, что это сообщение 1, 2, 3... из n. Этот метод позволит второму генералу узнать, насколько надежен канал, и отправить обратно соответствующее количество сообщений, чтобы обеспечить высокую вероятность получения хотя бы одного сообщения. Если канал можно сделать надежным, то одного сообщения будет достаточно, а дополнительные сообщения не помогут. Последнее имеет такую же вероятность потеряться, как и первое.
Предполагая, что генералы должны жертвовать жизнями каждый раз, когда посыльный отправляется и перехватывается, можно разработать алгоритм, минимизирующий количество посланников, необходимое для достижения максимальной уверенности в том, что атака скоординирована. Чтобы избавить их от принесения в жертву сотен жизней ради достижения очень высокой уверенности в координации, генералы могли бы договориться использовать отсутствие гонцов как признак того, что генерал, начавший сделку, получил хотя бы одно подтверждение и пообещал атаковать. Предположим, что посланнику требуется 1 минута, чтобы пересечь опасную зону, а 200 минут тишины после получения подтверждений позволят нам достичь чрезвычайно высокой уверенности, не жертвуя при этом жизнями посланников. В этом случае мессенджеры используются только в том случае, если сторона не получила время атаки. По истечении 200 минут каждый генерал может рассуждать: «Я не получал дополнительного сообщения в течение 200 минут; либо 200 гонцов не смогли пересечь опасную зону, либо это означает, что другой генерал подтвердил, совершил атаку и имеет уверенность». Я тоже буду».
История
[ редактировать ]Проблема двух генералов и доказательство ее невозможности были впервые опубликованы Э. А. Аккоюнлу, К. Эканадхамом и Р. В. Хубером в 1975 году в книге «Некоторые ограничения и компромиссы при проектировании сетевых коммуникаций». [ 7 ] где оно описано начиная со страницы 73 в контексте общения двух групп гангстеров.
« Парадоксом двух генералов». назвал Эту проблему Джим Грей [ 8 ] в 1978 г. в «Заметках об операционных системах баз данных». [ 9 ] начиная со страницы 465. Эта ссылка широко используется как источник определения проблемы и доказательства невозможности, хотя оба они были опубликованы ранее, как упоминалось выше.
Ссылки
[ редактировать ]- ^ Гмытрасевич, Петр Ю.; Эдмунд Х. Дерфи (1992). «Теоретико-рекурсивное моделирование и проблема скоординированной атаки» . Системы планирования искусственного интеллекта . Сан-Франциско: Издательство Morgan Kaufmann. стр. 88–95. дои : 10.1016/B978-0-08-049944-4.50016-1 . ISBN 9780080499444 . Проверено 27 декабря 2013 г.
{{cite book}}:|journal=игнорируется ( помогите ) - ↑ Скоординированная атака и ревнивые амазонки Алессандро Панконези. Проверено 17 мая 2011 г.
- ^ Лесли Лэмпорт. «Решенные проблемы, нерешенные проблемы и непроблемы в параллелизме» . 1983. п. 8.
- ^ Руби, Мэтт. «Как проблема византийского генерала относится к вам в 2024 году» . Лебединый биткойн . Проверено 16 февраля 2024 г.
- ^ «Проблема византийских генералов (консенсус при наличии неопределенности)» (PDF) . Имперский колледж Лондона . Проверено 16 февраля 2024 г.
- ^ Лэмпорт, Лесли; Шостак, Роберт; Пиз, Маршалл. «Проблема византийских генералов» (PDF) . НИИ Интернешнл . Проверено 16 февраля 2024 г.
- ^ Аккоюнлу, Э.А.; Эканадхам, К.; Хубер, Р.В. (1975). Некоторые ограничения и компромиссы при проектировании сетевых коммуникаций . Портал.acm.org. стр. 67–74. дои : 10.1145/800213.806523 . S2CID 788091 . Проверено 19 марта 2010 г.
- ^ «Домашняя страница сводки Джима Грея» . Research.microsoft.com. 3 мая 2004 г. Проверено 19 марта 2010 г.
- ^ Р. Байер, Р. М. Грэм и Г. Зигмюллер (1978). Операционные системы . Спрингер-Верлаг. стр. 393–481. ISBN 0-387-09812-7 .
{{cite book}}: CS1 maint: multiple names: authors list (link) Online version: Примечания по операционным системам баз данных . Портал.acm.org . Проверено 19 марта 2010 г.