В области вычислений проблема двух генералов - это мысленный эксперимент, призванный проиллюстрировать подводные камни и проблемы проектирования при попытке скоординировать действие путем общения по ненадежной связи. В эксперименте два генерала могут общаться друг с другом, только отправляя посыльного через вражескую территорию. Эксперимент спрашивает, как они могут договориться о времени начала атаки, зная, что любой посланник, который они отправят, может быть захвачен.
Он связан с более общей проблемой византийских генералов и часто появляется на вводных курсах по компьютерным сетям (особенно в отношении протокола управления передачей , где он показывает, что TCP не может гарантировать согласованность состояний между конечными точками и почему это так), хотя это применимо к любому типу двусторонней связи, где возможны сбои связи. Эта проблема является ключевым понятием в эпистемической логике и подчеркивает важность общих знаний . Некоторые авторы также называют это парадоксом двух генералов , проблемой двух армий или проблемой скоординированной атаки . [1][2] Проблема двух генералов была первой проблемой компьютерной связи, которая оказалась неразрешимой. Важным следствием этого доказательства является то, что обобщения, подобные проблеме византийских генералов, также неразрешимы перед лицом произвольных сбоев связи, что обеспечивает основу для реалистичных ожиданий для любых протоколов распределенной согласованности.
Определение
Две армии , каждую под командованием разных генералов , готовятся атаковать укрепленный город. Армии располагаются лагерем недалеко от города, каждая в своей долине. Третья долина разделяет два холма, и единственный способ для двух генералов общаться - это послать посланников через долину. К сожалению, долина занята защитниками города, и есть шанс, что любой посланник, посланный через долину, будет захвачен.
Хотя два генерала договорились о нападении, они не договорились о времени для атаки. Чтобы добиться успеха, требуется, чтобы армии двух генералов атаковали город одновременно, иначе армия одинокого атакующего погибнет при попытке. Таким образом, они должны общаться друг с другом, чтобы выбрать время для атаки и согласиться атаковать в это время, и каждый генерал должен знать, что другой генерал знает, что они согласились с планом атаки. Поскольку подтверждение получения сообщения может быть потеряно так же легко, как и исходное сообщение, для достижения консенсуса требуется потенциально бесконечная серия сообщений .
Мысленный эксперимент включает рассмотрение того, как они могут прийти к консенсусу. В простейшей форме один генерал, как известно, является лидером, решает время атаки и должен сообщить это время другому генералу. Проблема состоит в том, чтобы придумать алгоритмы, которые могут использовать генералы, включая отправку сообщений и обработку полученных сообщений, которые позволят им сделать правильный вывод:
- Да, мы оба атакуем в оговоренное время.
Допуская, что генералам довольно просто прийти к соглашению о времени атаки (то есть одно успешное сообщение с успешным подтверждением), тонкость проблемы двух генералов заключается в невозможности разработки алгоритмов для использования генералами. безопасно согласиться с приведенным выше утверждением.
Иллюстрируя проблему
Первый генерал может начать с сообщения «Атака в 09:00 4 августа». Однако после отправки первый генерал понятия не имеет, прошел ли посланник. Эта неопределенность может привести к тому, что первый генерал не решится атаковать из-за риска оказаться единственным нападающим.
Конечно, второй генерал может отправить подтверждение первому: «Я получил ваше сообщение и атакую в 09:00 4 августа». Однако посыльный, несущий подтверждение, может столкнуться с захватом, а второй генерал может колебаться, зная, что первый может сдерживаться без подтверждения.
Дальнейшие подтверждения могут показаться решением - пусть первый генерал отправит второе подтверждение: «Я получил ваше подтверждение запланированной атаки в 09:00 4 августа». Однако этот новый посланник от первого генерала тоже может быть схвачен. Таким образом, быстро становится очевидным, что независимо от того, сколько раундов подтверждения сделано, нет способа гарантировать второе требование, чтобы каждый генерал был уверен, что другой согласился с планом атаки. Оба генерала всегда будут гадать, прошел ли их последний посланник.
Доказательство
Для детерминированных протоколов с фиксированным количеством сообщений
Поскольку этот протокол является детерминированным , предположим, что существует последовательность из фиксированного числа сообщений, одно или несколько успешно доставлены, а одно или несколько нет. Предполагается, что у обоих генералов должна быть общая уверенность в том, что они нападут .
Рассмотрим последнее такое сообщение, которое было успешно доставлено. Если бы это последнее сообщение не было успешно доставлено, то хотя бы один генерал (предположительно получатель) решил бы не атаковать. Однако с точки зрения отправителя этого последнего сообщения последовательность отправленных и доставленных сообщений в точности такая же, как если бы это сообщение было доставлено.
Поскольку протокол детерминирован, обычная отправка последнего сообщения все равно решит атаковать. Теперь мы создали ситуацию, когда предлагаемый протокол приводит к тому, что один генерал атакует, а другой не атакует, что противоречит предположению, что протокол был решением проблемы.
Для недетерминированных протоколов и протоколов переменной длины
Недетерминированный протокол с потенциально переменным количеством сообщений можно сравнить с конечным деревом , помеченным краями , где каждый узел в дереве представляет собой изученный пример до указанной точки. Протокол, который завершается перед отправкой любых сообщений, представлен деревом, содержащим только корневой узел. Ребра от узла к каждому дочернему элементу помечены сообщениями, отправленными для достижения дочернего состояния. Конечные узлы представляют собой точки, в которых протокол завершается.
Предположим, что существует недетерминированный протокол P, который решает проблему двух генералов. Затем, аналогичный аргумент , который используется для фиксированной длиной детерминированных протоколов выше, P « также должен решить две генеральские проблемы, где дерево , представляющее Р» получается из что для P , удаляя все узлы листьев и края ведущих им.
Поскольку P конечно, из этого следует, что протокол, который завершается перед отправкой каких-либо сообщений, решит проблему. Но очевидно, что это не так. Следовательно, недетерминированный протокол, решающий проблему, не может существовать.
Инженерные подходы
Прагматический подход к решению проблемы двух генералов заключается в использовании схем, которые принимают неопределенность канала связи и не пытаются устранить ее, а скорее смягчают ее до приемлемой степени. Например, первый генерал может послать 100 гонцов, ожидая, что вероятность того, что все будут захвачены, мала. При таком подходе первый генерал будет атаковать несмотря ни на что, а второй генерал будет атаковать, если будет получено какое-либо сообщение. В качестве альтернативы первый генерал мог бы послать поток сообщений, а второй генерал мог бы послать подтверждение каждому, при этом каждый генерал чувствовал бы себя более комфортно с каждым полученным сообщением. Однако, как видно из доказательства, нельзя быть уверенным в том, что атака будет скоординирована. Не существует алгоритма, который они могли бы использовать (например, атаковать, если получено более четырех сообщений), который гарантированно предотвратил бы одно нападение без другого. Кроме того, первый генерал может отправлять пометку на каждое сообщение, говоря, что это сообщение 1, 2, 3 ... из n. Этот метод позволит второму генералу узнать, насколько надежен канал, и отправить соответствующее количество сообщений обратно, чтобы гарантировать высокую вероятность получения хотя бы одного сообщения. Если канал можно сделать надежным, тогда одного сообщения будет достаточно, а дополнительные сообщения не помогут. Последний может потеряться с такой же вероятностью, как и первый.
Предполагая, что генералы должны жертвовать жизнями каждый раз, когда посланник отправляется и перехватывается, можно разработать алгоритм, минимизирующий количество посланников, необходимых для достижения максимальной степени уверенности в том, что атака скоординирована. Чтобы спасти их от принесения в жертву сотен жизней и достижения очень высокой степени уверенности в координации, генералы могли бы согласиться использовать отсутствие посланников как указание на то, что генерал, начавший транзакцию, получил по крайней мере одно подтверждение и пообещал атаковать. Предположим, посланнику требуется 1 минута, чтобы пересечь опасную зону, а 200 минут молчания после получения подтверждений позволят нам достичь чрезвычайно высокой уверенности, не жертвуя жизнями посланника. В этом случае мессенджеры используются только в том случае, если партия не получила время атаки. По истечении 200 минут каждый генерал может рассуждать: «Я не получал дополнительных сообщений в течение 200 минут; либо 200 посыльных не смогли пересечь опасную зону, либо это означает, что другой генерал подтвердил и совершил атаку и уверен Я тоже буду".
История
Проблема двух генералов и доказательство ее невозможности были впервые опубликованы Э. А. Аккоюнлу, К. Эканадхамом и Р. В. Хубером в 1975 г. в статье «Некоторые ограничения и компромиссы при проектировании сетевых коммуникаций» [3], где она описывается, начиная с стр. 73 в контексте общения двух группировок гангстеров.
Эта проблема получили название Два Генералов Paradox от Джима Грея [4] в 1978 году в «Записках в операционных системах базы данных» [5] на стр 465. Этой ссылкой широко дан в качестве источника для определения проблемы и доказательство невозможности, хотя оба были опубликованы ранее, как упоминалось выше.
Рекомендации
- ^ Gmytrasiewicz, Петр J .; Эдмунд Х. Дерфи (1992). «Теоретико-решающее рекурсивное моделирование и проблема согласованной атаки» . Труды Первой международной конференции по системам планирования искусственного интеллекта . Сан-Франциско: Издательство Морган Кауфманн: 88–95. DOI : 10.1016 / B978-0-08-049944-4.50016-1 . ISBN 9780080499444. Проверено 27 декабря 2013 года .
- ↑ Скоординированная атака и завистливые амазонки Алессандро Панконези. Проверено 17 мая 2011.
- ^ Аккоюнлу, Э.А.; Ekanadham, K .; Хубер, Р.В. (1975). Некоторые ограничения и компромиссы при проектировании сетевых коммуникаций (PDF) . Portal.acm.org. С. 67–74. DOI : 10.1145 / 800213.806523 . S2CID 788091 . Проверено 19 марта 2010 .
- ^ "Домашняя страница резюме Джима Грея" . Research.microsoft.com. 2004-05-03 . Проверено 19 марта 2010 .
- ^ «Примечания по операционным системам базы данных» . Portal.acm.org . Проверено 19 марта 2010 .